Hash Tables cont.

So how is a hash table implemented? We could use an array for quick insert, deletion, and lookup, but it will take up a lot of space. On the other hand, we could use a linked list. This would only take up as much as space as there are objects, but the 3 operations would not be O(1). To resolve this, we can use both.

The first way to implement a hash table could be to use an array of linked lists. We use a hash function to determine which index the object goes into. If there is already something in that index, this is called a "collision." To resolve this, we just make a chain at that index of the array.

The "Birthday Paradox" states that given 23 people, there is a 50% chance that two people will share the same birthday. By this principle, we can see that it doesn't take relatively many objects to cause a collision.

The second way to implement a hash table would be to use open addressing. When there is a collision, simply put it elsewhere. This could be the next available index, which is called linear probing. Or, you could use another hash table to determine the offset. Implementing deletion in this method is much trickier.