理解自：鄧俊輝老師 《數(shù)據(jù)結(jié)構(gòu)：散列》 -以蟬為師
我們假設(shè)有兩個散列hash_a和hash_b,表a的長度M = 7,表b的長度M = 8。假設(shè)我們從1的位置開始，步長為2的產(chǎn)生數(shù)據(jù)。
那么產(chǎn)生的數(shù)據(jù)即為1,3,5,7,9,11···
我們將他們映射到表a和表b中，假設(shè)數(shù)據(jù)就到1000
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 72 | 71 | 72 | 71 | 72 | 72 | 72 |
我們可以看到足跡是遍歷了整個表。
換到表2。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 0 | 125 | 0 | 125 | 0 | 125 | 0 | 125 |
非常明顯的看到堆積問題。
這是為什么呢？原因非常簡單，因為當(dāng)任意步長為表長的因子時，總會出發(fā)回到原點（循環(huán)），導(dǎo)致堆積。
假設(shè)表長M和步長S有則必然(i + nS)%M =( i%M + nS%M)%M = (i + nk)%M（大概是吧，因為還沒學(xué)數(shù)論這里大概推導(dǎo)了一下）
解決的辦法就是讓GCD表示最大公約數(shù)，S為任意步長，M為表長。那么很明顯M必須為素數(shù)。
那么應(yīng)用到自然科學(xué)中，蟬的壽命在11和17這兩個素數(shù)，假設(shè)蟬的天敵壽命為M，則蟬必然換代的年份平均分布在這個hash表（天敵的壽命）中。 如果為合數(shù)，則容易發(fā)生蟬的數(shù)量的堆積，被天敵吃完。
