Changes

A '''hash table''' is a data structure that implements the map abstract data type. Given a piece of data known as a ''key'', a map may be used to look up a corresponding piece of data called the ''value''. This functionality is implemented by computing a ''hash function'' on a key to obtain an index in an [[array]] where the value may be stored. The value of the hash function on a key is completely determined by the identity of the key, so the hash function is a function in the mathematical sense where each key has one hash value. The motivation for using a hash table instead of a balanced binary search tree as map is that the average time complexity of looking up the value of a key is constant whereas the time complexity of a search in a tree is logarithmic with respect to the size of the tree.

A '''hash table''' is a [[data structure]] that implements the map abstract data type. Given a piece of data known as a ''key'', a map may be used to look up a corresponding piece of data called the ''value''. This functionality is implemented by computing a ''hash function'' on a key to obtain an index in an [[array]] where the value may be stored. The value of the hash function on a key is completely determined by the identity of the key, so the hash function is a function in the mathematical sense where each key has one hash value. The motivation for using a hash table instead of a balanced binary search tree as map is that the average time complexity of looking up the value of a key is constant whereas the time complexity of a search in a tree is logarithmic with respect to the size of the tree.

==Example==

==Example==

<pre>

<pre>