Hash function

HASH TABLES

Progamming Methods

Jorge Barbosa

Hash tables
• Hash table or hash map is a data structure that uses a hash function to efficiently map certain identifiers or keys (e.g., personnames) to associated values (e.g., their telephone numbers). The hash function is used to transform the key into the index (the hash) of an array element (the slot or bucket) where the correspondingvalue is to be sought.

•

Hash tables
• Ideally the hash function should map each possible key to a different slot index, but this ideal is rarely achievable in practice (unless the hash keysare fixed; i.e. new entries are never added to the table after creation). Most hash table designs assume that hash collisions — pairs of different keys with the same hash values — are normaloccurrences and must be accommodated in some way.

•

Advantages
• Speed
– Hash tables are particularly efficient when the maximum number of entries can be predicted in advance, so that the bucket arraycan be allocated once with the optimum size and never resized.

• If the set of key-value pairs is fixed and known ahead of time (so insertions and deletions are not allowed), one may reduce theaverage lookup cost by a careful choice of the hash function, bucket table size, and internal data structures.

Uses
• Associative arrays
– Hash tables are commonly used to implement many types ofinmemory tables.

• Database indexing
– Hash tables may also be used for disk-based persistent data structures and database indices although balanced trees are more popular in these applications.• Caches
– Hash tables can be used to implement caches, auxiliary data tables that are used to speed up the access to data that is primarily stored in slower media.

Uses
• Sets
– Besidesrecovering the entry which has a given key, many hash table implementations can also tell whether such an entry exists or not.

• Object representation
– Several dynamic languages, such as Python,...