Skip to main content

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 as 115.
    • Calculate index by using index method it will be 6.
    • Calculate hash code of Key vaibhav. It will be generated as 118.
    • Calculate index by using index method it will be the same 6.
  • How to solve
      1. 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 是否相等， 相等则替换。
      1. Check the Bucket of index 6 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.
      1. When the length of the linked list is greater than the threshold (default is 8) and the length of the HashMap array exceeds 64, perform the operation of converting the linked list to the red-black tree.

Complexity of HashMap​

  • put()
    • Average O(1), and insert into an empty bucket O(1).
    • insert into a red-black tree bucket O(nlogn).
    • insert into a linked list bucket O(n).
  • get()
    • Average O(1).
    • lookup in a red-black tree bucket O(nlogn).
    • lookup in a linked list bucket O(n).