How to implement a hash table with a chain?

Question

This is probably a stupid question, but I can’t love God, to understand what I am missing here in theory behind hash tables with a chain.

Here is what I understand:

The hash table uses a hash to associate the key with the place where the value is stored. Sometimes a hash prints the same location for different keys, i.e. Collisions may occur.

In this case, we can implement the chain by storing all values ​​with the same location in a linked list in this place.

I do not understand what it is:

When you enter a key, and the hash function creates the location where the chain takes place, how does it determine what value in the linked list at this place belongs to this particular key, unlike the other key involved in the collision?

I understand that this is a basic theory, but if someone can point out errors in my reasoning or tell me what I am missing, I would really appreciate it.

Answer 1

Easy way: maintain a linked list of "hash table entries" that are key / value pairs. Once you get to the bucket, check the request key for all the keys in the bucket.

Answer 2

When you enter a key, and the hash function creates the location where the chain takes place, how does it determine what value in the linked list at this place belongs to this particular key, unlike the other key involved in the collision?

You simply resort to linear search of a bucket on a key.

You can appreciate the following mini-hash table implementation, written in F #, taken from this blog post :

> let hashtbl xs = let spine = [|for _ in xs -> ResizeArray()|] let fk = spine.[k.GetHashCode() % spine.Length] Seq.iter (fun (k, v) -> (fk).Add (k, v)) xs fun k -> Seq.pick (fun (k', v) -> if k=k' then Some v else None) (fk);; val hashtbl : seq<'a * 'b> -> ('a -> 'b) when 'a : equality 

This hashtbl function accepts a sequence of xs key-value associations, builds a hash table represented as a spine bucket in the ResizeArray bucket, and returns a lambda function that finds the corresponding bucket and performs a linear search on it for the given key k . Linear searches are performed using the Seq.pick function.