0
$\begingroup$

Here is an example problem which I have having trouble figuring out. The red text is the answer.

enter image description here

I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at index 3, 5 at index 1, etc.)

But when the table is resized, each element has a new position. HOW is 1's new index 0? HOW is 5's new index 7? How did each element of the array get assigned their new index upon table resize?

Any help would be appreciated.

Thanks

$\endgroup$

3 Answers 3

1
$\begingroup$

It is the hash function h(k) that determines the position. They don't specify the hash function, but instead they give the value to which h(k) evaluates for both tables.

The hash function is usually a 32bit or 64bit integer that gets trimmed to the size of the hash table. Say they were using crc32 as hash algorithm then h(k) for the old table will be h(k)=(crc32(k) mod 7) and for the new table h(k)=(crc32(k) mod 14).

So it is very unlikely that the same k will have the same position in each table.

When the hash table resize, you have to move the values from the old table to the new table while re-hashing their positions.

$\endgroup$
0
$\begingroup$

It's not explicitly defined - rather there's an implicit subindex (based off the table's size) to the hash-function. At the start we had e.g., $h(0) = h_7(0) = 3$. They are then informing you that $h_14(0) = 8$. There is no explained reason for this. They then re-insert the data to the larger hash table going over the old data in the order it appears in the hash table.

$\endgroup$
0
$\begingroup$

It says in red letter in the given answer: re-hash the values in the order they appear in the old table. It is analogous to the operation of a self-resizing array which has to copy over the old elements from the old array into the new (larger size) array.

When a hastable is resized (i.e. enlarged once it reaches its load factor limit) all the keys that exist in the hashtable are re-hashed. The positions of the values need to be placed in their rightful position in the new hashtable, so they have to be inserted with the new hash function so that they can be found accordingly.

The key values are hashed in the order they appear (from left to right) in the hashtable because this is essentially the only way to iterate through all the values of a hashtable (unless you are using an augmented hash table structure like the LinkedHashTable or something).

The upside to rehashing everything is that if the old hashtable had a large number of collisions, when the hashtable resizes to a larger size, many of the elements that collided would spread out now.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.