Menu
This is probably a stupid question but, I cant for the love of god figure out what I'm missing here in the theory behind hash tables with chaining.
This is what I understand:
A hash table uses a hash to associate a key to a location where a value is stored. Sometimes a hash will produce the same location for different keys, ie collisions may occur.
In this case we can implement chaining by storing all values with the same location to a linked list at that location.
What I don't understand is this:
When you enter a key and the hash function produces a location at which there is chaining, how does it determine which value in the linked list at that location belongs to that specific key, as opposed to another key involved in the collision?
I realize this is basic theory, but if anyone could point out errors in my reasoning or tell me what I'm missing I would very much appreciate it.
369
Chaining is a technique used for avoiding collisions in hash tables. A collision occurs when two keys are hashed to the same index in a hash table. Collisions are a problem because every slot in a hash table is supposed to store a single element.
It is usually implemented using linked lists. In separate chaining, each element of the hash table is a linked list. To store an element in the hash table you must insert it into a specific linked list.
Hash Table chaining in Java is possible with both, Singly Linked List and Doubly Linked List. Though the implementation is same, the only difference is that Doubly Linked List allows two-way traversal i.e., the node contains a pointer to the next as well as the previous node.
To handle collisions, the hash table has a technique known as separate chaining. Separate chaining is defined as a method by which linked lists of values are built in association with each location within the hash table when a collision occurs. The figure shows incidences of collisions in different table locations.
Separate Chaining is one of the techniques that is used to resolve the collision. It is implemented using linked lists. This method combines a linked list with a hash table in order to resolve the collision. In this method, we put all the elements that hash to the same slot in the linked list.
Simple way: maintain a linked list of "hash table entries", which are key/value pairs. Once you get to the bucket, check your query key against all keys in the bucket.
89
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
