CODEWITHSUNDEEP
hashtableocamlchaining
Sind
Sind

Reputation: 167

How to implement hash table with chaining?

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.

Upvotes: 6

Views: 2648

Answers (2)

J D
J D

Reputation: 48697

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?

You just resort to linear search of the bucket by key.

You may 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 f k = spine.[k.GetHashCode() % spine.Length]
    Seq.iter (fun (k, v) -> (f k).Add (k, v)) xs
    fun k -> Seq.pick (fun (k', v) -> if k=k' then Some v else None) (f k);;
val hashtbl : seq<'a * 'b> -> ('a -> 'b) when 'a : equality

This hashtbl function takes an association sequence xs of key-value pairs, builds a hash table represented as a spine array of ResizeArray buckets and returns a lambda function that finds the appropriate bucket and does a linear search in it for the given key k. The linear search is performed using the Seq.pick function.

Upvotes: 0

rlibby
rlibby

Reputation: 6021

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.

Upvotes: 4

Related Questions