[Kotlin] HashMap
Hash(해시)
Hash란 단방향 암호화 기법으로 산술 연산을 통하여 입력된 값을 출력 데이터가 있는 곳을 알 수 있는 값으로 바꾸는 것을 말한다. Hash function(해시 함수)은 Hash기법을 이용하기 위해 사용하는 함수이다. Hash function을 통해 입력 값이 데이터가 있는 곳을 알 수 있는 출력 값으로 연결될 수 있으므로, Hash function은 입력 값을 출력 값으로 mapping(매핑)해주는 함수라고도 한다.
HashMap(해시맵), HashTable(해시테이블)
HashMap, HashTable은 Hash 기법을 사용하여 데이터를 보관하는 자료구조이다. 데이터에 접근하거나 검색할 때 데이터들을 순회하면서 일일이 비교하는 일반적인 자료구조와 다르게 key값을 통해 한 번의 산술연산으로 데이터에 접근할 수 있기 때문에 아주 빠른 접근 속도와 검색 속도가 특징이다.
Fig1은 HashMap의 구조를 나타낸 것이다. Java와 Kotlin에서는 HashMap과 HashTable이 다른 클래스로 존재하지만, 구조는 비슷하므로 HashMap 하나로 기재하려고 한다. 두 클래스의 차이점은 본 포스트에서 다루지 않는다.
Collision(충돌)
Fig1에서 Hash function을 거친 HashMap을 보자. 배열로 이루어져 있는데, 배열의 원소에는 또 여러 개의 데이터가 들어있다. 이유는 서로 다른 두 입력 값이 Hash function을 거쳐 나온 HashMap의 주소를 가리키는 곳이 같을 수도 있기 때문이다. 이런 경우를 collision(충돌)이라고 한다. 만약 Hash function이 여러 입력 값에 대해 같은 결과를 많이 만든다면, collision이 많아질 수 있고, 이렇게 되면 데이터를 찾는데 더 오랜 시간이 걸릴 수 있다. 따라서 Hash function을 잘 설계하는 것도 HashMap의 효율성에 연관된다.
Hash function
다음은 Hash function으로 사용되는 대표적인 방법들이다.
- Division Method : 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기보다 큰 값으로 나누어 계산한다. 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다. h(k) = k % Q (단, Q ≥ table size)
- Digit Folding : Folding이란 key를 동일하게 분할한 후 각 부분을 XOR연산하거나, 더하거나, 또는 key가 문자열일 경우 ASCII 코드로 바꾸고 값을 합하는 등의 연산을 하여 테이블 내의 주소로 사용하는 방법이다.
- Multiplication Method : 숫자로 된 key값 k와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kA % 1) × m
- Radix Conversion : 진수 변환을 통해 테이블 내의 주소로 사용하는 방법이다.
- Algebraic Coding : key를 이루고 있는 각각의 bit를 다항식의 계수로 이용하여 계산한 값을 테이블 내의 주소로 사용하는 방법이다.
- Univeral Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.
Collision resolution(충돌 해결법)
1. Separate chaining
Fig1과 같이 동일한 Bucket에 여러 개의 데이터를 저장하여 관리하는 방법이다. 만약 Bucket안의 데이터들을 Linked List를 활용해 Separate chaining을 적용한다고 하자. 이 경우 N개의 데이터가 같은 Bucket에 저장된다면 최악의 경우 O(N)의 시간복잡도를 갖는다.
이러한 방식은 Bucket 안의 데이터들을 관리하는 자료구조의 구현을 제외하면 구현이 간단하고, 쉽게 추가하고 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아져 효율성이 감소한다는 단점이 있다.
2. Open Addressing
Open Addressing이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.
- Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
- Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2², 3² 칸씩 옮기는 방식이다.
- Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.
HashMap의 용도
HashMap은 어떤 경우에 언제 사용하면 좋을까?
- key-value 방식이 필요할 때
- 데이터 저장 순서가 중요하지 않을 때
- 데이터 정렬보다 빠른 접근 속도가 필요할 때
위와 같은 경우 HashMap을 이용하는 것이 적합하다.
Kotlin의 HashMap
HashMap의 성능
Kotlin은 Java의 HashMap을 사용하고 있다. Java의 HashMap의 성능은
- initial capacity
- load factor
두 가지의 영향을 받는다. HashMap은 배열을 기반으로 하고 있다고 했는데, initial capacity는 처음 HashMap을 생성할 때 배열의 크기이다. 또, HashMap의 배열 공간의 대부분이 찼을 때 collision이 일어날 확률이 높아지므로, 어느 정도 데이터가 차면 HashMap의 배열의 크기를 늘려줘야한다. 데이터가 어느 정도 찼는지의 정도를 나타내는 것이 load factor 이고, 이 값은 0에서 1사이의 값이 될 수 있다.
처음 HashMap을 생성할 때 이 값을 정해주지 않으면 initial capacity는 16, load factor는 0.75로 작동한다. HashMap은 데이터 개수가 capacity와 load factor의 곱보다 커지면 배열을 두 배로 확장한다. 배열을 확장하는 것은 시간을 소요하는 작업이므로 어느 정도의 데이터를 저장할 것인지에 따라 initial capacity를 정해주는 것이 중요하다. Fig2는 HashTable의 배열의 크기가 커질 때를 도식화한 것이다. 그럼에도 collision이 일어날 수 있는데, Java의 HashMap은 separate chaining을 사용하여 Bucket에 Linked List를 사용하거나, java8 이후에는 Red-Black Tree를 사용한다.
hashCode(), equals() override
Kotlin에서 class를 작성할 때, 만약 클래스를 Hash를 사용한 자료구조에 보관한다면 객체의 동등성을 비교하는 함수로 equals()뿐만 아니라 hashCode()까지 override해주어야 한다. 만약 data class로 작성한다면 hashCode()함수와 equals()함수를 자동으로 override해준다. 이에 관한 자세한 내용은 아래 링크에서 참고하자.
Reference
Overall part
1. [망나니개발자] “[자료구조] 해시테이블(HashTable)이란?” — https://mangkyu.tistory.com/102
2. [wisecow] “<해싱 (Hashing)>: 기본 개념” — https://mattlee.tistory.com/62
3. [Suyeon Bak] “(Crypto) 해시(hash)란?” — https://medium.com/@yeon22/crypto-%ED%95%B4%EC%8B%9C-hash-%EB%9E%80-6962be197523
