Editing Hash function (section)

== Hash tables ==
{{main|Hash table}}

Hash functions are used in conjunction with [[hash tables]] to store and retrieve data items or data records. The hash function translates the key associated with each datum or record into a hash code, which is used to index the hash table. When an item is to be added to the table, the hash code may index an empty slot (also called a bucket), in which case the item is added to the table there.  If the hash code indexes a full slot, then some kind of collision resolution is required: the new item may be omitted (not added to the table), or replace the old item, or be added to the table in some other location by a specified procedure.  That procedure depends on the structure of the hash table.  In ''chained hashing'', each slot is the head of a linked list or chain, and items that collide at the slot are added to the chain.  Chains may be kept in random order and searched linearly, or in serial order, or as a self-ordering list by frequency to speed up access.  In ''open address hashing'', the table is probed starting from the occupied slot in a specified manner, usually by [[linear probing]], [[quadratic probing]], or [[double hashing]] until an open slot is located or the entire table is probed (overflow).  Searching for the item follows the same procedure until the item is located, an open slot is found, or the entire table has been searched (item not in table).

=== Specialized uses ===
Hash functions are also used to build [[cache (computing)|caches]] for large data sets stored in slow media. A cache is generally simpler than a hashed search table, since any collision can be resolved by discarding or writing back the older of the two colliding items.<ref>{{Cite web|last=Stokes|first=Jon|date=2002-07-08|title=Understanding CPU caching and performance|url=https://arstechnica.com/gadgets/reviews/2002/07/caching.ars|access-date=2022-02-06|website=Ars Technica|language=en-us}}</ref>

Hash functions are an essential ingredient of the [[Bloom filter]], a space-efficient [[Probability|probabilistic]] [[data structure]] that is used to test whether an [[element (mathematics)|element]] is a member of a [[set (computer science)|set]].

A special case of hashing  is known as [[geometric hashing]] or the ''grid method''. In these applications, the set of all inputs is some sort of [[metric space]], and the hashing function can be interpreted as a [[partition (mathematics)|partition]] of that space into a grid of ''cells''. The table is often an array with two or more indices (called a ''[[grid file]]'', ''grid index'', ''bucket grid'', and similar names), and the hash function returns an index [[tuple]].  This principle is widely used in [[computer graphics]], [[computational geometry]], and many other disciplines, to solve many [[proximity problem]]s in the [[Plane (geometry)|plane]] or in [[three-dimensional space]], such as finding [[closest pair problem|closest pairs]] in a set of points, similar shapes in a list of shapes, similar [[image processing|images]] in an [[image retrieval|image database]], and so on.

Hash tables are also used to implement [[associative array]]s and [[set (abstract data type)|dynamic sets]].<ref name="handbook_of_applied_cryptography">{{cite book|title=Handbook of Applied Cryptography|first1=Alfred J.|last1=Menezes|first2=Paul C.|last2=van Oorschot|first3=Scott A|last3=Vanstone|year=1996|publisher=CRC Press|isbn=978-0849385230|url-access=registration|url=https://archive.org/details/handbookofapplie0000mene}}</ref>