space 中封闭散列 table 运行 的线性冲突
Linear collision for closed hash table run out of space
所以我有一个 8 桶散列 table 和 h(i) = i mod 8
这些是正在插入的数字:
7, 11, 18, 28, 20, 8, 15, 23
我刚开始学习哈希 table 所以我对这些概念很困惑。
如果我有一个开放哈希 table,结果将是:
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
我这样做对吗?
是的,这看起来是正确的。请注意,实际上哈希 table 有一个阈值负载因子,在该阈值下它们将执行调整大小以保持较低的负载因子,因此通常您不会让线性探测 table 填满你所展示的水平。
所以我有一个 8 桶散列 table 和 h(i) = i mod 8
这些是正在插入的数字:
7, 11, 18, 28, 20, 8, 15, 23
我刚开始学习哈希 table 所以我对这些概念很困惑。
如果我有一个开放哈希 table,结果将是:
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
我这样做对吗?
是的,这看起来是正确的。请注意,实际上哈希 table 有一个阈值负载因子,在该阈值下它们将执行调整大小以保持较低的负载因子,因此通常您不会让线性探测 table 填满你所展示的水平。