Java HashMap동작 원리

 HashMap

 - Hash맵은 Key와 Value로 이루어진 Java의 자료구조

 - Key는 중복을 허용하지 않고 Value는 중복을 허용한다.

 - HashMap의 내부구조는 배열로 되어있고 key는 직접 내부 배열의 인덱스가 될 수 있다. 이 배열을 버킷이라 한다.

 - 인덱스를 구하기 위해서 해시 함수를 사용하는데 해시 함수는 hashcode() % M 으로 구할수 있다.

 - 그런데 이렇게 HashCode를 구하면 동일 중복값이 발생하게 된다. 이것을 해시 충돌이라 하는데

 - 해시 충돌을 방지하기 위해 Open Addressing 방식과 Separate Chaning 방식이 있다

 - Open Adressing 방식은 해시충돌이 발생하면 인접 index 값을 새로 구해서 해시충돌을 우회하는 방법이다.

 - Separate Chaning 방식은 동일한 해시값이 있으면 LinkedList로 관리하게 된다.

 - Java8에서는 8개 이상이면 Tree로 변경해서 관리하게 되고 다시 6개 이하가 되면 LinkedList로 변경하여 관리한다.

   Tree는 Red-Balck Tree를 사용하며 Tree는 메모리를 많이 사용하기 때문에 6개 이하이면 LinkedList로 관리하게 된다.

 - Hash 함수를 사용할때 해시 버킷이 적다면 메모리를 절약 할 수 있지만 충돌이 잦아진다. 그래서 특정 이상 수치가 넘어가면 해시 버킷을 2배로 늘린다. 

 - 해시함수를 구할때 소수로 되어있다면 충돌이 덜 발생할 수 있는데 int로 되어있어 해시 충돌이 잦아 질수 있다. 그래서 Java에서는 보조 해시 함수를 사

    용하여 해시값을 변형한다.