Hash-Table Data Structure
A Hash-Table Data Structure is an associative array that uses a hash function to transform a key into the index (the hash) of an array element (the slot or bucket) where the corresponding value is to be sought.
- AKA: Hash Map.
- Context:
- It can (typically) support a fast Lookup Function.
- It can (often) be a Primitive Data Type in a Programming Language (a Hash Table Data Type).
- It can (typically) implement a Collision Resolution Technique to resolve Data Key Collisions.
- It can (typically) be a Sparse Data Structure.
- It can range from being a Local Hash Table to being a Distributed Hash Table.
- …
- Example(s):
- a Phone Book.
- a Perl Hash Data Structure (which recently switched to using the MurmurHash function).
- a Bloom Filter Data Structure (based on a bit vector and hash functions) for a Bloom filter.
- …
- Counter-Example(s):
- a Search Tree.
- See: Hash Algorithm, Bloom Filter Hash Table, Cache Data Structure.
References
2013
- (Wkipedia, 2013) ⇒ http://en.wikipedia.org/wiki/Hash_table
- In computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.
Ideally, the hash function will assign each key to a unique bucket, but this ideal situation is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are never added to the table after it is created). Instead, most hash table designs assume that hash collisions — different keys that are assigned by the hash function to the same bucket — will occur and must be accommodated in some way.
In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at (amortized[1]) constant average cost per operation.[2]
In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.
- In computing, a hash table (also hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found.
- ↑ Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms — Fall 2005
- ↑ Donald Knuth (1998). 'The Art of Computer Programming'. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 0-201-89685-0.
2013b
- (Wikibooks, 2013) ⇒ http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables
- A hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person's name), find the corresponding value (e.g. that person's telephone number). It works by transforming the key using a hash function into a hash, a number that the hash table uses to locate the desired value.