Editing Hash table (section)

{{Short description|Associative array for storing key-value pairs}}
{{Distinguish|Hash list|Hash tree (disambiguation){{!}}Hash tree}}
{{Redirect|Rehash|the ''South Park'' episode|Rehash (South Park)}}
{{Use mdy dates|date=January 2013}}
<!--THE UNDERSCORE "_" IS SIGNIFICANT, DO NOT CHANGE IT TO SPACE-->
{{Infobox data structure
|name=Hash table
|type=Unordered [[associative array]]
|invented_by=
|invented_year=1953
|space_avg=Θ(''n'')<ref name="Cormen et al">
  {{cite book
  |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen
  |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson
  |last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest
  |last4=Stein |first4=Clifford |author4-link=Clifford Stein
  | title = Introduction to Algorithms
  | edition = 3rd
  | publisher = Massachusetts Institute of Technology
  | year = 2009
  | isbn = 978-0-262-03384-8
  | pages = 253–280
  |title-link=Introduction to Algorithms }}
</ref>

|space_worst=O(''n'')
|search_avg=Θ(1)
|search_worst=O(''n''){{efn|1=There are approaches with a worst-case ''expected'' time complexity of O(log<sup>2</sup> (1 - ''α'')<sup>-1</sup>) where ''α'' is the load factor.<ref name="Farach-Colton 2024">{{cite conference |title=Optimal Bounds for Open Addressing Without Reordering |author1=Martin Farach-Colton |author2=Andrew Krapivin |author3=William Kuszmaul |conference=2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) |doi=10.1109/FOCS61266.2024.00045|arxiv=2501.02305 }}</ref><!-- see discussion of negative queries at the end of section 1 -->}}
|insert_avg=Θ(1)
|insert_worst=O(''n'')
|delete_avg=Θ(1)
|delete_worst=O(''n'')
}}
[[File:Hash table 3 1 1 0 1 0 0 SP.svg|thumb|315px|right|A small phone book as a hash table]]

In [[computer science]], a '''hash table''' is a [[data structure]] that implements an [[associative array]], also called a '''dictionary''' or simply '''map'''; an associative array is an [[abstract data type]] that maps [[Unique key|keys]] to [[Value (computer science)|values]].<ref name="ms">{{cite book |doi=10.1007/978-3-540-77978-0_4 |chapter=Hash Tables and Associative Arrays |title=Algorithms and Data Structures |first1=Kurt|last1=Mehlhorn |author1-link=Kurt Mehlhorn |first2=Peter |last2=Sanders |author2-link=Peter Sanders (computer scientist) |publisher=Springer |date=2008 |pages=81–98 |isbn=978-3-540-77977-3 |chapter-url=https://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf}}</ref> 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. A map implemented by a hash table is called a '''hash map'''.

Most hash table designs employ an [[Perfect hash function|imperfect hash function]]. [[Hash collision|Hash collisions]], where the hash function generates the same index for more than one key, therefore typically must be accommodated in some way.

In a well-dimensioned hash table, the average time complexity for each 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 pairs]], at [[amortized analysis|amortized]] constant average cost per operation.<ref name="leiser">{{cite web |first=Charles E. |last=Leiserson |author-link=Charles E. Leiserson |url=http://videolectures.net/mit6046jf05_leiserson_lec13/ |title=Lecture 13: Amortized Algorithms, Table Doubling, Potential Method |archive-url=https://web.archive.org/web/20090807022046/http://videolectures.net/mit6046jf05_leiserson_lec13/ |archive-date=August 7, 2009 |work=course MIT 6.046J/18.410J Introduction to Algorithms |date=Fall 2005 |url-status=live}}</ref><ref name="knuth">{{cite book | first=Donald |last=Knuth |author1-link=Donald Knuth | title = The Art of Computer Programming | volume = 3: ''Sorting and Searching'' | edition = 2nd | publisher = Addison-Wesley | year = 1998 | isbn = 978-0-201-89685-5 | pages = 513–558 }}</ref><ref name="cormen">{{cite book |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein | title = Introduction to Algorithms | publisher = MIT Press and McGraw-Hill | year= 2001 | isbn = 978-0-262-53196-2 | edition = 2nd | pages=[https://archive.org/details/introductiontoal00corm_691/page/n243 221]–252 | chapter = Chapter 11: Hash Tables |title-link=Introduction to Algorithms }}</ref>

Hashing is an example of a [[space-time tradeoff]]. If [[computer memory|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.{{r|algo1rob|p=458}}

In many situations, hash tables turn out to be on average more efficient than [[search tree]]s or any other [[table (computing)|table]] lookup structure. For this reason, they are widely used in many kinds of computer [[software]], particularly for [[associative array]]s, [[database index]]ing, [[cache (computing)|caches]], and [[set (abstract data type)|sets]].