자료구조 - 해시(Hash)

해시(Hash)

---

https://en.wikipedia.org/wiki/Hash_table

해시는 데이터를 다루는 기법 중 하나로 검색과 저장을 아주 빠르게 하는 자료구조이다.

데이터를 저장할 때 키-값 형태로 데이터가 존재하고 키 값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어난다.

해시 자료구조는 데이터를 키-값 형태로 저장해 준다고 했는데 그러기 위해서 키 값을 고정된 길이의 값으로 바꿔주는 해시 함수와 해싱이라는 과정 그리고 키-값 데이터를 저장해 주는 해시 테이블을 이해해야 한다.

 

 

해시 함수(Hash Function)와 해싱(Hashing)

---

해시 함수라고 불리는 것으로 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 알고리즘이다.

해시 함수는 키 값을 고정된 길이의 hash로 변환하는 역할을 한다. 그림과 같이 사람의 이름을 해시 함수를 거쳐서 고정된 길이의 해시 값이 버킷(buckets)에 저장된다.

이러한 해시 함수에서 키 값을 hash로 변환하는 과정을 해싱이라고 하고 해싱 과정을 거쳐서 나오는 값을 해시 값 또는 해시코드라고 부른다.

 

해시 테이블(Hash Table)

---

해시 테이블은 연관 배열구조를 이용하여 데이터를 키와 값으로 저장하는 자료구조이다.

위의 그림과 같이 어떤 키 값을 해시 함수를 통해서 데이터를 키 값으로 바꾸어 버킷에 저장한다.

공부하면서 연관 배열 구조를 처음 접해봤는데 잠깐 정리해보자면 연관 배열은 자료구조 중 하나로, 키-값이 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있는 자료구조이다.

이러한 해시 테이블의 장단점을 살펴보면 먼저 장점으로는 3가지가 있다.

1. 중복을 제거할 수 있다.
2. 데이터 캐싱, 보안에 주로 사용된다.
3. 배열의 인덱스로 접근하기 때문에 삽입, 삭제 등의 연산이 빠르다.

반대로 단점도 3가지 알아보자.

1. 공간 복잡도가 커진다.
2. 충돌이 발생할 수 있다. 만약 충돌이 발생하면 시간 복잡도가 O(N)에 가까워진다.
3. 순서가 있는 배열에는 어울리지 않는다.

 

HashMap

---

Java 언어로 개발을 할 경우 HashMap이라는 자료구조를 자주 사용하게 되는데 똑같이 Collection 인터페이스를 구현하고 있는 HashTable과 어떤 차이가 있는지 알아보자.

두 가지의 자료구조에서 가장 큰 차이는 동기화 지원 여부와 null 처리여부이다.

HashTable은 동기화를 지원하지만 null을 허용하지 않고, 반대로 HashMap은 동기화 지원을 안 하지만 null은 허용해 준다.

동기화를 고려하면 HashTable을 사용하는 것이 좋지만 동기화 속도가 느려서 Java 5부터 동기화를 제공하는 ConcurrentHashMap을 제공한다고 한다. 이 또한 HashTable과 마찬가지로 동기화는 지원하지만 null은 허용하지 않는다.

 

해시 충돌

---

https://en.wikipedia.org/wiki/Hash_table

해시를 공부하기 위해서 자료를 찾아보면 항상 해시 충돌에 관한 문제와 어떻게 해결할 수 있는지 방법에 대한 설명이 나와있다.

해시 충돌을 먼저 알아보면 서로 다른 문자열이 해시 함수를 통하여 해싱한 해시 값이 중복인 경우를 말한다.

위의 사진과 같이 John Smith와 Sandra Dee라는 이름의 키 값이 해시 함수를 거치게 되면서 해시 테이블에 값을 저장될 때 같은 인덱스 값을 가지는 충돌 문제가 발생할 수 있다.

충돌이 많아질수록 탐색의 시간 복잡도가 O(1)에서 O(N)에 가까워지게 된다. 그렇기 때문에 충돌을 줄여주는 해시 함수를 사용하는 것이 좋다.

충돌을 해결하는 방법으로는 Separating Chaining 방법과 Open addressing 방법이 있다.

 

충돌을 해결해 주는 방법

---

1. Separating Chaining

https://en.wikipedia.org/wiki/Hash_table

