<programming, algorithm> (Or "hashing") A scheme for providing rapid
access to data items which are distinguished by some key. Each data item to be
stored is associated with a key, e.g. the name of a person. A hash function is
applied to the item's key and the resulting hash value is used as an index to
select one of a number of "hash buckets" in a hash table. The table contains
pointers to the original items.
If, when adding a new item, the hash table already has an entry at the indicated
location then that entry's key must be compared with the given key to see if it
is the same. If two items' keys hash to the same value (a "hash collision") then
some alternative location is used (e.g. the next free location cyclically
following the indicated one). For best performance, the table size and hash
function must be tailored to the number of entries and range of keys to be used.
The hash function usually depends on the table size so if the table needs to be
enlarged it must usually be completely rebuilt.
When you look up a name in the phone book (for example), you typically hash it
by extracting its first letter; the hash buckets are the alphabetically ordered
See also: btree, checksum, CRC, pseudorandom number, random, random number,
hash « hash bucket « hash character « hash coding
» hash collision » hash function » hashing