Map
- key-value pair들을 저장하는 ADT(Abstract Data Structure)
- 같은 key를 가지는 pair는 최대 한 개만 존재
- associative array, dictionary라고 불리기도 함
Map 구현체
- hash table
- tree-based
Hash Table
배열과 해시 함수(hash function)을 사용해 map을 구현한 자료구조
배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다.
(key, value, hash) 쌍 데이터를 저장하는데, hashFunction으로 key값을 인덱스로 바꾼 후 배열에 접근해 저장한다. (key, value, hash) 쌍이 같이 저장되는데, 이는 나중에 collision이 발생했을때 어떤 value가 내가 원하는 값인지 찾기 위함이다.
hash는 버킷의 크기를 늘렸을 때 알맞은 공간으로 다시 데이터를 넣기 위해 사용된다. hash값을 저장하고 있음으로 또 다시 key를 hash function에 넣어 hash값을 저장하지 않고 모듈러 연산으로 새로운 버킷의 알맞은 위치에 데이터를 넣을 수 있다.
Collision이 발생하지 않으면 O(1)만에 데이터에 접근할 수 있다.
Hash Function
임의의 크기를 가지는 type의 데이터를 고정된 크기를 가지는 type의 데이터로 변환하는 함수
hash table에선 임의의 데이터를 정수로 변환한다.
hash table의 버킷 크기만큼 정수를 모듈러 연산한다.
"인터스텔라" -> [hash function] -> 202
hash table의 버킷 크기가 8이라면 202 % 8 = 2을 한 결과가 버킷의 index가 된다.
대표적인 해시 함수론 아래 3가지가 있다.
1. Division Method: 나눗셈을 이용하는 방법으로 key를 테이블의 크기로 나누어 계산한다(인덱스 = key % 테이블 크기). 테이블 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
2. Digit Folding: 각 key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법.
3. Multiplication Method: 숫자로 된 key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용해 다음과 같은 계산을 해준다. h(k) = (kAmod1) x m
4. Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법
hash collision
두 가지 경우 발생할 수 있다.
- key는 다른데 hash가 같을 때
- key와 hash 둘 다 다른데 hash % map_capa 결과가 같을 때
hash collision 해결
기본적인 두 가지 방법에 대해 알아보자
1. Open Address 방식(개방주소법)
비어있는 해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하기 위한 대표적인 방법으로 3가지 방식이 존재한다.
- Linear Probing: 현재 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어있는 버킷에 데이터를 저장한다.
- Quadratic probing: 해시의 저장순서 폭을 제롭으로 저장하는 방식. 예를들어 처음 충돌이 발생한 경우엔 1만큼 이동하고 그다음엔 2^2, 3^2, 4^2씩 옮기는 방식이다.
- Double hashing probing: 해시된 값을 한 번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 더 많은 연산을 하게 된다.
Open Addressing에서 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되는데, 그렇기 때문에 Hash Table을 재정리 해주는 작업이 필요하다고 한다.
즉, 해시 충돌이 일어나서 open addressing 방식으로 처리되었을때, 이런 데이터 중 하나가 삭제된다면 삭제된 공간은 dummy space가 된다. dummy space로 표시되지 않았다면 탐색이 종료되지만 dummy space로 표시되었다면 open addressing 방식에 따라 다른 공간을 탐색한다.
2. Separate Chaining(분리 연결법)
동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 동일한 버킷으로 접근을 한다면 데이터들을 연결을 해서 관리해준다(Linked list 혹은 다른 자료구조를 이용해 저장한다). Java8의 HashTable은 self-balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현했다(Linked list와 red-black tree를 혼용한 방식).
hash table resizing
데이터가 많이 차게 되면 버킷의 크기를 늘려줘야 한다.
Java의 hash map은 전체 capacity의 75%가 차면 size를 2배로 늘려준다.
Java의 HashMap
- (보통) 모든 데이터를 상수 시간에 삽입/삭제/접근
- separate chaining으로 해시 충돌 해결(linked list와 red-black tree를 혼용한 방식)
- default initial capacity는 16
- (보통은) capacity의 75%가 차면 resize가 일어남
- resize는 2배씩 일어남. default가 16이고 항상 2의 배수로 늘어나니 capacity는 항상 2의 제곱.
Java의 HashMap, HashTable 차이
HashMap
동기화를 지원하지 않음. 즉, thread-safe 하지 않음.
key나 value에 null이 들어갈 수 있음.
같은 버킷에 들어있는 데이터 수에 따라 chaining을 Linked-list로 할지 tree로 할지 결정함.(데이터가 추가되어 8개가 되면 Linked-list -> red-black tree, 데이터가 삭제되어 6개가 되면 red-black tree -> linkedlist)
HashTable
동기화를 지원함. 즉, thread-safe함(구현부를 보면 synchronized 키워드가 붙어있음).
key나 value에 null이 들어갈 수 없음.
size, get, put 메서드 자체에 각각 synchronized 키워드가 붙어있음. 따라서 성능이 좋지 않음
concurrentHashMap
HashTable의 단점을 보완하면서 multi-thread 환경에서 사용할 수 있도록 나온 것.
put 메서드 내부에 synchronized키워드가 존재함.
버킷 단위로 lock을 사용하기 때문에 같은 버킷만 아니면 lock을 기다릴 필요가 없음.
HashMap과 마찬가지로 같은 버킷 데이터 수에 따라 Linked-list 혹은 red-black tree를 이용해 chaining함
출처
https://www.youtube.com/watch?v=ZBu_slSH5Sk
https://mangkyu.tistory.com/102
https://memostack.tistory.com/233
