자바에서 HashMap은 배열로 이루어져 있다.
HashMap의 index를 어떻게 관리하는지 보면, hashcode() % M 으로 index를 결정 하게 되는데, 이러한 단순한 방식으로는 해시 충돌이 일어나게 된다.
해시 충돌을 방지하기 위해 open addressing과 seperate chaining 방식을 사용한다. open addressing은 해시 충돌이 발생했을때, 비어 있는 주변 인덱스를 찾아 우회하는 방법이고, seperate chaining은 해시 충돌이 발생했을때, 같은 인덱스에서 linkedList로 관리한다. 자바에서는 아래 그림과 같은 seperate chaining 방식을 사용하고 있다.
출처: https://www.digitalocean.com/community/tutorials/java-hashmap
추가로, linkedList의 node가 8개 이상이 되면, red black tree 형태로 관리하게 된다.
