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:
“I know my fate. One day my name will be tied to the memory of something monstrous—a crisis without equal on earth, the most profound collision of conscience, a decision invoked against everything that had previously been believed, demanded, sanctified. I am no man, I am dynamite!”
—Friedrich Nietzsche (1844–1900)
“A great many will find fault in the resolution that the negro shall be free and equal, because our equal not every human being can be; but free every human being has a right to be. He can only be equal in his rights.”
—Mrs. Chalkstone, U.S. suffragist. As quoted in History of Woman Suffrage, vol. 2, ch. 16, by Elizabeth Cady Stanton, Susan B. Anthony, and Matilda Joslyn Gage (1882)