0

I'm working through some old exam papers and came across the following:

Demonstrate how a closed address hashing algorithm works using the data set {4, 2, 12, 3, 9, 11, 7, 8, 13, 18} as an input example.

Assume the lenght of the array is initially 7. You should demonstrate:

i. how the hash table is built, step-by-step ii. how a search on a hash table can be acheived in O(1) time.

Now, given that the array is initially set to 7, the largest hash function I can use is n mod 7, as there are are more elements to be inserted than the size of the array, the array must be resized.

I am assuming that the hash function remains the same after resizing?

Regarding the second part, how can O(1) search be achieved if many elements hash to the same value? Surely, I need to sequentially through clustered elements in the array?

Is this hypothesis correct?

4

1 回答 1

3

after resizing your hashtable. you should do an "expensive" rehashing. That is, you have to rehashing existing keys, to allocate them new slots. Your hash function then would be id mod newSize.

good implementation won't do resize/rehashing when the hashtable is full. there is a load factor, performance of open addressing/linear probing approach would be dramatically getting down when load factor higher than 0.75 (or 0.8? don't remember exactly) Therefore, when load factor reaches a limit (0.75 e.g.) resizing/rehashing will be executed.

the hashfunction cost constant time, so getting element costs constant time too.

于 2013-05-07T14:49:04.983 回答