Hash tables Page
Hash Table
Return to Data Structures
In computing, a hash table, also called hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to value (Unique key to Value (computer science))((Hash Tables and Associative Arrays, in book Algorithms and Data Structures: The Basic Toolbox, Kurt Mehlhorn and wp>Peter Sanders (computer scientist), Springer, 2008, pages 81–98, https://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf))
A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.
Ideally, the hashing function will assign each key to a unique bucket, but most ddg>hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions are typically accommodated in some way.
In a well-dimensioned hash table, the average time complexity for each hash lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of name–value pair (key–value pair, at amortized (amortized analysis) constant average cost per operation.((wp>Charles E. Leiserson, https://videolectures.net/mit6046jf05_leiserson_lec13 Amortized Algorithms, Table Doubling, Potential Method, https://web.archive.org/web/20090807022046/http://videolectures.net/mit6046jf05_leiserson_lec13, August 7, 2009, Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms—Fall 2005)) ((Donald Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching 2nd edition, Addison-Wesley, 1998, isbn>978-0-201-89685-5, pages 513–558)) ((Thomas Cormen]], Introduction to Algorithms, MIT Press and McGraw-Hill, 2001, isbn>978-0-262-53196-2, Pages 221–252 https://archive.org/details/introductiontoal00corm_691/page/n243, Chapter 11: Hash Tables))
Hashing is an example of a space-time tradeoff. If computer memory is infinite, the entire key can be used directly as an index to locate its value with a single memory access. On the other hand, if infinite time is available, values can be stored without regard for their keys, and a binary search or linear search can be used to retrieve the element.
In many situations, hash tables turn out to be on average more efficient than search trees or any other table (computing) lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, cache (computing) | caches, and sets (set (abstract data type).
wp>Hash table
{{navbar_footer}}