Oh course, hashing uses duplicate keys, didn't think of that but again in reality the hash key is augmented by the data it is carrying with it.
That's only because there is a limited number of cells in the target array.
The way I always designed hash tables was:
used for call record processing at LCI International (which became QWest, which is now Century Link).
That's only because there is a limited number of cells in the target array.
The way I always designed hash tables was:
- 1st make sure the length of the hash table is a prime number. This only because it makes for very even distribution. This length was chosen to be close to the number of items you expected to be in the table at any given time.
- I didn't worry about using another cell in the table when a collision was encountered, what I did instead was to start a linked list moving laterally from the cell. Then you never had to reallocate the table itself, which is time consuming.
- On lookup, if a collision was encountered, it would start a search in the linked list but it would rarely go more than a few nodes before a match was found. This never caused a bottleneck as you would be inclined to think, because the prime number length of the table led to very even distribution (in a large table).
used for call record processing at LCI International (which became QWest, which is now Century Link).