해시란? (Hash Table)

해시테이블이란?

HashTable(해시테이블)이란?

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.

해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.

해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고,

이 index를 활용해 값을 저장하거나 검색하게 된다.

여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

예를 들어 우리가 (Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자.

그러면 먼저 index = hash_function("John Smith") % 16 연산을 통해 index 값을 계산한다.

그리고 array[index] = "521-1234" 로 전화번호를 저장하게 된다.

이러한 해싱 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로

매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 해시테이블의 평균 시간복잡도는 O(1)이다.

Hash Function (해시 함수)

• 해시함수 : 입력값의 형태는 다양하고, 출력값의 형태는 숫자이다.
  • 해시 함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다.
• 해시함수 요구조건 :
  • 해시함수는 입력값이 같다면, 동일한 출력값을 받아야 한다.
  • 입출력값이 일정하지 않다면 적절한 해시함수가 아니다.
    • 예를 들어, 입력값 'aqua'가 4를 반환한다면, 입력값 'beige'는 4를 반환할 수 없다.
    • 해시함수는 특정 범위 안에 있는 숫자를 반환해야 한다.

해시 테이블에 사용되는 대표적인 해시 함수로는 아래의 4가지가 있다.

1. Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다. ( 주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려져 있다.
2. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multiplication Method: 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다.
   h(k)=(kAmod1) x m
4. Univeral Hashing: 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

해시(Hash)값이 충돌하는 경우

해시(Hash)값이 충돌하는 경우

• 충돌이 적은 해시 함수를 만드는 것이 해시 테이블의 가장 중요한 목적이다

그런데 만약 "John Smith"를 해시 함수를 돌려 나온 값과 "Mang Kyu"를 해시 함수를 돌려 나온 값이 동일하다면 어떻게 해야 할까?

해시 테이블에서는 충돌에 의한 문제를 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 크게 2가지로 해결하고 있다.

 

분리 연결법(Separate Chaining)

Separate Chaining이란 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 위의 그림과 같이 동일한 버킷으로 접근을 한다면 데이터들을 연결을 해서 관리해주고 있다.

 

실제로 Java8의 Hash테이블은 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현하였다.

 

이러한 Chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다.

 

하지만 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.

• 해시 테이블에서 동일한 해시값에 대해 충돌이 일어나면, 그 위치에 있던 버킷에 키값을 뒤이어 연결한다.
• 데이터의 형태는 위 그림처럼 연결리스트의 형태를 갖는다.
  • 해시테이블 방법은 체이닝 방식을 활용한다.
    • 체이닝의 원리
      1. 키의 해시값을 계산한다.
      2. 해시값을 이용해 리스트의 인덱스를 구한다.
      3. 같은 해시값이 있다면(충돌한다면) 리스트로 연결한다.
• 충돌을 줄이기 위해, 각 리스트에 대해 연결(리스트 형태)하도록 한다.
  • 따라서, 특정 해시값에 대해 충돌이 발생해도, 체이닝을 통해 값을 찾을 수 있다.
• 아래 그림과 같이 체이닝으로 충돌상황을 재현하고 해결하는 모습을 구현해볼 수 있다.
  • 체이닝은 연결리스트의 원리를 사용하기 때문에 해시값이 같은 노드를 연결하는 모습을 나타낸다.
  • 아래와 같이 해시값이 인덱스 역할을 한다.(0,1,2,3,...,8)
  • 아래 예시 그림은 나누기방법(division method)을 사용한 것인데, 나누기방법은 쉽기 때문에 많이 사용되는 기본적인 해시함수로서 키값이 정수로 가정된다.
    • 아래 해시함수의 공식은 '키의 값 % 13' 이다.
    • 따라서 매핑되는 해시값(버킷)이 '13으로 나눈 나머지값'을 나타내도록 구성하였다.
    • 해시값 4에서 충돌이 발생되므로 체이닝을 통해 연결시키는 것을 확인할 수 있다

# 체이닝을 예시코드로 배워보자.
# 아래와 같이 리스트안에 중첩되는 리스트를 만들어서 연결개념으로 해시테이블을 생성한다.
chain_hash_table = [[] for _ in range(10)]  # 이번에는 10의 길이로 테스트를 진행한다.(0~9, 총 10개의 인덱스)
print(chain_hash_table)

# 해시함수는 위와 동일하게 테스트할 수 있다.
def chain_hash_func(key):
    return key % len(chain_hash_table)
 
print(chain_hash_func(10)) 
print(chain_hash_func(20)) 
print(chain_hash_func(25))

# append를 활용해서 키-값 쌍을 해시테이블에 삽입한다.
def chain_insert_func(chain_hash_table, key, value):
    hash_key = chain_hash_func(key)
    chain_hash_table[hash_key].append(value)
    
chain_insert_func(chain_hash_table, 10, 'A')
print(chain_hash_table)

chain_insert_func(chain_hash_table, 25, 'B')    # 5번째 인덱스에 B가 삽입된다.
print(chain_hash_table)

# 아래 결과값과 같이 중첩되는 결과값이 있더라도 값이 대체(충돌)되는 것이 아니다.
# 리스트 메소드 개념(list.append)이 활용되어 값을 이어 붙인다.('A' -> 'C')
chain_insert_func(chain_hash_table, 20, 'C')    
print(chain_hash_table)

개방 주소법(Open Addressing) 

🔍 자세히보기 : open addressing은 하나의 bucket에 하나의 entry만 들어갈 수 있는 형태이다.

• 다른 로직의 함수를 활용하기 때문에 open address이라 한다.
  • 이 방법은 비어있는 배열 슬롯이 발견될 때까지 array의 위치를 검색하여 해시 충돌을 해결한다.
  • 충돌이 일어나는 경우, 탐사(Probing)를 진행하면서 빈 공간을 찾아야 해결이 된다.
    • 체이닝과 다르게 저장공간이 정해져있다.

Open Addressing이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.

1. Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
2. Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
3. Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

Open Addressing에서 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되는데, 그렇기 때문에 Hash Table을 재정리 해주는 작업이 필요하다고 한다.

💡 생각하는 시간 : 파이썬과 해시테이블

• 그렇다면 해시테이블로 구현된 파이썬의 자료형은 무엇인가? 딕셔너리이다.
  • 파이썬의 경우 해시테이블 충돌 시 어떤 방식을 통해 해결할까?
  • 체이닝의 경우 연결리스트를 활용하고, 오픈어드레싱은 내부적으로 공간이 어느정도 정해진 배열을 활용하여 설계되어있다.
    • 파이썬의 경우, 내부적으로 오픈어드레싱 방식을 활용한다.
• 파이썬에서 오픈어드레싱을 활용하는 경우 빈 공간이 없는 경우 시간이 오래 걸릴 수 있다.
  • 때문에 로드팩터를 작게 설정하여 성능 저하 문제를 해결한다.
    
    

Load Factor(로드 팩터)

• 로드 팩터는 절대적인 성능측정도구가 아닙니다.
  • 로드 팩터에는 해시테이블의 상황, 입출력의 상황, 메모리에 적재되는 시간 등 영향을 주는 요소가 다양합니다.
  • 로드 팩터에서 발생할 수 있는 상대성을 고려하며 개념을 활용하기 보다 이러한 개념이 있다는 것을 인지해주시길 바랍니다.
  • 로드 팩터에 대한 자세한 내용은 README의 레퍼런스에 첨부하였으니 추가학습을 원하시는 분들은 참고하시면 됩니다.
• 위의 공식처럼 로드 팩터 비율에 따라 해시함수 재작성여부, 해시테이블 크기조정여부가 결정된다.
  • 로드 팩터값을 통해 해시 테이블의 성능정도를 파악할 수 있다.
• 해시 테이블에 저장된 항목 수(해시테이블에 입력된 키 갯수)를 슬롯 수(해시 테이블 전체 인덱스 갯수)로 나눈 값이다.
  • 오픈어드레싱을 사용하면 최대 로드 팩터는 1정도 나온다.
  • **체이닝을 사용하면 로드 팩터는 오픈어드레싱보다 좋은 성능(로드팩터 <= 1)**을 보일 수 있다.
    • 로드팩터를 낮추면 해시에 대한 성능이 올라간다

 

해시 테이블에 대한 다양한 실생활 사례

• 전화 번호부 (사람의 이름을 전화 번호에 매핑)
• DNS 확인 (웹 주소를 IP 주소에 매핑)
• 학생 기록 (고유한 학생 ID가 학생 정보에 매핑)
• 도서관 시스템 (책의 고유 식별자가 자세한 책 정보에 매핑)

좋은 해시함수란?

• 해시함수를 어떻게 구현하는지에 따라 해시의 성능이 결정된다.
  1. 키와 값의 계산과정이 쉬워야 한다.(위에서 설명한 나누기방법처럼 쉬워야 한다.)
  2. 충돌을 피할 수 있어야한다.
  • 계산과정이 쉬운 경우
    • 체이닝(연결리스트)이 제대로 활용된다면 반복작업없이 해시의 검색 알고리즘을 활용하여 O(1)의 검색시간을 확보할 수 있을 것이다.
    • 해시값은 해시되는 데이터에 의해 완전히 결정된다.
    • 해시함수는 모든 입력 데이터를 사용해야 한다.
  • 충돌을 피할 수 있는 경우
    • 해시함수는 가능한 해시값의 전체 집합에 데이터를 균일하게 배포한다.
    • 해시함수는 유사한 문자열에 대해 다른 해시값을 생성한다.
• 해시를 사용할 때 주의할 점
  • 키 데이터타입에 맞는 좋은 해시함수가 있는지 확인
  • 적절한 해시테이블 크기(배열크기)

 

Reference

• 해시테이블의 기본특징
• 로드팩터와 내부구조