[자료구조] 해시(Hash)와 해시 테이블(Hash Table)

Hash와 Hash Table을 학습하기 전에

해시는 분명 2학년 때 자료구조 수업에서 학습했다. 그런데 당시의 나는 해시라는 개념을 명확하게 이해하지 못했던 것 같다. 수업 시간에 해시 ... ? 해시태그 ... 해시 브라운 ... 해쉬스완 ... 이런 생각을 했던 기억이 있는 것을 보면 말이다.

 

각설하고, 해시는 상당히 강력한 힘을 가지고 있다. 이번 포스트에서는 해시란 무엇인지, 해시 함수란 무엇인지, 해시 테이블이 무엇인지를 학습하며 해시가 가진 강력한 힘을 보다 잘 활용할 수 있는 것이 목표이다.

 

해시 함수 (Hash function)

해시를 설명하기 전에 해시 함수에 대해 알아야 한다. 왜냐하면 해시는 해시 함수를 통해 만들어진 값이기 때문이다.

 

해시 함수는 말 그대로 함수이다. 입력이 주어지면, 출력을 뱉어낸다. 그런데 여기서 중요한 특징은, 입력으로 임의의 길이를 갖는 임의의 데이터가 주어지더라도 출력으로는 고정된 길이의 데이터가 나온다는 것이다.

해시 함수

해시 함수의 입력으로 John Smith, Lisa Smith, Sam Doe, Sandra Dee 등 다양한 길이의 문자열이 주어지더라도, 해시 함수는 고정된 길이 2의 출력값을 뱉어낸다. 아무리 큰 데이터를 넣더라도 정해진 크기의 출력이 나오는 함수인 것이다.

 

또한, 위 그림을 통해 알 수 있는 해시의 또다른 특징은 단방향 함수라는 것이다. 단방향 함수라는 것은, 해시 함수를 통해 얻은 해시값을 원래의 데이터로 복구시킬 수는 없다는 것을 의미한다. John Smith라는 입력은 항상 02라는 출력을 뱉어내므로 02는 John Smith를 나타내는 거 아니야 ? 라고 생각할 수 있지만, Sandra Dee라는 입력 역시 02라는 출력을 뱉어낸다. 따라서 02라는 해시값을 가지고 원래의 입력을 구해낼 수는 없는 것이다.

 

해시 함수란 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수이다.

 

해시 충돌 (Hash collision)

하지만 해시는 만능이 아니다. 입력의 범위는 임의의 길이이므로 이론상 정의역이 무한한데, 출력의 범위는 고정된 길이이므로 이론상 치역은 유한하기 때문이다(갑자기 수학 얘기가 나와서 당황했다면 개추). 위 그림을 예시로 들어보자면, 해시 함수의 입력값으로 전교생 1,000명 (우리 고등학교는 전교생이 1,000명 쯤 되었던 것 같다) 이 주어지고, 출력값으로 길이가 2인 정수값을 반환한다면, 길이가 2인 정수는 고작 해봐야 00부터 99까지, 100개 뿐이다.

 

즉, 서로 다른 입력에도 동일한 값을 출력하는 상황이 나올 수 있다는 것이다. 이를 '해시 충돌' 이라고 부른다.

 

해시 충돌이란 서로 다른 입력에도 동일한 값을 출력하는 상황을 말한다.

 

해시 테이블 (Hash table)

해시 테이블은 해시 함수를 사용해 변환한 값을 인덱스로 삼아 Key와 Value를 저장하는 자료구조이다.

 

배열을 사용하면서, 그런 생각을 해본 적이 있을 수도 있다. 정수값인 인덱스가 아니라, 문자열이나 문자처럼 숫자가 아닌 값을 인덱스로 삼을 수 있다면 편할 것 같다는 생각 말이다. XX고등학교 3학년 8반 전화번호부를 생각해보자.

 

arr["미키마우스"] = "010-XXXX-XXXX";
arr["미니마우스"] = "010-OOOO-OOOO";

 

이런 식으로 말이다. 하지만 배열은 정수 인덱스를 취하기 때문에 이런 구조가 불가능하다. 나 역시 과거 코딩테스트를 공부하면서 문자열을 인덱스로 삼고 싶다는 생각을 종종 해왔고, Map에 대해 이해하기 전에는 조금 복잡하게 ... 구현을 하면서 풀었던 경험이 있다. 해시 테이블은 이러한 나의 고민을 해결해줄 수 있는 좋은 자료구조이다. 해시 함수의 정의가 무엇이었는지 다시 생각해보자.

 

'임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수' 

 

해시 테이블은 내부적으로 배열을 가지고 있다. 즉, 해시 함수의 결과값이 이 해시 테이블의 인덱스가 되는 것이다.

해시 테이블

