Simple Hash Table
A hash table (or hash map) is a data structure used to implement an associative array, a structure that can map keys to values. A hash table uses a hash function to compute the index into an array of buckets, or slots, from which the correct value can be found. This 'hashing' of the key makes a lookup very efficient and independent of the number of items in the hash table.
This implementation uses the djb2 hash function which provides a good distribution of hashed values (or indexes) to minimize collisions. A hash collision occurs when two different keys hash to the same value. If the collisions are not handled properly, the first value in the hash table will be overwritten by the second.
Hash collisions can be handled using one of several techniques. One way is to implement what is called separate chaining. With separate chaining, instead of assigning a single value to the index (or hash), some type of additional data structure is assigned, say a linked-list for example. Then the payload (key/value pair) is added to the data structure based on the data structure's native API. So basically, the hash table becomes an array of data structures--a data structure of data structures.
This project implements separate chaining to mitigate hash collisions.
Another method for resolving hash collisions is linear probing. Linear probing is not implemented in this project.
For specific examples and documentation, see the below sections
Although this implementation is designed to be used with
Node.js, it could be used in other contexts with minor
modifications. This implementation does not have any external dependencies
that would preclude it from being used in the browser--just include it with a
<script> tag and it should be good to go. Disclaimer: I have not tested
this implementation in any other context/environment; only tested with node.js
Install with npm :
npm install simple-hashtable --save
Available methods for a Hash Table instance:
Determines if the hash table is empty or not. Returns true if is empty, false otherwise.
Clears all entries in the hash table
Returns the number of keys in the hash table
### put(key, value)
Puts the value in the hash table and utilizes the key for lookup
Gets the value from the hash table that is associated with the key
Removes the value from the hash table that is associated with the key
Determines whether or not the hash table contains the key
Determines whether or not the hash table contains the value
Returns an array of all the keys in the hash table
Returns an array of all the values in the hash table
### setHashFn(fn) Sets the hash function for the hash table to fn
MIT © Jason Jones