> [!tldr] **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. The point of a hashing function is to resolve an arbitrary input to a particular, fixed-length, hopefully unique output deterministically. This is used to store (& look things up) in memory in your computer... but also can be used like a general [[Checksum]]. > [!note] [[Checksum]] usage > Rather than seeing if A = A we run A through a hashing function to get AHASH and we check that against the AHASH of the thing we want it to be the same as. If so, we can deduce with *reasonable* certainty (but not absolute) that A = A? And we do this because AHASH is, in practice, much smaller and easier to transmit and check against then actual A itself. > > One advantage hashing has is flagging transpositional errors, whereas simple checksums wouldn't care about what order things were sent in. 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]]