A data structure that uses a hash function to map identifying values, known as keys, to their associated values
A hash map (or hash table) is a data structure which contains "key-value" pairs and allows retrieving values by key.
Hash maps (wikipedia) are part of the standard libraries for many languages:
- C++:
std::unordered_map - C# and other .Net languages:
Dictionary - Java:
HashMap,ConcurrentHashMap, and others (including the rather agedHashtable) - JavaScript: "Associative Array"
- Perl:
%{hash} - Python: "Dictionary"
It is a relatively common exercise in computer science courses to reimplement a hash table from first principles.
The most attractive feature is fast lookup of elements, particularly for large numbers of elements. Hash maps work by using a hash function to transform keys into a hash number that is then used as an index into an array of "buckets" containing one or more elements. This allows constant time access to the relevant bucket, followed by a linear search for the desired element within the bucket. When the number of elements in each bucket is kept low (possibly by dynamically resizing the array of buckets as elements are inserted) this offers constant time lookup on average even when the number of elements in the hash map increases. This can be a significant advantage compared to lookup in a tree-based structures which needs to perform more steps as the number of elements increases.
A drawback of hash tables is that elements are not stored in an obvious or meaningful order, as a good hash function will not map neighbouring keys to neighbouring buckets.
