안녕하세요 남갯입니다.
출처 : https://d2.naver.com/helloworld/831311
오늘은 Hash Map에 대해 정리한것을 글로 써보려고합니다.
HashMap의 정의
Key와 Value로 이루어져 있고 그 갯수에 따라 동적으로 증가하는 associate array이다.
HashMap 과 HashTable 차이점
둘은 거의 기능은 동일하다. 하지만 HashTable은 특정버전 이후 업데이트를 안하고 있는 반면 Hashmap은 특정버젼 이후에 꾸준한 업데이트를 해왔다.
또한 Hashmap 보조해시함수라는것을 이용해 해시충돌을 적게 발생시키므로 성능상 더 좋은 이점을 갖고있다.
HashMap의 저장방법
해시맵은 Key와 Value를 해시함수를 통해 버킷의 특정 인덱스에 저장한다. 해시함수는 아래와 같이 동작한다고 한다. hashcode % M 을 통해서 버킷의 크기보다 작은 인덱스에 저장을 하도록 한다. 따라서 1/M확률로 충돌이 발생하게 된다.
해시를 저장하는 공간을 버킷이라고 부른다. 버킷은 특정 임계치를 만족하면 공간을 두배로 증가시킨다.
해시충돌을 처리하기 위한 방법
해시 충돌이란 hashcode % M으로 처리된 인덱스의 버킷에 value를 저장하게 되는데, 이미 저장되어있는 곳에 다른키가 저장을 하게되서 충돌하게 되는 현상이다.
이 충돌을 해결하기위해서는 크게 두가지의 방법이 존재하는데,
1. open Addressing
- 특정배열의 인덱스가 2번이면 3번에 저장 유무를 확인한뒤 저장 혹은
- 인덱스 제곱수만큼 더해서 그 위치에 저장
- 충돌시 다른 해시함수를 한번 더 돌려서 저장
2 .seperate chaining
충돌하게 되면 LinkedList를 통해 저장을 시키는 방법이다.
둘다 최악의 경우는 O(M)의 시간복잡도를 가지게 되지만 갯수가 적을경우 openAddressing 이 일정갯수가 넘어가게 된다면 seperate chaining이 더 좋다. 왜냐하면 배열의 크기가 커질경우 해시충돌을 피하는 적중률이 낮아지기 때문이다.
자바 8버전 부터 달라진점
자바 8버전 부터는 일정 갯수가 넘어가게 될 경우 트리구조를 이용하게된다. 링크드리스트의 트리구조를 사용하게 되면 O(N)이였던 시간복잡도를
O(logN)의 시간 복잡도를 가질 수 있다. 따라서 엄청난 성능 개선이 되었다.