data-structures - 閉じたハッシュ テーブルのスペース不足の線形衝突

Question

だから私は8バケットのハッシュテーブルを持っていますh(i) = i mod 8 これらは挿入されている数字です:

7, 11, 18, 28, 20, 8, 15, 23

ハッシュテーブルの学習を始めたばかりなので、これらの概念についてかなり混乱しています。

開いているハッシュ テーブルがある場合、結果は次のようになります。

0 | 8
1 |
2 | 18
3 | 11
4 | 28 20
5 |
6 |
7 | 7 15 23

閉じたハッシュを使用して線形衝突処理を実装する必要がある場合、

0 | 8
1 | 15 moved from 7
2 | 18
3 | 11
4 | 28 
5 | 20 moved from 4
6 | 23 moved from 7
7 | 7

私はこれを正しく行っていますか？

Answer 1

はい、これは正しいようです。実際には、ハッシュ テーブルにはしきい値の負荷係数があり、負荷係数を低く保つためにサイズ変更を実行するため、通常、線形プローブ テーブルが実証したレベルまでいっぱいになることはありません。