封闭寻址哈希表。它们是如何调整大小的?
Closed addressing hash tables. How are they resized?
阅读 hopscotch hashing 并试图理解它是如何编码的,我意识到在线性探测哈希 table 变体中,我们需要使用递归方法来调整大小,如下所示:
创建现有存储桶的备份数组
分配请求容量的新数组
- 遍历备份数组并重新散列每个元素以获得
元素在新数组中的新位置并将其插入到
新数组
- 完成后释放备份阵列
代码结构如下:
public V put(Object key, Object value) {
//code
//we need to resize)
if(condition){
resize(2*keys.length);
return put(key, value);
}
//other code
}
private void resize(int newCapacity) {
//step 1
//step 2
//go over each element
for(Object key:oldKeys) {
put(key, value);
}
}
我不喜欢这种结构,因为我们递归调用 put inside resize。
这是使用线性探测变体
时调整散列大小的标准方法 table
好问题!通常,在像跳房子哈希、布谷鸟哈希或静态完美哈希这样的封闭地址哈希中,重新哈希有可能失败,单个 "rehash" 步骤可能必须处于一个循环中,试图将所有内容分配到一个新的 table 直到找到可行的方法。
您可能需要考虑使用三种方法 - put
,外部可见函数,rehash
,内部函数,以及 tryPut
,它试图添加一个元素,但是可能会失败。然后你可以实现这样的功能,这些功能主要是为了展示,绝对可以优化一下:
public V put(Object key, Object value) {
V oldValue = get(key);
while (!tryPut(key, value)) {
rehash();
}
return oldValue;
}
private void rehash() {
increaseCapacity();
boolean success;
do {
success = true;
reallocateSpace();
for (each old key/value pair) {
if (!tryPut(key, value)) {
success = false;
break;
}
}
} while (!success);
}
private boolean tryPut(Object key, Object value) {
// Try adding the key/value pair using a
// hashtable specific implementation, returning
// true if it works and false otherwise.
}
这里不再有任何奇怪递归的风险,因为tryPut
从不调用任何其他东西。
希望对您有所帮助!
阅读 hopscotch hashing 并试图理解它是如何编码的,我意识到在线性探测哈希 table 变体中,我们需要使用递归方法来调整大小,如下所示:
创建现有存储桶的备份数组
分配请求容量的新数组
- 遍历备份数组并重新散列每个元素以获得 元素在新数组中的新位置并将其插入到 新数组
- 完成后释放备份阵列
代码结构如下:
public V put(Object key, Object value) {
//code
//we need to resize)
if(condition){
resize(2*keys.length);
return put(key, value);
}
//other code
}
private void resize(int newCapacity) {
//step 1
//step 2
//go over each element
for(Object key:oldKeys) {
put(key, value);
}
}
我不喜欢这种结构,因为我们递归调用 put inside resize。
这是使用线性探测变体
好问题!通常,在像跳房子哈希、布谷鸟哈希或静态完美哈希这样的封闭地址哈希中,重新哈希有可能失败,单个 "rehash" 步骤可能必须处于一个循环中,试图将所有内容分配到一个新的 table 直到找到可行的方法。
您可能需要考虑使用三种方法 - put
,外部可见函数,rehash
,内部函数,以及 tryPut
,它试图添加一个元素,但是可能会失败。然后你可以实现这样的功能,这些功能主要是为了展示,绝对可以优化一下:
public V put(Object key, Object value) {
V oldValue = get(key);
while (!tryPut(key, value)) {
rehash();
}
return oldValue;
}
private void rehash() {
increaseCapacity();
boolean success;
do {
success = true;
reallocateSpace();
for (each old key/value pair) {
if (!tryPut(key, value)) {
success = false;
break;
}
}
} while (!success);
}
private boolean tryPut(Object key, Object value) {
// Try adding the key/value pair using a
// hashtable specific implementation, returning
// true if it works and false otherwise.
}
这里不再有任何奇怪递归的风险,因为tryPut
从不调用任何其他东西。
希望对您有所帮助!