-
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. By a mathematical function e.g. like in our case the value of the key is converted into a hash value. This cannot be converted back afterwards. The hash value has always the same length, no matter how big the value of the key was before. In addition, with different values of the key also always a different Hashwert should come out and with same values a same Hashwert.
| 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 loadfactor. Because the loadfactor 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
With Separate Chaining, the collided objects are chained together using a linked list.
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.
Here a constant interval is searched for a free position. Mostly one takes for the interval size 1.
The interval is squared after each unsuccessful search step.
Another hash function returns the interval.