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