關於Hash雜湊的集中查重方式
這裡總結一下Hash散列當出現不能插入位置的幾種位移和計算方式,以免遺忘和出現不知道都在講些神馬;
當我們key1和key2衝突的時候,主要有三種方式進行衝突解決;
先來說兩種開放定址法,所謂開放定址法就是重新計算了hash值;
1.線性探查法:
當我們插入key的位置,產生衝突之後,加1,檢視該位置是否可以使用。如果不可以使用,再次+1,重複到找到位置,或者查完沒有滿足的位置,並且在這個途中,可以越過尾部,從hash序列頭部進行列舉。
但是該方法有一個缺點,就是容易造成元素扎堆;
2.平方探查法:
插入時,當H(key)的位置被佔時,將檢查下列位置:H(key)+1^2,H(key)-1^2,H(key)+2^2,H(key)-2^2...。如果在這個途中H(key)+k^2超過了表長,則進行取模操作;如果H(key)-k^2<0時,則進行((H(key)-k^2)%Tsize+Tsize)%Tsize,從而保證索引為正;
這兩個方向的操作稱為正向和負向操作,為了避免計算麻煩,往往可以採用正向操作;注意一點,尋找的次數k在[0,Tsize]內,當k超過這個範圍,必不可能插入,停止計算;
第三中時拉鍊法則:
3.拉鍊法:
拉鍊法不計算新的hash值,而是在重複Hash值的地方構建一個單鏈表,從而將所有重複的節點連線起來,查詢的時候遍歷該連結串列中的所有元素;