해시(Hash)

해시는 키(key)와 값(value)이 한 쌍을 이루는 자료구조입니다. 원리가 간단하기 때문에 복잡한 알고리즘 없이도 탐색이 가능하다는 장점이 있고, 자료구조에서 중요하게 다루는 부분은 아니라 정확한 의미를 모르고 지나가기 쉽습니다. 사전은 해시와 원리가 비슷해 예시로 많이 쓰이고 있습니다.

 

사전은 단어와 뜻으로 이루어져 있습니다. (Photo by PDPics)

사전은 단어와 뜻으로 이루어져 있습니다. 사용자는 단어의 뜻을 알기 위해 단어가 어디에 위치했는지 찾아봅니다. 각 단어의 뜻은 단어 바로 옆에 적혀 있기 때문이죠. 여기서 단어는 뜻을 찾기 위한 '주소'라고 보면 되겠습니다. 같은 단어가 여러개 있다면, 거기에다 흩어져 있다면 뜻을 찾기 힘들어 사전의 의미가 없어집니다. 물론 실제 사전은 알파벳순으로 정렬되어 중복된 단어가 있어도 크게 불편하지 않지만, 해시는 그렇지 않습니다.

 

사전이 단어와 뜻으로 이루어져 있듯이, 해시는 키와 값으로 이루어져 있고 다음과 같은 법칙을 따릅니다.

 

1. 키는 중복되지 않아야 한다.

2. 키가 없는 값은 존재할 수 없다.

 

이 조건을 만족하는 해시 데이터가 모여 있는 자료구조는 '테이블', '딕셔너리', 또는 맵(map)이라 불립니다. 이러한 구조에서는 키만 알면 바로 값을 찾을 수 있어, 이상적인 환경에서 시간복잡도 O(1)을 기대할 수 있습니다.

 

해시 함수

해시 함수는 키가 해시로 사용하기 힘들 때 키 값을 적당한 값으로 만들어 주는 함수입니다.  

연산자 mod(%)를 사용하여 키의 자릿수를 줄입니다.

Hash Function의 질이 낮아 키값이 중복되는 충돌이 일어납니다.

위 그림은 나쁜 해시 함수의 예로, 키에서 일부를 가져와 해시 값을 만들었기 때문에 충돌이 일어날 위험이 큽니다. 충돌은 데이터가 쏠려 있으면 더 자주 발생해 데이터를 분산시켜 저장하는 것이 중요합니다. 이를 반영한 충돌의 해결 방법은 크게 두 가지가 있습니다. 

 

- Open Addressing

  => 다른 해시 버킷에 데이터 삽입해 충돌 피함.

  => 연속된 공간에 데이터 삽입 - 캐시 효율이 높음

  => M 길이의 배열에서 Worst Case O(M) => 고정 크기 배열이므로 resizing

 

1. 선형 조사법 Linear Probing

충돌은 해시 값이 같은 곳에 여러 데이터가 저장되어 발생합니다. 선형 조사법은 충돌이 발생했을 때, 발생한 곳의 옆자리를 살펴봅니다. 옆자리도 충돌이 생긴다면 저장할 공간이 나올 때까지 옆으로 움직입니다. 

 

2. 이차 조사법 Quadratic Probing

이차 조사법은 선형 조사법의 데이터 쏠림 현상을 보완합니다. 선형 조사법이 한 칸씩 비교하면서 움직였다면, 이차 조사법은 n^2칸 옆의 칸을 비교합니다. 각 칸에는 상태가 기록되어 있는데 EMPTY(한 번도 저장 안됨), DELETED(있었는데 지금 없음), INUSE(데이터가 있음)로 EMPTY 상태라면 탐색 종료, DELETED라면 충돌이 발생할 수 있어 선형 조사법으로 전환합니다. 

 

3. 이중 해시 Double Hash

해시 값을 기준으로 이차 조사법을 사용한다면, 해시 값이 같을 때 항상 같은 위치를 비교합니다. 이중 해시는 해시 함수를 2개 사용하는데, 키를 가공하는 함수, 충돌 발생 시 비교할 칸을 정하는 함수를 사용합니다. 이때 두 번째 함수는 해시 값의 길이에 따라 달라지는 값을 반환해 그만큼 칸을 건너뛰게 합니다.

 

- Separate Chaining

 

4. 체이닝 Chaining

앞의 세 가지 방법은 모두 충돌을 피해 다른 칸에 데이터를 저장합니다. 반면, 체이닝은 같은 칸에 데이터를 저장하되 연결리스트를 사용해 충돌을 피합니다. 탐색할 때 연결 리스트를 다 탐색해야 하는 것이 단점이지만, 메모리와 수행 시간 면에서 효율적입니다.

 

구현

C

- 연결 리스트로 테이블 만들기

- 해시 함수 선언

 

JAVA

- HashMap 사용하기 => separate chaining 사용됨

https://codechacha.com/ko/java-map-hashmap/

Java - HashMap 사용 방법 및 예제

 

좋은 해시 함수는 키 전체를 참조하여 해시 값을 만들어 냅니다.

해시 함수는 보안 분야에서 중요한 역할을 하고 있는데, 암호화를 할 때 길이를 줄이거나, 늘리는 등 대상을 변형해 해독하기 어렵게 합니다.

 

 

참고자료

윤성우 (2012). 윤성우의 열혈 C 자료구조

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

https://bcho.tistory.com/1072

Hashtable의 이해와 구현 #1