JDK 내부에서도 사용하는 충돌처리 방식으로 연결 리스트를 사용하는 방식이다. 레드 블랙 트리도 사용할 수 있는데 두 개의 기준은 데이터가 6개 이하면 연결 리스트를, 8개 이상이면 트리를 사용한다.

만일 7개일 경우 데이터를 삭제하게 되면 연결 리스트로 바꿔야 되고, 추가되면 레드-블랙 트리로 바꿔야 하기 때문에 오버헤드가 발생하게 되어 기준을 6과 8로 잡은 것이다.

앞서 충돌에 대한 설명에서 나와있던 그림이 Separating Chaining 방법으로 각 인덱스가 연결 리스트(entries)를 가리키게 된다.

연결 리스트를 사용할 경우 인덱스 충돌이 일어났을 때 인덱스가 가리키고 있는 연결 리스트에 노드를 추가 삽입한다.

그림을 예시로 보면 John Smith와 Sandra Dee라는 키 값에 대한 인덱스가 충돌이 발생하는데 해당 인덱스가 가리키는 연결 리스트에 Sandra Dee의 해시 값을 노드로 만들어 추가해 주는 방식이다.

데이터를 탐색할 때는 키에 대한 인덱스가 가리키고 있는 연결 리스트를 선형 검색하여 해당 키에 대한 데이터를 반환한다. 삭제 또한 비슷하게 키에 대한 인덱스가 가리키고 있는 연결 리스트에서 해당 노드를 삭제한다.

Separating Chaining 방식을 사용하면 충돌을 해결할 수 있지만, 단점으로는 연결 리스트 구조를 사용하기 때문에 추가할 수 있는 데이터 수의 제약이 있다.

 

2. Open addressing

인덱스에 대한 충돌 처리에 대해서 연결 리스트와 같은 추가적인 메모리를 사용하지 않고 Hash Table Array의 빈 공간을 사용하는 방법이다.

추가적인 메모리 공간을 사용하지 않기 때문에 Separate Chaining 방식에 비해서 메모리가 덜 사용된다는 장점이 있다.

Open addressing 방법에는 Linear Probing, Quadratic Probing, Double hashing 등이 있는데 이 중에서 Linear Probing에 대해서 정리해 보자.

 

Linear Probing 방식은 인덱스가 중복되는 충돌이 발생했을 때 인덱스 뒤에 있는 버킷 중에 빈 버킷을 찾아서 데이터를 넣는 방식이다.

그림을 보면 John Smith와 Sandra Dee의 인덱스가 겹치면서 충돌이 발생하는데 이때 Sandra Dee의 데이터를 겹치는 152 인덱스 뒤인 153에 넣게 된다.

기존의 해시 함수를 통해서 나온 인덱스가 충돌로 인해서 다른 인덱스로 바뀌기 때문에 Linear Probing에서 원하는 데이터를 탐색하기 위해서는 같은 키가 나오거나 또는 키가 없을 때까지 검색을 진행해야 한다.

데이터를 삭제하기 위해서는 더미 노드를 넣어서 검색할 때 다음 인덱스까지 검색을 연결해 주는 역할을 해줘야 하므로 삭제 작업이 어렵다.

 

Resizing

Resizing은 Separating Chaining과 Open addressing 방법을 사용할 때 버킷의 크기가 일정 크기를 넘기게 되면 더 큰 버킷을 가지는 배열을 새로 만든 다음 기존 배열의 해시를 다시 계산해서 복사해 주는 작업이다.

보통은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 경우 임계점이라 판단하고 기존의 길이의 두 배로 확장해 준다.

숫자로 표현하면 0.75라는 숫자가 되고 해당 숫자를 load factor라고 불린다.

Separating Chaining의 경우 버킷이 일정 수준으로 차 버리면 각 버킷에 연결되어 있는 리스트의 길이가 늘어나기 때문에 검색 성능이 떨어지게 되므로 버킷의 개수를 늘려줘야 한다.

반대로 Open addressing의 경우 고정 크기의 배열을 사용하기 때문에 데이터를 더 넣기 위해서는 배열을 확장해줘야 한다.

 

 

 

참고 자료

---

[알고리즘] 해시(Hash)

[자료구조] Hash/HashTable/HashMap

Hash table - Wikipedia