Saturday, April 4, 2015

Int to Int hashMap using linear probing.

The key motivation of linear probing hash table is to make the number of entries at each bucket small and constant, such as one. Couple things are noticed in the following implementation:
1. linear probing using a hash function hash(key, step) to generate unique index at each step in order to probe the table.
2. the hash capacity has to set to a primer in order to loop through all possible slots in the table
3. the hash function use random function's nextInt(capacity) to get a random number between 0 and capacity -1.
4. during the steps of probing, the value at the index could be empty or deleted. To differentiate EMPTY slot and DELETED slot, two special flags are used, so this hash doesn't allow value equal to both EMPTY or DELETED.



The current implementation is still in draft stage and may have bugs.

No comments:

Post a Comment