Collision Resolution
Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys. For example, if 2,500 keys are hashed into a million buckets, even with a perfectly uniform random distribution, according to the birthday problem there is a 95% chance of at least two of the keys being hashed to the same slot.
Therefore, most hash table implementations have some collision resolution strategy to handle such events. Some common strategies are described below. All these methods require that the keys (or pointers to them) be stored in the table, together with the associated values.
Read more about this topic: Hash Table
Famous quotes containing the words collision and/or resolution:
“When the wind carries a cry which is meaningful to human ears, it is simpler to believe the wind shares with us some part of the emotion of Being than that the mysteries of a hurricane’s rising murmur reduce to no more than the random collision of insensate molecules.”
—Norman Mailer (b. 1923)
“Unfortunately, many things have been omitted which should have been recorded in our journal; for though we made it a rule to set down all our experiences therein, yet such a resolution is very hard to keep, for the important experience rarely allows us to remember such obligations, and so indifferent things get recorded, while that is frequently neglected. It is not easy to write in a journal what interests us at any time, because to write it is not what interests us.”
—Henry David Thoreau (1817–1862)