맵 & 해시 테이블

맵(Map)

• key-value 쌍을 저장하는 ADT(Abstract Data Type: 추상 자료형)
• 같은 key를 가지는 쌍은 최대 한 개만 존재(key의 중복을 허용하지 않음)
• associative array, dictionary라고 불리기도 함

Map 구현체

• 해시 테이블(Hash Table)
• 트리 기반(Tree-based)

해시 테이블(Hash Table, Hash Map)

• 배열과 해시 함수를 사용하여 map을 구현한 자료 구조
• (일반적으로) 상수 시간으로 데이터에 접근하기 때문에 빠르다

해시 함수(Hash Function)

• 임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수
• (Hash Table에서는) 임의의 데이터를 정수로 변환하는 함수

"인터스텔라"라는 Input이 해시 함수를 거쳐 20033이라는 정수가 나온다고 가정할 때, 20033이 인터스텔라의 hash가 된다.

해시 테이블의 동작 과정

1. 해시 테이블이 8의 크기를 가지고 있다고 가정
2. put("010-2222-2222", "홍진호") 실행
3. "010-2222-2222" 키를 해시 함수를 통해 202라는 해시를 획득
4. 획득한 해시를 해시 테이블의 크기(capacity)로 나머지 연산하여 2를 획득
5. 해시 테이블의 2 인덱스에 key, value, hash 삽입

해시 충돌(Hash Collision)

발생 원인

• key는 다른데 hash가 같을 때
• key도 hash도 다른데 나머지 연산(hash % map_capa) 결과가 같을 때

해시 충돌 해결 방법

• Separate chaining
• Open addressing(Open addressing 중에서도 여러가지의 방식이 있다)

Separate chaining

충돌이 발생할 경우 해시 테이블의 Linked List로 관리되고 있는 각 버킷(슬롯)에 참조값을 두어 여러개의 key-value 쌍을 관리
충돌 되었던 버킷의 값이 삭제가 된다면 삭제된 자리에 Linked List로 연결되었던 참조값이 그 자리를 차지하게 된다.

Open addressing(Linear Probing 방식)

충돌이 발생할 경우 충돌이 발생한 해시 테이블의 버킷(슬롯)의 다음 비어있는 버킷을 찾아 삽입하는 방식
충돌 되었던 버킷의 값이 삭제 된다면 값을 비우는 것이 아닌, deleted와 같은 삭제되었던 버킷이라는 것을 표시할 수 있는 더미 데이터를 삽입한다.

해시 테이블 리사이징(resizing)

• 해시 테이블 내의 특정 기준만큼의 데이터가 삽입되면 크기를 늘려주는 행위
• Java 기준 기존 해시 테이블에서 두 배 만큼의 사이즈로 해시 테이블을 만들고, 기존 해시 테이블에서의 각 해시값과 늘어난 사이즈를 나머지 연산을 통해 새 해시 테이블로 삽입

Java Hash Table 사용 예제

Map<String, String> phoneToName = new HashMap<>();
phoneToName.put("010-2222-2222", "홍진호");
phoneToName.put("010-7777-7777", "김럭키");
System.out.println(phoneToName.get("010-7777-7777"));
System.out.println(phoneToName.containsKey("010-2222-2222"));

Java HashMap 특징

	Java HashMap
구현	hash table 사용
데이터 접근 시간	(일반적으로) 모든 데이터를 상수 시간에 접근
삽입/삭제 시간	(일반적으로) 모든 데이터를 상수 시간에 접근
해시 충돌 해결 방법	Separate chaining
default init capacity	16
resize 타이밍	맵 사이즈의 3/4 이상 데이터 존재 시
resize 규모	2배
hash table capacity	power of 2(2의 승으로만 존재)