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