Data Structures and Algorithms/Hash Tables

A hash table is a data structure. A hash table has a corresponding hash function that it used to access the data in the hash table. Analogous to how you can access and array value if you know its key (i.e. array index), even hash tables have keys. These keys are passed to the hash function, which then returns the address of the corresponding value. The key to a hash table's performance lies in its hash function. Unlike arrays which always have only 1 value per key, hash values allow a many-to-one relation between keys and values, i.e. each key points to a bucket, which can store multiple values using data structures like linked lists. Hash tables can thus provide for nearly fixed average time for insertion, deletion and accessing data, even for large amounts of data.