Editing Associative array (section)

=== Hash table implementations ===
{{main | Hash table}}
[[File:Hash table average insertion time.png|thumb|right|362px|This graph compares the average number of [[CPU cache]] misses required to look up elements in large hash tables (far exceeding size of the cache) with chaining and [[linear probing]]. Linear probing performs better due to better [[locality of reference]], though as the table gets full, its performance degrades drastically.]]
The most frequently used general-purpose implementation of an associative array is with a [[hash table]]: an [[Array data structure|array]] combined with a [[hash function]] that separates each key into a separate "bucket" of the array. The basic idea behind a hash table is that accessing an element of an array via its index is a simple, constant-time operation. Therefore, the average overhead of an operation for a hash table is only the computation of the key's hash, combined with accessing the corresponding bucket within the array. As such, hash tables usually perform in O(1) time, and usually outperform alternative implementations.

Hash tables must be able to handle [[hash collision|collisions]]: the mapping by the hash function of two different keys to the same bucket of the array. The two most widespread approaches to this problem are [[separate chaining]] and [[open addressing]].<ref name="gt"/><ref name="ms"/><ref name="clrs"/><ref name="fklm">{{citation|contribution=Pathfinders for associative maps|title=Ext. Abstracts GIS-l 2006|last1=Klammer|first1=F.|author1-link=F. Klammer|last2=Mazzolini|first2=L.|author2-link=L. Mazzolini|publisher=GIS-I|year=2006|pages=71–74}}.</ref> In separate chaining, the array does not store the value itself but stores a [[Pointer (computer programming)|pointer]] to another container, usually an [[association list]], that stores all the values matching the hash. By contrast, in open addressing, if a hash collision is found, the table seeks an empty spot in an array to store the value in a deterministic manner, usually by looking at the next immediate position in the array.

Open addressing has a lower [[cache miss]] ratio than separate chaining when the table is mostly empty. However, as the table becomes filled with more elements, open addressing's performance degrades exponentially. Additionally, separate chaining uses less memory in most cases, unless the entries are very small (less than four times the size of a pointer).