HashMap, HashTable

초보개발·2022년 7월 13일

JAVA

목록 보기

11/15

해시맵: 탐색에 특화된 자료구조

HashMap과 HashTable은 key: value 쌍으로 저장되는 구조이다. key에 대한 해시 값으로 value를 저장하고 조회할 수 있고 key-value 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array라고 할 수 있다. 즉, key 값으로 value를 얻을 수 있다.

HashTable(Dictionary), HashMap(Map, 사상)

해시테이블 구현은 링크드 리스트와 hash code function만 있으면 된다.

해시맵 데이터 삽입 과정

키의 hash code 계산

hashCode( )가 반환하는 자료형은 int이고 생성 가능한 객체의 수는 이 범위를 뛰어 넘기도 하고 애초에 HashMap 객체에서 $O(1)$ 을 보장하기 위한 random access를 가능하게 하려면 원소가 $2^{32}$ 인 배열을 모든 HashMap이 갖고 있어야하기 때문 -> 메모리 절약을 위해 실제 해시 함수의 표현 정수 범위 $|N|$ 보다 작은 M개의 원소가 있는 배열만 사용

int index = X.hashCode() % M 으로 나머지 값으로 해시 버킷의 인덱스를 구한다.

서로 다른 해시 코드를 갖는 서로 다른 객체가 $1/M$ 의 확률로 같은 해시 버킷의 인덱스를 가질 수 있음 -> 해시 함수가 얼마나 해시 충돌을 회피하도록 잘 구현되어있는지의 문제가 아닌 다른 종류의 충돌

3-1. Open Addressing은 데이터를 삽입하려는 해시 버킷이 이미 사용중이면 다른 해시 버킷에 해당 데이터를 삽입한다.

데이터 저장/조회할 해시 버킷을 찾을 때 Linear Probing, Quadratic Probing 등 사용
데이터 삭제할 때 처리가 효율적이지 않음
연속된 공간에 데이터를 저장하므로 Separate Chaning보단 캐시 효율이 높음(📌지역성)
배열의 크기가 커진다면(M이 커지면) 캐시 효율의 장점이 사라지게 됨 -> 캐시의 적중률이 낮아지기 때문!
🔑 즉, 데이터 개수가 적다면 Open Addressing

3-2. Java의 HashMap에서는 Separate Chaining을 사용한다. 이 경우 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 연결 리스트의 head로 구성되어 있다.

해시 충돌을 잘 회피할 수 있도록 구현한다면 worst case가 발생하는 것을 줄일 수 있음 -> 보조 함수
데이터의 개수가 많아지면 연결 리스트에서 트리로 변경해 사용

hash collision: 다른 두개의 키가 같은 해시코드를 갖거나 다른 두개의 해시코드가 같은 인덱스를 가리키는 경우

Separate Chaining

연결 리스트? 트리?

// java8 HashMap
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

이를 결정하는 기준은 해시 버킷에 할당된 key-value 쌍의 개수이다.
하나의 해시 버킷에 8개가 모이면 연결리스트 -> 트리 변경, 삭제되어 6개가 되면 다시 연결 리스트로 변경

트리는 연결리스트보다 메모리 사용량이 많고 데이터가 적을 때 연결 리스트의 worst case 수행 시간의 차이가 의미 없는 수준이기 때문
왜 8과 6으로 2이상의 차이를 두었냐면, 만약 차이가 1일 경우 어떤 한 key-value 쌍이 삽입/삭제가 반복적으로 일어날 때 불필요하게 트리와 연결 리스트로 변경하는 일이 빈번해져 성능 저하를 유발할 수 있음

해시 버킷의 동적 확장

해시 버킷의 개수가 적다면 메모리 공간을 절약할 수 있지만 해시 충돌이 그만큼 발생하여 성능적인 손실이 발생한다. HashMap은 key-value 쌍 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 2배로 늘린다.
이렇게 해시 버킷 개수를 늘리면 $N/M$ 값도 작아지므로 해시 충돌로 인한 성능 문제도 어느정도 해결 가능하다.
데이터 개수가 임계점에 다다를 때마다 해시 버킷의 개수 크기를 2배씩 증가 시킨다. (버킷의 최대 개수는 $2^{30}$ )

임계점: load factor * 현재 해시 버킷 개수
- load factor: 0.75 = 3/4, HashMap 생성자에 지정 가능
2배씩 증가의 문제: 해시 버킷의 개수 M이 $2^a$ 가 되어 인덱스를 계산할 때 X.hashCode( )의 하위 a개 비트만 사용하게 된다는 것, 즉 해시 함수가 32비트 영역을 고르게 사용하도록 만들었어도 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생 가능