Hashtables
What is a Hashtable?
Hashtables are a data structure that utilize key value pairs. This means every Node or Bucket has both a key, and a value. The basic idea of a hashtable is the ability to store the key into this data structure, and quickly retrieve the value. This is done through what we call a hash. A hash is the ability to encode the key that will eventually map to a specific location in the data structure that we can look at directly to retrieve the value.
Hash maps do this to store values:
accept a key calculate the hash of the key use modulus to convert the hash into an array index store the key with the value by appending both to the end of a linked list Hash maps do this to read value:
accept a key calculate the hash of the key use modulus to convert the hash into an array index use the array index to access the short LinkedList representing a bucket search through the bucket looking for a node with a key/value pair that matches the key you were given
Hashing is implemented in two steps:
An element is converted into an integer by using a hash function. This element can be used as an index to store the original element, which falls into the hash table. The element is stored in the hash table where it can be quickly retrieved using hashed key.
hash = hashfunc(key) index = hash % array_size
In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.
Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions are typically accommodated in some way.
In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key–value pairs, at (amortized[2]) constant average cost per operation.[3][4]
In many situations, hash tables turn out to be on average more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.