Java Collections 集合
1. Internal Working of HashMap
Data structure
Node
HashMap contains an array of Node
and Node
can represent a class having the following objects:
int hash
K key
V value
Node next
Hashing
Hashing is a process of converting an object into integer form by using the method hashCode()
.
Buckets
It bucket is one element of the HashMap array. It is used to store nodes. Two or more nodes can have the same bucket. In that case, a link list structure is used to connect the nodes. Buckets are different in capacity. A relation between bucket and capacity is as follows:
capacity = number of buckets * load factor
Index Calculation in Hashmap
The Hash code of the key may be very large, then it will easily cause outOfMemoryException
. So we generate an index to minimize the size of the array. The following operation is performed to calculate the index.
index = hashCode(key) & (n-1)
Hash Collision 哈希碰撞
- Case
- Calculate hash code of Key
vishal
. It will be generated as115
. - Calculate index by using index method it will be
6
. - Calculate hash code of Key
vaibhav
. It will be generated as118
. - Calculate index by using index method it will be the same
6
.
- Calculate hash code of Key
- How to solve
-
- Go to index
6
of the array and compare the first element’s key with the given key. If both are equals then return the value, otherwise, check for the next element if it exists. 检查两个 key 是否相等, 相等则替换。
- Go to index
-
- Check the
Bucket
of index6
is a Red-black Tree Node. if it is, call the((TreeNode<K,V>)p).putTreeVal()
method. Otherwise, traverse the linked list and insert, inserting the end of the linked list.
- Check the
-
- When the length of the linked list is greater than the threshold (default is
8
) and the length of the HashMap array exceeds64
, perform the operation of converting the linked list to the red-black tree.
- When the length of the linked list is greater than the threshold (default is
-
Complexity of HashMap
put()
- Average
O(1)
, and insert into an empty bucketO(1)
. - insert into a red-black tree bucket
O(nlogn)
. - insert into a linked list bucket
O(n)
.
- Average
get()
- Average
O(1)
. - lookup in a red-black tree bucket
O(nlogn)
. - lookup in a linked list bucket
O(n)
.
- Average