Menu
From the book CLRS ("Introduction to Algorithms"), there are several hashing functions, such as mod, multiply, etc.
What hashing function does Java use to map the keys to slots?
I have seen there is a question here Hashing function used in Java Language. But it doesn't answer the question, and I think the marked answer for that question is wrong. It says that hashCode() let you do your own hashing function for Hashtable, but I think it is wrong.
The integer returned by hashCode() is the real key for Hashtble, then Hashtable uses a hashing function to hash the hashCode(). What this answer implies is that Java give you a chance to give Hashtable a hashing function, but no, it is wrong. hashCode() gives the real key, not the hashing function.
So what exactly the hashing function does Java use?
225
Like HashMap, Hashtable stores key/value pairs in a hash table. When using a Hashtable, you specify an object that is used as a key, and the value that you want linked to that key. The key is then hashed, and the resulting hash code is used as the index at which the value is stored within the table.
The Hashtable class implements a hash table, which maps keys to values. Any non-null object can be used as a key or as a value. To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method. It is similar to HashMap, but is synchronized.
In Java, one of the most basic computer science concepts is “hashing”. Java's hashCode() function does the hashing for us. By employing hashing techniques, it is possible to map data to a representational integer value.
Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from.
When a key is added to or requested from a HashMap in OpenJDK, the flow of execution is the following:
hashCode() method.If the hash table size was chosen appropriately high, the number of collisions will be limited. Thus, a single lookup takes only constant time on average. This is called expected constant time. However, if an attacker has control over the keys inserted into a hash table and knowledge of the hash algorithm in use, he can provoke a lot of hash collisions and therefore force linear lookup time. This is why some hash table implementations have been changed recently to include a random element that makes it harder for an attacker to predict which keys will cause collisions.
key.hashCode() | | 32-bit value | hash table V +------------+ +----------------------+ HashMap.hash() --+ | reference | -> | key1 | value1 | null | | |------------| +----------------------+ | modulo size | null | | = offset |------------| +---------------------+ +--------------> | reference | -> | key2 | value2 | ref | |------------| +---------------------+ | .... | | +----------------+ V +----------------------+ | key3 | value3 | null | +----------------------+ If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
