hash coding

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 letter sections.

See also: btree, checksum, CRC, pseudorandom number,

random, random number, soundex.

(1997-08-03)