Descriptions
Hash functions are mostly used to accelerate table lookup or data comparison tasks such as finding items in a database, detecting duplicated or similar records in a large file, finding similar stretches in DNA sequences, and so on.
A hash function should be referentially transparent (stable), i.e., if called twice on input that is "equal" (for example, strings that consist of the same sequence of characters), it should give the same result. This is a contract in many programming languages that allow the user to override equality and hash functions for an object: if two objects are equal, their hash codes must be the same. This is crucial to finding an element in a hash table quickly, because two of the same element would both hash to the same slot.
Some hash functions may map two or more keys to the same hash value, causing a collision. Such hash functions try to map the keys to the hash values as evenly as possible because collisions become more frequent as hash tables fill up. Thus, single-digit hash values are frequently restricted to 80% of the size of the table. Depending on the algorithm used, other properties may be required as well, such as double hashing and linear probing. Although the idea was conceived in the 1950s, the design of good hash functions is still a topic of active research.
Hash functions are related to (and often confused with) checksums, check digits, fingerprints, randomization functions, error correcting codes, and cryptographic hash functions. Although these concepts overlap to some extent, each has its own uses and requirements and is designed and optimized differently. The HashKeeper database maintained by the American National Drug Intelligence Center, for instance, is more aptly described as a catalog of file fingerprints than of hash values.
Read more about this topic: Hash Function
Famous quotes containing the word descriptions:
“Our Lamaze instructor . . . assured our class . . . that our cervix muscles would become “naturally numb” as they swelled and stretched, and deep breathing would turn the final explosions of pain into “manageable discomfort.” This descriptions turned out to be as accurate as, say a steward advising passengers aboard the Titanic to prepare for a brisk but bracing swim.”
—Mary Kay Blakely (20th century)
“The fundamental laws of physics do not describe true facts about reality. Rendered as descriptions of facts, they are false; amended to be true, they lose their explanatory force.”
—Nancy Cartwright (b. 1945)
“Matter-of-fact descriptions make the improbable seem real.”
—Mason Cooley (b. 1927)