A hash table is an associative data structure with an array/list to contain the data. It is often that this structure is of fixed size. Items are stored in the structure at particular locations, but this location is calculated from their value. Thus the key into the list is a hash of their value, derived with a specific algorithm (possibly seeded with some constant extra value).
The hashing algorithm is designed to allow for uniform coverage of all possible location indices.
Given there are fewer slots in the structure than there are possible values to store, there will be occasions where two items will have identicial keys, these are called collisions.
What to do in these cases? There are two approaches: linear probing and chaining.
(Well, strictly there's a third, to resize the array, but that's expensive and needs all keys to be recalculated.)
- Bond 1, pp285--298.
- Baeldung.com
- wikipedia
- wikibooks
See the shared document for some things to do.
NB there is a built-in Hashtable class, you should ignore this for now.
There is an IHashTable.cs file in this repo which you could choose to use as the basis for the work outlined in the document.