What is a Hash Table?
Data stucture that stores elements in key-value pairs where
- Key - unique integer (or property name is Javascript objects) that is used for indexing the values
- Value - data that is associated with the key
- Bucket - array cell/slot where nodes of key-value pairs are stored
For fast data store and retrieval
- In a linear search (ie. linked lists) and binary search (ie. BST), data lookups/search has a time complexity of O(n) and O(log n). For large datasets, these complexities can become significantly high
- Hashing allows lookups to occur in constant time (O(1))
Actions and their time complexity
insert ⇒ O(1)
- dependant on hash function (but it is assumed that most programming languages uses a hash function that is O(1))
lookup (finding a value based on a key) ⇒ O(1)
- same as insert. given property name will be hashed and direct exactly to the address to find values
- however, depends on whether there are any collisions
delete ⇒ O(1)
- same thing because we use the key
- also, hash tables are unordered, we don’t have to shift indexes like we would with arrays
search (check if certain key exists) ⇒ O(1)
Hash functions (해시 함수)
A hash function is used for mapping each element of a dataset to indexes in the table. The function generates a value of fixed length for each input that it gets. There are many types of hash functions (ie. md5, SHA-1, SHA-256, etc.) and we can assume that the hash functions in our programming languages use a type that has a time complexity of O(1).
A hash function for a hash table will generate a hash output, which is then used as an index in the hash table and an index space (or an address space) is alloted for that index.
Some key aspects of hash functions:
- One-way function (일방적) - it’s practically impossible to get what the input would be by the output (the key value cannot be retrieved from the hash)