Private addressing hash tables. How do they change?
Reading about hopscotch hashing and trying to figure out how the code might be, I realized that in the linear probing hash table variants, we need to have a recursive approach to resizing like this:
-
create a backup array of existing buckets
-
allocate a new array of requested capacity
- go through the backing array and rephrase each element to get the new position of the element in the new array and insert it into the new array
- on completion of backup array creation
And the structure of the code will look like this:
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);
}
}
I don't like this structure as we recursively call put in resize.
Is this the standard approach to resizing a hash table when using linear probing options.
source to share
Good question! Typically in hashing with a private address like hash hash, cuckoo hashing, or static perfect hashing, where there is a chance the rename might fail, one "paraphrase" step might have to sit in a loop trying to assign everything to a new table while won't find a way to do it that works.
You might want to consider three methods put
, an external visible function, an rehash
internal function, and tryPut
which tries to add an element but may fail. Then you can implement functions like this, which are mainly for presentation and can be optimized a bit:
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.
}
There is no more risk of strange recursion here because it tryPut
never calls anything else.
Hope this helps!
source to share