摘要: 哈希結構

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

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