Human above all, with pathos, weaknesses and grumpy at times. Speak for myself; think out loud. Direct, seemingly hard faced. Urged to fix things. Am fortunate.
qnoid

# How To Think Of... A Hash Table (part 2)

Start at the beginning with Part 1

Let’s take a step back for a minute and take a look at the array.

``````[0, 1, 2]
``````

Imagine that each value in the array represents a “bucket”. That is a collection of values (rather than a single one). So each time you put a value in that bucket, it grows.

`````` 9
6	7
3	4  5
0  1  2
^  ^  ^
[0, 1, 2] //bucket index
``````

Rotating the view 90 degrees to the right will reveal that each bucket really is just an array

``````0 > [0, 3, 6, 9]
1 > [1, 4, 7]
2 > [2, 5]
``````

This will allow us to store more than one value under the same index. Notice how 0 and 3 are both under index 0. Calculating the index of the bucket is not enough any more when querying for the value since there is the possibility of getting more than one.

That is why we need a class to hold the value as well as the actual key associated with it.

Having a reference to the next value in the bucket will allow us to grow and iterate the array without the overhead of maintaining it.

So given the index and the key, we find the bucket and then iterate until we match the key to get the value. Remember that each key is really unique.

In that sense in every put as well as creating a new Value with the key and value we need to assign the current one as the next in the list.

That all works great but our hash table is of fixed and very small length. We need to deal with the fact that our buckets will grow longer and longer in time.