What is hash table?

Hash Table

Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects like; in universities, every student is identified with a unique roll number that can be used to retrieve information about them. In this example, the students were hashed to a unique number.

Now, show you one another example. Suppose, you have multiple programming CDs and you want to assign them with particular numbers to make searching them easily. To store the number/value, you can use simply an array like a data structure where numbers can be used directly as an index to store values. However, in this case where the numbers are complex and cannot be used directly as an index, then you can use hashing to solve the difficulties. In hashing, complex numbers are converted into the simple format by using hash functions. The values are then stored in a data structure called hash table. By using that keys you can access the element and the algorithm of hash function computes an index that suggests where an entry can be found or inserted.

So, basically, Hash Table is a data structure where data stored in an associative manner, like an array format, where each data value has its own unique index value. Access to data becomes very fast if we know the index of the desired data.

The importance of a hash table

Hashing is an important Data Structure which is designed to use a special function called the Hash function. A hash table is used to store keys/value pairs. It uses a hash function to compute an index into an array in which an element will be inserted or searched. By using a good hash function, hashing can work well.

 

For instance, you have an object and you want to assign a key to it to make searching easy. To store the key/value pair, you can use a simple array like a data structure where keys (integers) can be used directly as an index to store values.

However, in cases where the keys are large and cannot be used directly as an index, you should use hashing. In hashing, large keys are converted into small keys by using hash functions.

The values are then stored in a data structure called the hash table.

The idea of hashing is to distribute entries (including key/value pairs) uniformly across an array. Each element is assigned a key (converted key). By using that key you can access the element in O(1) time. Using the key, the algorithm (hash function) computes an index that suggests where an entry can be found or inserted.

 

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. 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 a constant average cost per operation.

Hash function working process

• Search Operation - Whenever an element is to be searched, compute the hash code of the key passed and locate the element using that hashcode as an index in the array. Use linear probing to get the element ahead if the element is not found in the computed hash code.

• Insert Operation - Whenever an element is to be inserted, compute the hash code of the key passed and locate the index using that hashcode as an index in the array. Use linear probing for empty location, if an element is found at the computed hash code.

• Delete Operation - Whenever an element is to be deleted, compute the hash code of the key passed and locate the index using that hashcode as an index in the array. Use linear probing to get the element ahead if an element is not found in the computed hash code. When found, store a dummy item there to keep the performance of the hash table intact.

Techniques to construct a hash function

The folding method for constructing hash functions begins by dividing the item into equal-size pieces but the last piece may not be of equal size. These pieces are then added together to give the resulting hash value.

Another numerical technique for constructing a hash function is called the mid-square method. We first square the item and then extract some portion of the resulting digits.

Advantages of Hash Table

• Hash tables are used to quickly store and retrieve data or records.

• Records are stored in blocks using hash keys.

• Synchronization is the biggest advantage of Hashtable.

• The chosen value of a hashing algorithm is used to calculate Hash keys and the value must be a common value of all the records and each block can have multiple records which are organized in a particular order.

• In many situations, hash tables turn out to be 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.

• Hash tables over other table data structures are speedy. Because the hash tables are particularly efficient when the maximum number of entries can be predicted in advance so that the bucket array can be allocated once to the optimum size and never resized.

Disadvantages

• Hash tables can be more difficult to implement than self-balancing binary search trees.

• Hash collisions are practically unavoidable. when hashing a random subset of a large set.

• Hash tables become quite inefficient when there are many collisions.

• Hashtable does not allow null values, like the hash map.

• To processing applications, such as spell-checking, hash tables may be less efficient than trees, finite automata, or Judy arrays.

• If the keys are not stored, then there may be difficult to enumerate the keys that are present in the table at any given moment, because the hash function is collision-free.