摘要: 哈希結(jié)構(gòu)

C++博客 Alex-Lee 2009-10-21

哈希結(jié)構(gòu)在處理大量數(shù)據(jù)時具有很好的優(yōu)勢，在插入，查詢，刪除等操作上具有常量的時間復(fù)雜度O(1)。使用范圍是數(shù)據(jù)集具有自然數(shù)上的關(guān)鍵字域（不是自然數(shù)也需要能夠轉(zhuǎn)為自然數(shù)域），通過哈希函數(shù)將關(guān)鍵字映射到尋址數(shù)組的槽。由于關(guān)鍵字域U[0...n]與尋址數(shù)組[0...m]中，總是n>m，也就是說，總有多個關(guān)鍵字對應(yīng)一個槽。這個碰撞就需要通過一些方法改變。可以通過拉鏈法（鏈表法）和開放地址法。對于拉鏈法中，鏈表不能太長，否則影響速度，最好控制在10個元素之內(nèi)，這樣就要去尋址數(shù)組長度m>= n/10，這樣就會多消耗些空間。為了讓每個鏈表長度基本一致，就需要  閱讀全文