쓰이는 자료구조 - Hash Table

쓰이는 자료구조 - 해시 테이블

 

 

1. 왜, 해시 테이블인가?

 

- 해시: 어떤 값을 고정된 길이로 변환하는 것

 

- 해싱 함수(Hashing Function): Key에 대해 산술 연산(고정된 길이로 변환)을 수행하여 데이터 위치를 찾을 수 있는 값을 출력하는 함수

 

- 해시 값(=해시 주소): Key를 해싱 함수로 연산하여 얻은 값. 이를 기반으로 해시 테이블에서 Key에 대한 데이터 위치를 찾을 수 있다.

 

- 해시 테이블: K(=Key, 키)에 V(=Value, 데이터)를 저장하는 데이터 구조 -> 빠른 검색을 할 수 있다.

 

 

 

해시 테이블 구조

 

 

그 과정을 예로 들어볼까. 실제로는 복잡하겠지만, 이해를 위해 간단하게 예를 들어보겠다.

 

- 해싱 함수: K % 8

- 해시 테이블 크기: 8 (8개의 데이터를 저장할 수 있는 공간)

 

전화번호부가 있다. 총 8명의 친구가 있는데, 빠르게 찾고 싶어서 해시 테이블에 자료를 저장하고 싶다.

그 중, odeok이라는 친구의 전화번호(010)를 저장하는 과정을 설명해보자.

odeok을 해싱 함수로 연산하면, '8000002' 이라는 일련의 고정된 길이의 숫자로 치환되고, 이를 8로 모듈러 연산을 수행한다. 이러한 과정을 거치고 나면 반환되는 값은 '2'. 8개의 공간 중 3번째 공간(0부터 시작)에 '010'이 저장된다.

 

실제로 코딩테스트를 진행해보면 이런 해시 테이블의 구조까지 상세하게 알 필요는 없다. 해시 테이블은 이미 각 언어에서 기본으로 제공해주고, 우리는 이를 활용하면 된다. 그런데 내가 굳이 이러한 해시 테이블의 structure에 대해서 서술하는 이유는 이런 idea가  어떠한 문제 해결에 응용되어질 수 있기 때문이다. 

 

---

 

2. 어디서, 왜 사용될까?

 

- 장점:

배열과 달리 K를 기반으로 V를 빠르게 찾을 수 있으므로 저장/검색 속도가 빠르다.

빠른 검색이 가능하므로 키에 대한 데이터가 이미 존재하는지 확인하기 쉽다.

 

 

- 단점:

저장공간이 상대적으로 많이 필요하다.(아래의 데이터 충돌 상황을 최대한 피하려면)

서로 다른 K이지만 해싱 함수를 통해 같은 결과를 반환한다면 같은 주소에 다른 데이터가 서로 들어가려는 충돌상황이 발생될 수 있는데, 이런 충돌을 해결하기 위한 별도의 data structure가 요구된다.

 

 

- 주요 용도:

저장/삭제/수정/검색이 빈번하게 이루어지는 상황에서 사용되어진다. (그냥 거의 모든 상황..)

대표적으로 캐시(임시기억)에서 활용된다.

 

---

 

3. 충돌을 해결하기 위한 IDEA

 

3-1. Chaining 

 

- Open Hashing 기법으로, 해시 테이블의 기본 저장 공간 외의 공간을 추가적으로 활용하는 기법

 

- 충돌이 발생하면, Linked List를 활용하여 문제를 해결한다.

 

 

Hash Table - Chaining

 

 

앞서 말했던 사례에서 살을 붙여볼까. 이번에는 Tistory라는 친구의 '011'전화번호를 저장하려고 한다. Tistory를 해싱 함수로 연산하였더니 '8000082'가 나왔고 모듈러 연산을 했더니 공교롭게도 또 '2'가 나왔다. 그럼, 다시 세번째 공간에 Tistory의 전화번호 '011'을 저장해야하는데, odeok의 전화번호는 지워져야하는 걸까? 이런 문제를 해결하기위해 충돌을 대비한 Linked List 를 따로 마련하는 것이다. [8000002, 010]과 [8000082, 011] 을 함께 저장할 수 있는 자료 구조. 기존의 사례에선 해시 테이블의 저장공간이 단일 데이터 타입(int, string 등) 이어도 상관없지만, 이번의 사례에선 다르다. Tistory 친구의 전화번호를 검색하기 위해서 해싱 함수를 거쳤더니 2가 나왔다. 제일 먼저 저장된 값은 010이고 두번째 값은 011인데 뭐가 진짜 전화번호일까? 이를 구분하기위해 K를 함께 저장해야한다. 따라서 단일 데이터 타입이 되어서 안되고 객체 타입이 되어야하겠지.

 

 

3-2. Linear Probing

 

- Close Hashing 기법으로, 해시 테이블의 기본 저장 공간 내에서 충돌 문제를 해결하는 기법

 

- 충돌이 발생하면, 해당 해시 값의 다음 address부터 맨 처음 나오는 빈 공간에 값을 저장한다.

 

- Chaining 기법은 추가적인 저장공간(Linked List)가 필요했는데, Linear Probing은 필요가 없으므로 memory가 제한적인 경우 적합하다.

 

Linear Probing도 Chaining과 마찬가지로 Hash Table의 데이터 타입이 객체가 되어야한다. 단지 Linked List가 추가적으로 필요하지 않을 뿐.

 

---

 

4. 마무리

 

해시 테이블은 빠른 검색이 가능하다는 장점이 있지만, 잦은 충돌 문제를 숙제로 안고 가야한다. 이를 해결하려면 해시 함수율(모듈러연산의 피연산자라고 할까나..)을 재정의하거나, 해시 테이블의 저장 공간을 늘려야한다. 이 때문에 저장 공간과 효율성은 반비례하므로 그 중간 지점을 잘 찾아야한다. 물론 우리가 그걸 찾을 필요는 없고.