-
Notifications
You must be signed in to change notification settings - Fork 0
HashMap Learning Text (English)
#HashMap
A HashMap maps a key to a value and stores this value pair in a hash table. The key is hashed and the hash code is used as an index to reference where the value is stored in the table. Also, key and value do not have to be of the same data type, e.g. the key can be of the data type string and the value of the data type integer.
Hashing is a cryptographic function, the so-called hash function, which works only in one direction. In our case, the value of the key is converted into a hash value by the mathematical SHA-1 function. The Hash value cannot be converted into the original value afterward. Hash values will always be the same length, no matter how big the value of the key was before. In addition, different values of the key should always result in a different Hashvalue and equal values to the same Hashvalue.
| HashMap | Hashtable |
|---|---|
| Not thread-safe | Thread-safe |
| Null values may be set as key and value | Null values may not be set as key and value |
The table of the HashMap cannot become completely full unless you change the load factor. Because the load factor indicates how full the table can become before the table is extended automatically. Then the hash table is hashed again, i.e. the internal data structure is formed anew. The rebuilding should approximately double the table.
When this happens there is a collision. The next thing to do is to resolve this collision. There are two different strategies for resolving Separate Chaining and Open Addressing
The collided objects are chained together using a linked list with Separate Chaining.
Open addressing refers to the procedure in which the collided values in the hash table are moved to free positions in the event of a collision. A distinction is made between linear probing, quadratic probing, and double hashing.
In a constant interval, the algorithm searches for a free position. By default, the interval size is 1.
The interval is squared after each unsuccessful search step.
Another hash function returns the interval.