해시 함수와 해시값을 활용해 이런 해시 테이블을 사용한다면, 속도 면에서 큰 장점을 얻을 수 있다. 해시 함수는 입력값을 출력값으로 바꿔주는 연산 1회를 통해 해시값을 뽑아낼 수 있다. 즉, O(1)의 시간 복잡도로 Key의 해시값을 계산하고, Key의 해시값을 인덱스로 삼아 버킷(실제 값(Value)이 저장되는 장소)에 접근할 수 있기 때문이다.

 

해시, 해시 함수, 해시 테이블을 활용하는 경우의 장점은 빠른 속도이다.

 

Java에서는 해시 테이블로 2가지 자료구조를 제공한다. HashMap과 Hashtable이라는 자료구조인데, 이는 이전 포스트(https://optimal-solution.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-ArrayList%EC%99%80-Vector)에서 다룬 ArrayList와 Vector의 차이와 유사한 차이점을 가진다. HashMap은 synchronized를 지원하지 않고, value에 null을 넣을 수 있지만 Hashtable은 synchronized를 지원하며 value에 null을 넣으면 NPE를 발생시킨다.

 

해시 충돌 해결법

앞서 해시 충돌이란 무엇인지 간략하게만 알아보았다. 해시 테이블을 설명하고 나서 해시 충돌 해결법을 설명하는 이유는, 해시 테이블의 구조를 안다면 해시 충돌을 왜 해결해야 하는지와 어떻게 해결하는지를 더욱 명확히 이해할 수 있기 때문이라고 생각해 구성을 이 아래로 뺐다. 이전에 봤던 해시 함수 이미지를 다시 가져와보겠다.

John Smith와 Sandra Dee의 해시값이 동일하다

우리는 해시 테이블을 학습하면서, Key의 해시값을 인덱스 삼아 배열 안에 버킷 (혹은 슬롯이라고 부르기도 함) 에 저장한다고 배웠다. 그런데 John Smith와 Sandra Dee의 해시값이 02로 같다면, 해시 테이블이 가진 배열의 02번 인덱스는 둘 중 누가 사용해야 하는 것일까 ? John Smith가 이미 02번 버킷을 사용 중이라면, Sandra Dee의 데이터는 어디에 저장해야 하는 것일까 ?

 

이러한 문제가 발생하기 때문에 우리는 해시 충돌을 해결해야 한다. 해시 충돌을 해결하는 방법에는 크게 2가지가 존재한다.

 

Separate Chaining

해시 충돌이 발생했을 때, 충돌한 두 Key의 데이터를 동일한 버킷에 저장하되, 이를 Linked List 형태로 관리하는 방법이다.

Separate Chaining

John Smith와 Sandra Dee의 해시값이 152로 동일하지만, 버킷에서는 데이터를 1개만 저장하는 것이 아니라 Linked List 형태로 관리해 여러 데이터를 담을 수 있도록 하는 것이다. 단순히 Value만 저장하는 것이 아니라, Key와 Value, 그리고 다음 Key-Value 쌍에 대한 포인터로 구성된 노드를 저장하는 것이다. Value만 저장하지 않고 Key까지 저장하는 이유는 나중에 저장한 데이터에 접근할 때 문제가 발생할 수 있기 때문이다. Value만 저장한다면, 521-1234가 John Smith의 전화번호인지 Sandra Dee의 전화번호인지 알 길이 없다.

 

Separate Chaining의 장점은, 해시 충돌이 일어났더라도 크게 개의치 않고 Linked List에 추가해주기만 하므로 삽입에 O(1)이라는 시간 복잡도를 갖는다는 것이다. 하지만 이는 동시에 단점이 될 수 있다. 탐색, 수정, 삭제의 경우에는 해당 Linked List를 전부 순회하면서 일치하는 Key를 찾아야 하므로, 최악의 경우 O(N)의 시간 복잡도를 갖는다(여기서 N은 해시 테이블에 저장된 데이터의 개수를 의미).

 

참고로, Java의 HashMap은 Separate Chaining 방식을 채택하며 Java 8에서는 데이터의 개수가 많아지면 Linked List 대신 Tree를 사용해 더욱 시간적인 효율을 꾀하고 있다.

https://d2.naver.com/helloworld/831311

 

Separate Chaining : 충돌이 발생하더라도 동일한 버킷에 저장하되, 버킷 내 데이터들을 Linked List 형태로 관리하는 방법

장점 : 삽입에 O(1)의 시간 복잡도 가짐

단점 : 탐색, 수정, 삭제에 O(N)의 시간 복잡도 가짐
(N : 해시 테이블 안의 데이터 개수)

 

Open Addressing

Open Addressing은 해시값을 인덱스 삼아 버킷에 접근했는데 해당 버킷에 이미 다른 데이터가 존재할 경우, 다른 주소 공간도 이용할 수 있도록 '주소를 개방' 하는 방식이다.

Open Addressing

John Smith와 Sandra Dee의 해시값은 873으로 동일하지만, 위 그림을 보면 Sandra Dee는 874번 버킷을 사용한다. 이처럼 자신의 버킷이 아니더라도 다른 빈 버킷을 이용할 수 있는 방법이 바로 Open Addressing이다.

 

다른 주소 공간, 즉 내 버킷이 아니라 다른 버킷을 사용한다면 발생하는 문제점은 없을까 ? 가령 Sandra Dee가 873번 버킷을 사용해야 하는데 874번 버킷을 사용 중이라는 것을 어떻게 표시하고, 관리하고, 활용할 것인가 와 같은 문제가 있을 수 있다. 그래서 Open Addressing에서 삽입, 탐색, 삭제는 아래와 같이 이루어진다.

 

삽입 - 해시 충돌이 발생했을 경우 다음 버킷으로 이동하면서 비어있는 버킷에 저장한다. 이처럼 비어있는 버킷을 탐색하는 과정을 Probing이라고 부른다.

탐색 - 계산된 해시값에 대한 버킷부터 검사하며 이 버킷이 해시값에 대한 버킷이 맞는지 확인한다. 아니라면 Probing을 해 나가는데 이 때 '삭제' 표시가 된 버킷은 스킵한다.

삭제 - 탐색을 통해 해당 해시값에 대한 데이터를 찾고 삭제한 뒤 '삭제' 표시를 한다.

 

이런 방식을 통해 Open Addressing에서는 원래의 해시값 버킷이 아니라 다른 빈 버킷을 사용할 수 있도록 관리한다. 그렇다면 Probing, 즉 탐사는 어떤 원리를 통해 이루어질까 ? Probing에도 크게 3가지 방식이 존재한다.

 

Linear Probing

단순하게 1칸 인접한 버킷을 활용하는 방법이다. 하지만, 해시 충돌이 일어나는 Key가 만약 100개가 있다면, 100번째로 삽입되는 Key에 대해서는 빈 버킷을 찾기 위해 최소 100번의 Probing을 수행해야 한다. 이처럼 데이터가 밀집되는 현상을 클러스터링 이라고 부르는데, Linear Probing은 이러한 클러스터링 문제에 취약하고, 이로 인해 탐색과 삭제에 오랜 시간이 소요될 수 있다.

 

Quadratic Probing

바로 1칸 인접한 버킷이 아니라, 1^2, 2^2, 3^2, ... 와 같이 거듭제곱만큼 떨어진 버킷을 탐사하는 방식으로 Linear Probing에 비해 더 폭넓게 탐사한다. 하지만 초기 해시값이 같은 상황이라면, Linear Probing과 마찬가지로 클러스터링 문제가 발생한다.

 

Double Hashing

해시 함수를 2번 사용하는 방법이다. Linear Probing, Quadratic Probing에서 발생하는 클러스터링 문제를 피하기 위해 첫 해시 함수는 해시값을 찾기 위해 사용하고, 두 번째 해시 함수는 충돌이 발생했을 때 Probing 폭을 계산하기 위해 사용한다.

 

Open Addressing : 해시 값에 해당하는 버킷에 이미 다른 데이터가 존재할 경우, 비어있는 다른 버킷을 사용할 수 있도록 하는 방법

탐사 방식 - Linear Probing, Quadratic Probing, Double Hashing

 

(추가) 로드 팩터 (Load factor)

로드 팩터란, 해시 테이블에 저장된 데이터 개수 N을 버킷의 개수 K로 나눈 값이다. 로드 팩터가 1 미만이라면 해시 테이블이 덜 사용되었음을 나타내며, 많은 빈 슬롯이 있을 수 있다. 하지만 로드 팩터가 1 초과라면, 테이블이 밀집되어 있음을 의미하며 충돌이 더 자주 발생해 성능 저하를 초래할 수 있다.

 

잘 설계된 해시 테이블에서의 이상적인 로드 팩터는 일반적으로 0.7에서 0.8 정도의 범위에 있다. 로드 팩터가 일정 임계값을 초과하면 버킷의 수를 늘려 해시 테이블의 크기를 조절하는 게 일반적이며, 이를 리해싱 이라고 부른다. Java 10에서는 HashMap 디폴트 로드 팩터를 0.75로 지정하여 이를 넘는 경우 리해싱을 수행한다고 한다.

 

마무리

대체 2018년의 나는 왜 해시태그, 해시 브라운, 해쉬스완을 생각했을까 ... 하는 생각은 여전히 지울 수 없다. 해시는 Set, Map 등 자료구조에서도 많이 활용되며, 이후에 다룰 Set, Map에서는 해시 기반과 트리 기반으로 크게 두 갈래로 나뉘면서 어떤 상황에서 어떤 것을 선택하는 것이 좋을지 고민을 하게 될 상황이 온다. 오늘 해시에 대해 톡톡히 공부해두고 나중에 이 지식이 나에게 큰 도움이 된다면 좋겠다.