數據結構——哈希表解析介紹.doc

本文根據他人博文整理而來，尊重原創(chuàng)。在前面的系列文章中，依次介紹了基于無序列表的順序查找，基于有序數組的二分查找，平衡查找樹，以及紅黑樹，下圖是他們在平均以及最差情況下的時間復雜度：可以看到在時間復雜度上，紅黑樹在平均情況下插入，查找以及刪除上都達到了lgN的時間復雜度。那么有沒有查找效率更高的數據結構呢，答案就是本文接下來要介紹了散列表，也叫哈希表(Hash Table)什么是哈希表哈希表就是一種以 鍵-值(key-indexed) 存儲數據的結構，我們只要輸入待查找的值即key，即可查找到其對應的值。哈希的思路很簡單，如果所有的鍵都是整數，那么就可以使用一個簡單的無序數組來實現：將鍵作為索引，值即為其對應的值，這樣就可以快速訪問任意鍵的值。這是對于簡單的鍵的情況，我們將其擴展到可以處理更加復雜的類型的鍵。使用哈希查找有兩個步驟:1. 使用哈希函數將被查找的鍵轉換為數組的索引。在理想的情況下，不同的鍵會被轉換為不同的索引值，但是在有些情況下我們需要處理多個鍵被哈希到同一個索引值的情況。所以哈希查找的第二個步驟就是處理沖突2. 處理哈希碰撞沖突。有很多處理哈希碰撞沖突的方法，本文后面會介紹拉鏈法和線性探測法。哈希表是一個在時間和空間上做出權衡的經典例子。如果沒有內存限制，那么可以直接將鍵作為數組的索引。那么所有的查找時間復雜度為O(1)；如果沒有時間限制，那么我們可以使用無序數組并進行順序查找，這樣只需要很少的內存。哈希表使用了適度的時間和空間來在這兩個極端之間找到了平衡。只需要調整哈希函數算法即可在時間和空間上做出取舍。哈希函數哈希查找第一步就是使用哈希函數將鍵映射成索引。這種映射函數就是哈希函數。如果我們有一個保存0-M數組，那么我們就需要一個能夠將任意鍵轉換為該數組范圍內的索引（0M-1）的哈希函數。哈希函數需要易于計算并且能夠均勻分布所有鍵。比如舉個簡單的例子，使用手機號碼后三位就比前三位作為key更好，因為前三位手機號碼的重復率很高。再比如使用身份證號碼出生年月位數要比使用前幾位數要更好。在實際中，我們的鍵并不都是數字，有可能是字符串，還有可能是幾個值的組合等，所以我們需要實現自己的哈希函數。1. 正整數獲取正整數哈希值最常用的方法是使用除留余數法。即對于大小為素數M的數組，對于任意正整數k，計算k除以M的余數。M一般取素數。2. 字符串將字符串作為鍵的時候，我們也可以將他作為一個大的整數，采用保留除余法。我們可以將組成字符串的每一個字符取值然后進行哈希，比如public int GetHashCode(string str) char s = str.ToCharArray(); int hash = 0; for (int i = 0; i s.Length; i+) hash = si + (31 * hash); return hash;上面的哈希值是Horner計算字符串哈希值的方法，公式為:h = s0 31L1+ + sL 3 312+ sL 2 311+ sL 1 310舉個例子，比如要獲取”call”的哈希值，字符串c對應的unicode為99，a對應的unicode為97，L對應的unicode為108，所以字符串”call”的哈希值為 3045982 = 99313+ 97312+ 108311+ 108310= 108 + 31 (108 + 31 (97 + 31 (99)如果對每個字符去哈希值可能會比較耗時，所以可以通過間隔取N個字符來獲取哈西值來節(jié)省時間，比如，可以 獲取每8-9個字符來獲取哈希值：public int GetHashCode(string str) char s = str.ToCharArray(); int hash = 0; int skip = Math.Max(1, s.Length / 8); for (int i = 0; i s.Length; i+=skip) hash = si + (31 * hash); return hash;但是，對于某些情況，不同的字符串會產生相同的哈希值，這就是前面說到的哈希沖突（Hash Collisions），比如下面的四個字符串：如果我們按照每8個字符取哈希的話，就會得到一樣的哈希值。所以下面來講解如何解決哈希碰撞：避免哈希沖突拉鏈法 (Separate chaining with linked lists)通過哈希函數，我們可以將鍵轉換為數組的索引(0-M-1)，但是對于兩個或者多個鍵具有相同索引值的情況，我們需要有一種方法來處理這種沖突。一種比較直接的辦法就是，將大小為M 的數組的每一個元素指向一個條鏈表，鏈表中的每一個節(jié)點都存儲散列值為該索引的鍵值對，這就是拉鏈法。下圖很清楚的描述了什么是拉鏈法。圖中，”John Smith”和”Sandra Dee” 通過哈希函數都指向了152 這個索引，該索引又指向了一個鏈表， 在鏈表中依次存儲了這兩個字符串。該方法的基本思想就是選擇足夠大的M，使得所有的鏈表都盡可能的短小，以保證查找的效率。對采用拉鏈法的哈希實現的查找分為兩步，首先是根據散列值找到等一應的鏈表，然后沿著鏈表順序找到相應的鍵。 我們現在使用我們之前介紹符號表中的使用無序鏈表實現的查找表SequentSearchSymbolTable來實現我們這里的哈希表。當然，您也可以使用.NET里面內置的LinkList。首先我們需要定義一個鏈表的總數，在內部我們定義一個SequentSearchSymbolTable的數組。然后每一個映射到索引的地方保存一個這樣的數組。public class SeperateChainingHashSet : SymbolTables where TKey : IComparable, IEquatable private int M;/散列表大小 private SequentSearchSymbolTable st;/ public SeperateChainingHashSet() : this(997) public SeperateChainingHashSet(int m) this.M = m; st = new SequentSearchSymbolTablem; for (int i = 0; i m; i+) sti = new SequentSearchSymbolTable(); private int hash(TKey key) return (key.GetHashCode() & 0x7fffffff) % M; public override TValue Get(TKey key) return sthash(key).Get(key); public override void Put(TKey key, TValue value) sthash(key).Put(key, value); 可以看到，該實現中使用 Get方法來獲取指定key的Value值，我們首先通過hash方法來找到key對應的索引值，即找到SequentSearchSymbolTable數組中存儲該元素的查找表，然后調用查找表的Get方法，根據key找到對應的Value。 Put方法用來存儲鍵值對，首先通過hash方法找到改key對應的哈希值，然后找到SequentSearchSymbolTable數組中存儲該元素的查找表，然后調用查找表的Put方法，將鍵值對存儲起來。 hash方法來計算key的哈希值， 這里首先通過取與&操作，將符號位去除，然后采用除留余數法將key應到到0-M-1的范圍，這也是我們的查找表數組索引的范圍。實現基于拉鏈表的散列表，目標是選擇適當的數組大小M，使得既不會因為空鏈表而浪費內存空間，也不會因為鏈表太而在查找上浪費太多時間。拉鏈表的優(yōu)點在于，這種數組大小M的選擇不是關鍵性的，如果存入的鍵多于預期，那么查找的時間只會比選擇更大的數組稍長，另外，我們也可以使用更高效的結構來代替鏈表存儲。如果存入的鍵少于預期，索然有些浪費空間，但是查找速度就會很快。所以當內存不緊張時，我們可以選擇足夠大的M，可以使得查找時間變?yōu)槌担绻麅却婢o張時，選擇盡量大的M仍能夠將性能提高M倍。線性探測法線性探測法是開放尋址法解決哈希沖突的一種方法，基本原理為，使用大小為M的數組來保存N個鍵值對，其中MN，我們需要使用數組中的空位解決碰撞沖突。如下圖所示：對照前面的拉鏈法，在該圖中，”Ted Baker” 是有唯一的哈希值153的，但是由于153被”Sandra Dee”占用了。而原先”Snadra Dee”和”John Smith”的哈希值都是152的，但是在對”Sandra Dee”進行哈希的時候發(fā)現152已經被占用了，所以往下找發(fā)現153沒有被占用，所以存放在153上，然后”Ted Baker”哈希到153上，發(fā)現已經被占用了，所以往下找，發(fā)現154沒有被占用，所以值存到了154上。開放尋址法中最簡單的是線性探測法：當碰撞發(fā)生時即一個鍵的散列值被另外一個鍵占用時，直接檢查散列表中的下一個位置即將索引值加1，這樣的線性探測會出現三種結果：1. 命中，該位置的鍵和被查找的鍵相同2. 未命中，鍵為空3. 繼續(xù)查找，該位置和鍵被查找的鍵不同。實現線性探測法也很簡單，我們只需要兩個大小相同的數組分別記錄key和value。public class LinearProbingHashSet : SymbolTables where TKey : IComparable, IEquatable private int N;/符號表中鍵值對的總數 private int M = 16;/線性探測表的大小 private TKey keys; private TValue values; public LinearProbingHashSet() keys = new TKeyM; values = new TValueM; private int hash(TKey key) return (key.GetHashCode() & 0xFFFFFFF) % M; public override TValue Get(TKey key) for (int i = hash(key); keysi != null; i = (i + 1) % M) if (key.Equals(keysi) return valuesi; return default(TValue); public override void Put(TKey key, TValue value) int hashCode = hash(key); for (int i = hashCode; keysi != null; i = (i + 1) % M) if (keysi.Equals(key)/如果和已有的key相等，則用新值覆蓋 valuesi = value; return; /插入 keysi = key; valuesi = value; 線性探查（Linear Probing）方式雖然簡單，但是有一些問題，它會導致同類哈希的聚集。在存入的時候存在沖突，在查找的時候沖突依然存在。性能分析我們可以看到，哈希表存儲和查找數據的時候分為兩步，第一步為將鍵通過哈希函數映射為數組中的索引， 這個過程可以認為是只需要常數時間的。第二步是，如果出現哈希值沖突，如何解決，前面介紹了拉鏈法和線性探測法下面就這兩種方法進行討論：對于拉鏈法，查找的效率在于鏈表的長度，一般的我們應該保證長度在M/8M/2之間，如果鏈表的長度大于M/2，我們可以擴充鏈表長度。如果長度在0M/8時，我們可以縮小鏈表。對于線性探測法，也是如此，但是動態(tài)調整數組的大小需要對所有的值從新進行重新散列并插入新的表中。不管是拉鏈法還是散列法，這種動態(tài)調整鏈表或者數組的大小以提高查詢效率的同時，還應該考慮動態(tài)改變鏈表或者數組大小的成本。散列表長度加倍的插入需要進行大量的探測， 這種均攤成本在很多時候需要考慮。哈希碰撞攻擊我們知道如果哈希函數選擇不當會使得大量的鍵都會映射到相同的索引上，不管是采用拉鏈法還是開放尋址法解決沖突，在后面查找的時候都需要進行多次探測或者查找， 在很多時候會使得哈希表的查找效率退化，而不再是常數時間。下圖清楚的描述了退化后的哈希表：哈希表攻擊就是通過精心構造哈希函數，使得所有的鍵經過哈希函數后都映射到同一個或者幾個索引上，將哈希表退化為了一個單鏈表，這樣哈希表的各種操作，比如插入，查找都從O(1)退化到了鏈表的查找操作，這樣就會消耗大量的CPU資源，導致系統無法響應，從而達到拒絕服務供給(Denial of Service, Dos)的目的。之前由于多種編程語言的哈希算法的“非隨機”而出現了Hash碰撞的DoS安全漏洞，在ASP.NET中也曾出現過這一問題。在.NET中String的哈希值內部實現中，通過使用哈希值隨機化來對這種問題進行了限制，通過對碰撞次數設置閾值，超過該閾值就對哈希函數進行隨機化，這也是防止哈希表退化的一種做法。下面是BCL中string類型的GetHashCode方法的實現，可以看到，當碰撞超過一定次數的時候，就會開啟條件編譯，對哈希函數進行隨機化。ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail), SecuritySafeCritical, _DynamicallyInvokablepublic override unsafe int GetHashCode() if (HashHelpers.s_UseRandomizedStringHashing) return InternalMarvin32HashString(this, this.Length, 0L); fixed (char* str = (char*) this) char* chPtr = str; int num = 0x15051505; int num2 = num; int* numPtr = (int*) chPtr; int length = this.Length; while (length 2) num = (num 0x1b) numPtr0; num2 = (num2 0x1b) numPtr1; numPtr += 2; length -= 4; if (length 0) num = (num 0x1b) numPtr0; return (num + (num2 * 0x5d588b65); .NET中哈希的實現我們可以通過在線源碼查看.NET 中Dictionary，類型的實現，我們知道任何作為key的值添加到Dictionary中時，首先會獲取key的hashcode，然后將其映射到不同的bucket中去：public Dictionary(int capacity, IEqualityComparer comparer) if (capacity 0) Initialize(capacity); parer = comparer ? EqualityComparer.Default;在Dictionary初始化的時候，會如果傳入了大小，會初始化bucket 就是調用Initialize方法：private void Initialize(int capacity) int size = HashHelpers.GetPrime(capacity); buckets = new intsize; for (int i = 0; i = 0; i = entriesi.next) if (entriesi.hashCode = hashCode & comparer.Equals(entriesi.key, key) if (add) ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); entriesi.value = value; version+; return; #if FEATURE_RANDOMIZED_STRING_HASHING collisionCount+;#endif int index; if (freeCount 0) index = freeList; freeList = entriesindex.next; freeCount-; else if (count = entries.Length) Resize(); targetBucket = hashCode % buckets.Length; index = count; count+; entriesindex.hashCode = hashCode; entriesindex.next = bucketstargetBucket; entriesindex.key = key; entriesindex.value = value; bucketstargetBucket = index; version+; #if FEATURE_RANDOMIZED_STRING_HASHING if(collisionCount HashHelpers.HashCollisionThreshold & HashHelpers.IsWellKnownEqualityComparer(comparer) comparer = (IEqualityComparer) HashHelpers.GetRandomizedEqualityComparer(comparer); Resize(entries.Length, true); #endif 首先，根據key獲取其hashcode，然后將hashcode除以backet的大小取余映射到目標backet中，然后遍歷該bucket存儲的鏈表，如果找到和key相同的值，如果不允許后添加的鍵與存在的鍵相同替換值(add)，則拋出異常，如果允許，則替換之前的值，然后返回。如果沒有找到，則將新添加的值放到新的bucket中，當空余空間不足的時候，會進行擴容操作(Resize)，然后重新hash到目標bucket。這里面需要注意的是Resize操作比較消耗資源?？偨Y前面幾篇文章先后介紹了基于無序列表的順序查找，基于有序數組的二分查找，平衡查找樹，以及紅黑樹，本篇文章最后介紹了查找算法中的最后一類即符號表又稱哈希表,并介紹了哈希函數以及處理哈希沖突的兩種方法：拉鏈法和線性探測法。各種查找算法的最壞和平均條件下各種操作的時間復雜度如下圖:在實際編寫代碼中，如何選擇合適的數據結構需要根據具體的數據規(guī)模，查找效率要求，時間和空間局限來做出合適的選擇。希望本文以及前面的幾篇文章對您有所幫助。說明:本程序建立的哈希表示意圖:哈希函數為對哈希表長取余源代碼:cppview plaincopy1. /*2. *哈希表算法實現3. *(c)copyright2013,jdh4. *AllRightReserved5. *文件名:main.c6. *程序員:jdh7. */8. 9. #include10. #include11. 12. /*13. *宏定義14. */15. 16. /*17. *數據類型重定義18. */19. 20. #defineuint8_tunsignedchar21. #defineuint16_tunsignedshort22. #defineuint32_tunsignedlong23. 24. /*25. *哈希表長度26. */27. 28. #defineHASH_TABLE_LEN10029. 30. /*31. *數據結構32. */33. /鏈表節(jié)點34. typedefstruct_Link_Node35. 36. uint16_tid;37. uint16_tdata;38. struct_Link_Node*next;39. Link_Node,*Link_Node_Ptr;40. 41. /哈希表頭42. typedefstruct_Hash_Header43. 44. struct_Link_Node*next;45. Hash_Header,*Hash_Header_Ptr;46. 47. /*48. *全局變量49. */50. 51. /哈希表52. Hash_Header_PtrHash_TableHASH_TABLE_LEN;53. 54. /*55. *函數56. */57. 58. /*59. *哈希表函數60. *說明:61. *1.用哈希函數生成id對應的哈希表中的位置62. 輸入:id63. 返回:位置64. */65. 66. uint8_thash_func(uint16_tid)67. 68. uint8_tpos=0;69. 70. pos=id%HASH_TABLE_LEN;71. 72. returnpos;73. 74. 75. /*76. *初始化節(jié)點77. *返回:結點指針78. */79. 80. Link_Node_Ptrinit_link_node(void)81. 82. Link_Node_Ptrnode;83. 84. /申請節(jié)點85. node=(Link_Node_Ptr)malloc(sizeof(Link_Node);86. /初始化長度為087. node-next=NULL;88. 89. returnnode;90. 91. 92. /*93. *初始化哈希表頭結點94. *返回哈希表頭結點指針95. */96. 97. Hash_Header_Ptrinit_hash_header_node(void)98. 99. Hash_Header_Ptrnode;100. 101. /申請節(jié)點102. node=(Hash_Header_Ptr)malloc(sizeof(Hash_Header);103. /初始化長度為0104. node-next=NULL;105. 106. returnnode;107. 108. 109. 110. /*111. *哈希表初始化112. *說明:113. *1.初始化哈希表Hash_Table114. *2.哈希表長度最大不能超過256115. */116. 117. voidinit_hash_table(void)118. 119. uint8_ti=0;120. 121. for(i=0;inext=NULL;125. 126. 127. 128. /*129. *在哈希表增加節(jié)點130. *說明:131. *1.在哈希表的某個鏈表末增加數據132. 輸入:new_node:新節(jié)點133. */134. 135. voidappend_link_node(Link_Node_Ptrnew_node)136. 137. Link_Node_Ptrnode;138. uint8_tpos=0;139. 140. /新節(jié)點下一個指向為空141. new_node-next=NULL;142. 143. /用哈希函數獲得位置144. pos=hash_func(new_node-id);145. 146. /判斷是否為空鏈表147. if(Hash_Tablepos-next=NULL)148. 149. /空鏈表150. Hash_Tablepos-next=new_node;151. 152. else153. 154. /不是空鏈表155. /獲取根節(jié)點156. node=Hash_Tablepos-next;157. 158. /遍歷159. while(node-next!=NULL)160. 161. node=node-next;162. 163. 164. /插入165. node-next=new_node;166. 167. 168. 169. /*170. *在哈希表查詢節(jié)點171. *說明:172. *1.知道在哈希表某處的單鏈表中,并開始遍歷.173. *2.返回的是查詢節(jié)點的前一個節(jié)點指針.這么做是為了做刪除操作.174. 輸入:pos:哈希表數組位置,從0開始計數175. id:所需要查詢節(jié)點的id176. root:如果是根節(jié)點,則*root=1,否則為0177. 返回:所需查詢的節(jié)點的前一個節(jié)點指針,如果是根節(jié)點則返回根節(jié)點,失敗返回0178. */179. 180. Link_Node_Ptrsearch_link_node(uint16_tid,uint8_t*root)181. 182. Link_Node_Ptrnode;183. uint8_tpos=0;184. 185. /用哈希函數獲得位置186. pos=hash_func(id);187. 188. /獲取根節(jié)點189. node=Hash_Tablepos-next;190. 191. /判斷單鏈表是否存在192. if(node=NULL)193. 194. return0;195. 196. 197. /判斷是否是根節(jié)點198. if(node-id=id)199. 200. /是根節(jié)點201. *root=1;202. returnnode;203. 204. else205. 206. /不是根節(jié)點207. *root=0;208. /遍歷209. while(node-next!=NULL)210. 211. if(node-next-id=id)212. 213. returnnode;214. 215. else216. 217. node=node-n