Hashing is a crucial arrangement which is meant to use a special function called the Hash function which is employed to map a given value with a specific key for faster access of elements. The mapping’s efficiency depends of the efficiency of the hash function used.
It is a really useful concept that regularly comes up in System Design Interviews. you would possibly got to apply the concept while designing the backend of a system to alleviate bottlenecks . you’ll even be directly asked to style and implement a uniform Hashing.
The process of re-calculating the hashcode of already stored entries (Key-Value pairs) and to move these to another bigger size hashmap when the threshold is crossed/reached, is known as Rehashing
Rehashing of a hash map is completed when the amount of elements within the map reaches the utmost threshold value. Java specification suggests that the great ratio value is .75 and therefore the default initial capacity of HashMap is 16. Once the amount of elements reaches or crosses 0.75 times the capacity, the complexity increases, So to beat this the dimensions of the array is increased by double and every one the values are hashed again and stored within the new array of double size. this is often done to scale back the complexity and maintain low ratio . during this case, when the amount of elements is 12, rehashing occurs. (0.75 * 16 = 12).
Why Rehashing is required?
Rehashing is required because whenever a brand new key value pair is inserted into map, the load factor increases and because of which complexity also increases. And if complexity increases our hashMap won’t have constant O(1) time complexity. Hence rehashing is required to distribute the things across the hashmap as to reduce both load factor and complexity, So that the methods, get() and put() have constant time complexity of O(1). After rehashing is completed existing items may fall within the same bucket or different bucket.
Hashing is involved when our goal is to style a database storage system such that:
- We should be ready to distribute the incoming queries uniformly among the set of “n” database servers
- We should be ready to dynamically add or remove a database server
- When we add/remove a database server, we’d like to maneuver the minimal amount of knowledge between the servers To handle all above questions we need to understand the concepts of hashing in details. You need to learn and find the answers of following questions.
- What is hashing?
- What is hash table?
- How to build distributed hash tables?
- What is rehashing and why we need this?
- What is consistent hashing?
- What is hash ring? I have written a detailed article on each one of above concepts, you can find all details here on Hashing in datastructure
Top comments (0)