HashMap의 동작

Amortized Constant Time을 위하여 어떻게 해시 충돌 가능성을 줄이는가?

HashMap = HashTable 제공 기능은 동일

[차이점]

1. HashMap은 동기화 X (Thread-Safe 보장 안함) -> 직접 Syncronize로 동기화 구현해야됨, HashTable은 동기화 O 
2. HashMap은 보조 해시 합수는 사용하기 때문에 HashTable 보다 해시 충돌이 덜 발생함 
3. HashMap은 지속적으로 개선되고 있음

[공통점]
1. 키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 할당 배열이라고 부름


HashMap java 8 버전에 개선된 사항
데이터의 개수가 일정 이상일 때에는 링크드리스트보다 트리가 성능상 이점이 많기 때문에 java 8버전부터 HashMap에서 상수 형태로 데이터가 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다.
만약 데이터가 삭제되어 6새에 이르면 다시 링크드 리스트로 변경된다.
(이유 : 데이터가 적을때 트리와 링크드 리스트의 WorstCast 수행 시간이 차이가 안나기 때문에)

=> 8, 6 2이상이 차이 나는 이유는 차이가 1인 경우 불필요하게 링크드리스트 -> 트리, 트리 -> 링크드 리스트 변경이 자주 발생하기 때문에 성능 저하를 일으킴
                 
java 7 -> java 8 차이
java 8은 Node클래스를 사용함. 링크드 리스트 대신에 트리를 사용할 수 있도록 하위 클래스인 TreeNode가 있다는 것이 java 7과의 차이점이다.

Java HashMap에서는 해시 충돌을 방지하기 위하여 Separate Chaining과 보조 해시 함수를 사용한다.

Java 8에서는 Separate Chaining에서 링크드 리스트 대신 트리를 사용하기도 한다.

그리고 String 클래스의 hashCode() 메서드에서 31을 승수로 사용하는 이유는 성능 향상 도모를 위한 것이다.

예를 들어 HttpRequest가 생성될때마다 여러 개의 Hashmap이 생성되고 GC의 대상이 된다. 즉, 많은 데이터들이 HashMap에 저장됨으로 앞으로도 HashMap은 계속 개선될 것이다.