HashMap works on the principle of
Hashing. Hashing is a principle used to store and retrieve data in constant
O(1) time. Before going to discuss about HashMap working, I want to explain
some basics of Hashing, Hash table, collisions etc.,
Hash Table
Hash table is a data structure used to
store collection of items in a way that it is easy to find them in later.
Usually you can store and search data of Hash table in constant (O(1)) time.
For example, consider following hash
table of size 13 (Technically each position of hash table is called slot, so it
has 13 slots). Initially hash table is empty. Let us try to insert some data
into hash table based on some hash function.
What is Hash function?
Hash function is used to map an item to
a slot (position) in Hash table. Hash function takes an item as input and
returns a slot in range between 0 and hash table size (exclusive).
To demonstrate example, I am going to
use following hash function.
h(item)=item%13
Item
|
Hash
Value
|
103
|
12
|
65
|
0
|
35
|
9
|
19
|
6
|
23
|
10
|
76
|
11
|
Based on the Hash value computed, all
the items are placed in respective slots . Element 103 is placed in slot 12,
Element 65 is placed in slot 0 etc.,
There is a problem in above approach.
Suppose you want to insert an element 26 in Hash table, 26 % 13 = 0, 26 has to
be placed in slot 0, but slot 0 is already occupied with element 65. Here the
concept of collision comes into picture. I will explain more about this later
in the post.
Load Factor
Load factor is denoted by λ, λ = (Number
Of Items)/(Hash table size). In our example λ = 6/13 = 0.46153846153846156.
How to search for an element in Hash Table?
We can use the same hash function to
search for an element in Hash table. Suppose you want to search for an element
23.
a. Apply hash function on element 23, to
find the slot. 23 % 13 = 10
b. Go to slot 10 and check whether element
23 exist or not.
What is Perfect Hash function?
Perfect Hash function maps each element
to a unique slot. Ideally there is no systematic way to construct a perfect
hash function. Usually depends on the load factor, hash table is resized to
reduce the collisions.
Collision Resolution
Collision occurs when two items mapped
to same slot. Collision resolution techniques play an important role in hashing.
One way to address the problem of collisions is linear probing.
Linear
Probing
In linear probing technique, we try to
find next open slot in hash table sequentially. For example, hash table is already
occupied with elements 103, 65, 35, 19, 23, 76.
When we try to place element 26 (slot =
26 % 13 = 0) in hash table, collision occurs. We try to find next open slot
from the position 0 and place the element 26 in it. Next open position after
slot 0 is 1, so we place the element 26 in slot 1.
Suppose you want to insert element 48
into hash table, Find the slot for the element 48 (slot = 48 % 13 = 9). Since
slot 9 is already occupied with element 35, we need to find next open slot
sequentially. Slots 10, 11, 12, 0, 1 are
occupied with elements; slot 2 is open for element 48. Place the element 48
into the slot 2. Same linear probing technique is used while searching elements
in Hash table.
How
you search for an element in linear probing?
Suppose you want to search for an
element 35, find the slot value using hash function (slot = 35 % 13 = 9). Check
the slot 9 for the element 35. Slot 9 has the element 35, return TRUE.
Suppose you want to search for an
element 48, calculate the slot value (slot = 48 % 13 = 9). Check the slot 9 for
the value 48, slot 9 is occupied with value 35. We cannot simply return FALSE,
since there is a possibility of collisions, we must do a sequential search,
starting at position 10, looking until either we find the item 48 or we find an
empty slot.
Chaining
Another way of solving the Collisions is
using chaining. Chaining maintains a linked list kind of data structure at each
slot to resolve collisions.
For example, Elements 103, 65, 35, 19,
23, 76 are inserted into hash table of size 13 using the hash function
h(item)=item%13.
Suppose you want insert an element 130
into Hash table, calculate the slot (slot = 130 % 13 = 0). Slot 0 is already occupied with element
65, so create a new node with element 130 attach this node the slot 0. If you
add elements 130, 91, 71, 50, 89, 206 to the hash table, hash table change like
below.
Suppose you want to search for an
element 206 in the hash table, you calculate slot for the element 206 (slot =
206 % 13 = 11), you go to the slot 11 and traverse entire linked list at slot
11, if you found the value 206 in the linked list, you return TRUE, else FALSE.
One problem with this approach is if linked list size grows, time complexity
increases for search and insert operations. To solve this issue Java8 maintains
a binary search tree kind of data structure.
I hope with this you got some idea in
Hashing, load factor, collision resolution techniques, lets start discuss on
HashMap internal working in Java.
HashMap works on the principle of
Hashing. HashMap Use two properties, which impact the performance.
a. Capacity
b. Load Factor
Capacity
Capacity is the number of buckets(slots)
in the hash table.
Load
Factor
The load factor is a measure of how full
the hash table is allowed to get before its capacity is automatically
increased. By default Load Factor for HashMap is 0.75.
For Example let us assume
Initial capacity is 10 (I.e, Number Of
Buckets (or) slots)
Load Factor is 0.75
Each Bucket has the capacity to store
100 data items.
So when all the items reached 0.75 * 100
* 10 = 750, then the internal data structures rehashed and the Capacity (Number
Of Buckets (or) slots) increases depends on implementation. The same logic
applies in future also. HashMap is not synchronized, So user has to taken care
while performing put kind of operations.
How
data inserted into HashMap?
‘public V put(K key, V value)’ method is
used to insert <key, Value> pair into HashMap. HashMap internally stores
mapping in the form of Map.Entry object which contains both key and value
object. When you call put method, hashCode() method on object 'key' is called,
hashcode of the key is used to find the bucket (or) slot location for this
<Key, Value> pair entry. Once the bucket is identified, equals() method is
used to check whether the key is already exist in the bucket or not. If the key
is already exist in bucket, then value associated with the key is replaced,
else new Map.Entry object is created.
How
to get an element from HashMap?
‘public V get(Object key)’ method is
used to retrieve the value associated with key. 'get' method calculate the
hashCode on the object key, Based on the hasCode value of the key, it
identifies the bucket. This bucket uses tree kind of data structure to resolve
collisions. By using equals() method get method checks whether key is in the
map or not. If key is not in map, then get method return null, else return the
value associated with this key.
Note
a. Immutable objects like String, Integer
etc., are best fit to use as HashMap keys. Since the bucket (or) slot
identification is based on keys, they must be immutable. One more advantage of
immutable keys is the object's hashcode wont change and it allows caching the
hashcode of different keys which makes the overall retrieval process very fast.
b. Time complexity of get and put
operations is O(1).
You
may like
Great!
ReplyDelete