**A data structure enabling very fast retrieval of data by loading values into slots based on a hash function - "Maps" in [[JavaScript]] are Hash Tables** Hash Tables are data structures holding values in an array in a position according to their value (or key, etc) calculates through a hashing function. This allows you to look up values from the hashing table in constant time - you don't have to look index-by-index to find the element you're searching for. You can apply the a hashing function then go look there. > [!tip] Hash Tables are also called Dictionaries or, Hash Maps, or Associative Arrays ## Hashing Function A hashing function takes any sort of input and uses it to [[Deterministic]]ally build a *location* or *index* for a where that input would go into a list. You could, in theory, build a hashing function that looked at a book's title and determined where it would likely be sorted in a list of 10 millions alphabetically-sorted books. It could have weights and expect a book titled "AAAAAAAAAA" to be the 0th book, and a book starting with "M" to be near the 5 millionth place. **Note: in practice Hashing Functions don't try to preserve order.**. The Hash Function does not *sort*, it tries to *spread out* inputs over the available space of outputs in a repeatable way. There is no such thing as a universal perfect hashing function. Hashing collisions occur when two separate values to store result in the same hashing function output. This causes the 2nd value to have to find a new location to live in accordance with some sort of collision handling strategy. ![[Pasted image 20250629192321.png]] **** # More ## Source - [[Wikipedia]] ## Related - [[Types of Non-relational Databases]] - [[Data Topics]] - [[Relational Databases]]