advanced-js-reading-notes
Hash-Table
What is a Hashtable?
Hash - A hash is the result of some algorithm taking an incoming string and converting it into a value that could be used for either security or some other purpose. In the case of a hashtable, it is used to determine the index of the array.
Buckets - A bucket is what is contained in each index of the array of the hashtable. Each index is a bucket. An index could potentially contain multiple key/value pairs if a collision occurs.
Collisions - A collision is what happens when more than one key gets hashed to the same location of the hashtable.
A collision occurs when more than one key hashes to the same index in an array. As mentioned earlier, a “perfect hash” will never have any collisions. To put this into perspective, the worst possible hash is one that hashes every single key to the same exact index of an array. The more keys you have hashed to a specific index, the more key/value pair combos you can potentially have.
Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects.
Hash function A hash function is any function that can be used to map a data set of an arbitrary size to a data set of a fixed size, which falls into the hash table. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes.
To achieve a good hashing mechanism, It is important to have a good hash function with the following basic requirements:
-
Easy to compute: It should be easy to compute and must not become an algorithm in itself.
-
Uniform distribution: It should provide a uniform distribution across the hash table and should not result in clustering.
-
Less collisions: Collisions occur when pairs of elements are mapped to the same hash value. These should be avoided.
-
Note: Irrespective of how good a hash function is, collisions are bound to occur. Therefore, to maintain the performance of a hash table, it is important to manage collisions through various collision resolution techniques.
Applications Associative arrays: Hash tables are commonly used to implement many types of in-memory tables.