摘要: Hash查找因為其O(1)的查找性能而著稱，被對查找性能要求高的應用所廣泛采用。它的基本思想是：
(1) 創建一個定長的線性Hash表，一般可以初始化時指定length;
(2) 設計Hash函數，將關鍵字key散射到Hash表中。其中hash函數設計是最為關鍵的，均勻分布、沖突概率小全在它；
(3) 通常采用拉鏈方法來解決hash沖突問題，即散射到同一個hash表項的關鍵字，以鏈表形式來表示(也稱為桶backet);
(4) 給定關鍵字key，就可以在O(1) + O(m)的時間復雜度內定位到目標。其中，m為拉鏈長度，即桶深。
閱讀全文