Map Interface
key와 value 형태로 저장하는 자료구조이다.key에 대한 해시 값에 해당하는 버킷에 Entry(key, value) 값을 저장한다.
1. 해시 함수
- 해시 함수는
key 값을 해시 테이블의 인덱스(버킷) 값으로 변환한다.
- 해시 함수가
key 값을 해시 테이블의 인덱스 값으로 변환하기 때문에 Random Access가 가능하다.
- 만약
key에 해당하는 인덱스 값을 unique하게 생성한다면 하나의 버킷에 하나의 Entry만 저장할 수 있으므로 요소를 찾는 시간은 O(1)만큼 걸린다.
2. 해시 충돌
- 실제로는 해시 함수는
key에 대한 유일성을 보장하지 못한다.
- 즉, 서로 다른
key값에 대해서 같은 값을 반환할 때가 있기 때문에 서로 다른 객체가 해시 테이블의 같은 버킷에 저장될 수 밖에 없다.
- 즉,
해시 충돌이 발생할 경우 추가적인 탐색 시간이 소요되기 때문에 해시 함수가 key에 대해서 얼마나 좋은 분포도를 가지고 있느냐가 성능을 좌우한다.
1) Chaining
- 해시 충돌이 발생할 경우, 버킷을
LinkedList 형태로 구성하여 저장하는 방식이다.
- 자바에서는 탐색 시간을 줄이기 위해
LinkedList 요소의 개수가 8개 이상이 될 경우 Red-Black Tree로 변환하여 성능을 향상 시킨다.
- 하나의 버킷에 요소의 개수가 6개이면
LinkedList 형태를 취하고 8개 이상이면 Red-Black Tree 형태를 취한다.
- 6과 8로 차이를 둔 이유는 어떤 한
key, value 쌍이 반복적으로 저장/삭제될 경우 리스트와 트리로 변환하는 과정이 반복되면서 생기는 성능저하를 방지하기 위함이다.
2) Open Addressing
- 해시 충돌이 발생할 경우, 비어있는 버킷을 찾기 위해 추가적인 연산(?)을 수행한다.
버킷 k에 대해서 해시 충돌이 발생했다면 비어있는 버킷을 찾을 때 까지 k+1, k+2, ... 번째 버킷을 확인한다.- 그러나 이 방법에는
cluster가 발생하여 성능이 저하될 가능성이 있다. 만약 해시 함수의 결과가 계속해서 k값만 반환한다면 결국 k번째 버킷에서부터 순차적으로 요소들이 저장될 것이고 이 과정에서 비어있는 버킷을 찾기 위해 반복적으로 순차 탐색이 발생할 것이다.
- 이 문제점을 극복하기 위해
Quadratic probing 이라는 방식을 사용하는데 비어있는 버킷을 찾기 위해서 1씩 증가시키는 것이 아니라 1, 4, 9, 16.... 처럼 제곱 수만큼 증가시키며 찾는 방식이다.
3. Load Factor
- 해시 테이블의 버킷에 요소들이 저장될 수록
해시 충돌이 발생할 확률이 높아진다.
Load Factor는 해시 테이블의 전체 버킷에 대한 요소가 저장된 버킷의 비율을 말한다. Load Factor의 값이 0.5라면, 현재 해시 테이블에는 절반에 해당하는 버킷에 요소들이 저장되어 있음을 뜻한다.- 즉,
Load Factor 의 값이 작을 수록 해시 테이블은 비어있음을 나타내고 값이 클수록 해시 테이블이 가득차있다는 것을 말한다.
- 자바의 경우,
Load Factor의 값이 0.75를 넘을 경우 빈번한 충돌을 피하기 위해 해시 테이블의 크기를 resize하게 된다.
- 해시 테이블을
resize하는 경우, 기존 해시 테이블에 저장되어 있는 요소들을 새로운 해시 테이블에 저장시키기 위해서 O(n) 시간만큼의 추가적인 연산이 발생할 수 밖에 없다.
4. 사용자 정의 객체를 KEY로 사용할 경우
- 사용자가 정의한 객체를
key로 사용할 경우에는 반드시 hashCode()와 equals()메소드를 재정의해야 한다.
equals() 메소드의 결과가 참인 두 객체에 대해서 hashCode()는 반드시 같은 해시 값을 리턴하지만 해시 값이 같다고해서 두 객체가 반드시 같은 객체는 아니다. 즉, 서로 다른 객체가 같은 버킷에 저장될 수 있다는 뜻이다.HashMap은 우선적으로 해시 값이 같다면 버킷에 저장되어 있는 Entry 요소들을 탐색하며 equals() 연산의 결과가 참인 value 객체를 리턴한다. 이러한 이유때문에 반드시 hashCode() 와 equals()를 함께 재정의해야한다.
