해시 테이블 (Hash Table)

해싱과 해시함수 그리고 해시 테이블

 

해시함수(Hash Function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다. 이 때 매핑 전 원래 데이터의 값을 키(Key), 매핑 후 데이터의 값을 해시값(Hash Value), 매핑하는 과정 자체를 해싱(Hashing)이라고 한다.

 

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시 함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색, 삭제하게 된다.

해시 함수(Hash Function)의 역할

 

해시 함수는 임의의 길이를 갖는 메세지를 입력받아서 고정된 길이의 해시값을 출력하는 함수를 말한다.

해시 테이블에서 사용되는 대표적인 해시 함수

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

Key와 Value의 구조

Key

Key는 데이터의 저장 위치를 결정하는 주소

• 고유성 : 하나의 해시 테이블 안에서 Key는 절대 중복될 수 없다. 만약 이미 존재하는 Key로 새로운 Value를 넣는다면 기존 Value는 지워지고 새로운 Value로 덮어씌워지게 된다.
• 불변성 : 해시 테이블의 핵심은 Key값이 변하지 않아야 index를 똑같게 구할 수 있다는 것이다. 파이썬의 경우는 str, int, tuple처럼 Immutable 타입만 Key가 될 수 있다. 리스트나 딕셔너리는 Key로 쓸 수 없다.

Value

Value는 저장하고 싶은 실제 정보

• 자유로움 : Key와 달리 제약이 없다. 중복도 상관없고, 타입도 가리지 않는다.
• 수동성 : Value 자체로는 해시 테이블 내에서 아무런 역할을 할 수 없다. Key가 없다면 Value는 반환될 수 없다.

키(Key)         해시 함수 + 나머지 연산         실제 메모리 배열 (Buckets)
+--------+                                     +----------------------------------+
| 김사과 | ----> [ Hash Function ] ----> [0]   | 인덱스 [0]: ("김사과", "apple")   |
+--------+                                     +----------------------------------+
| 이메론 | ----> [ Hash Function ] ----> [4]   | 인덱스 [1]: 빈 방 (None)          |
+--------+                                     +----------------------------------+
| 반하나 | ----> [ Hash Function ] ----> [2]   | 인덱스 [2]: ("반하나", "banana" ) |
+--------+                                     +----------------------------------+
                                               | 인덱스 [3]: 빈 방 (None)          |
                                               +----------------------------------+
                                               | 인덱스 [4]: ("이메론", "melon")   |
                                               +----------------------------------+

충돌 (Collision)이 발생하는 이유

 

해시 함수가 서로 다른 입력 값에 대해 동일한 해시 테이블 주소를 반환하는 것을 일컫어 '충돌(Collision)'이라고 한다.

어떤 해시 함수든, 그 알고리즘이 아무리 정교하게 설계되었다 하더라도 모든 입력 값에 대해 고유한 해시 값을 만들지 못한다.

무한한 종류의 Key를 유한한 크기의 테이블 인덱스로 압축하다보니, 확률적으로 같은 인덱스를 배정받는 충돌이 일어날 수 밖에 없다.

class HashTable:
    def __init__(self):
        self.size = 5
        self.table = [[] for _ in range(self.size)]     # 5개의 비어있는 리스트 생성 (버킷 생성)

    def put(self, key, value):
        bucket_number = key % self.size                 # key를 5로 나눈 나머지로 버킷 번호 계산


        for pair in self.table[bucket_number]:          # 버킷에 같은 key 확인
            if pair[0] == key:
                print(f'[{key}] 키가 이미 존재. 데이터를 업데이트 합니다.')
                pair[1] = value                         # 값 업데이트
                return

        if len(self.table[bucket_number]) > 0:          # 버킷에 같은 key가 있다면 충돌 발생
            print(f'{value} 충돌 이미 데이터가 있습니다.')

        self.table[bucket_number].append([key,value])   # 새로운 데이터면 버킷에 추가


test_table = HashTable()

print("----- 최종 해시 테이블 상태 -----")
for i, bucket in enumerate(test_table.table):
    print(f"{i}번 버킷 : {bucket}")

test_table.put(0, 'apple')
test_table.put(1, 'banana')
test_table.put(2, 'melon')
test_table.put(6, 'orange')     # 충돌 발생
test_table.put(1, 'cherry')     # 값 업데이트 발생

print("----- 최종 해시 테이블 상태 -----")
for i, bucket in enumerate(test_table.table):
    print(f"{i}번 버킷 : {bucket}")

----- 최종 해시 테이블 상태 -----
0번 버킷 : []
1번 버킷 : []
2번 버킷 : []
3번 버킷 : []
4번 버킷 : []

orange 충돌 이미 데이터가 있습니다.
[1] 키가 이미 존재. 데이터를 업데이트 합니다.
----- 최종 해시 테이블 상태 -----
0번 버킷 : [[0, 'apple']]
1번 버킷 : [[1, 'cherry'], [6, 'orange']]
2번 버킷 : [[2, 'melon']]
3번 버킷 : []
4번 버킷 : []

충돌 해결 방법

체이닝 (Chaining)

체이닝(Chaining)은 해시 함수로 서로 다른 키에 대해 같은 주소값을 반환해서 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 기법이다. 충돌이 일어나면 링크드 리스트에 사슬처럼 주렁주렁 엮는다는 의미에서 붙여진 이름이다. 체이닝 기반의 해시 테이블은 데이터 대신 링크드 리스트에 대한 포인터를 관리한다. 체이닝은 오픈 해싱 기법인 동시에 폐쇠 주소법(Closed Addressing) 알고리즘이기도 하다.

• 충돌이 나면 같은 버킷의 데이터를 Linked List 형태로 저장하는 방식.
• 테이블을 늘릴 필요 없이 링크만 추가하면 되므로 직관적이지만, 한번에 데이터가 많이 몰리면 검색 속도가 느려질 수 있다.

체이닝 (Chaining)

체이닝 기반 해시 테이블의 탐색

• 찾고자 하는 목표값을 해싱하여 링크드 리스트가 저장되어 있는 주소를 찾는다.
• 이 주소를 이용하여 해시 테이블에 저장되어 있는 링크드 리스트에 대한 포인터를 생성한다.
• 링크드 리스트의 앞에서부터 뒤까지 차례대로 이동하며 목표값이 저장되어 있는지 비교한다. 목표값과 링크드 리스트 내의 노드 값이 일치하면 해당 노드의 주소를 반환한다.

개방 주소법 (Open Addressing)

개방 주소법(Open Addressing)은 충돌이 일어날 때 해시 함수에 의해 얻어진 주소가 아니더라도 얼마든지 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘이다. 개방 주소법은 충돌이 일어나면 해시 테이블 내의 새로운 주소를 탐사(Probe)하여 충돌된 데이터를 입력하는 방식으로 동작한다.

 

선형 탐색

 

선형 탐색(Linear Probing)은 가장 간단한 탐사 방법이다. 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있음을 발견하면, 현재 주소에서 고정 폭으로 다음 주소로 이동한다. 그 주소에 다른 데이터가 있어 충돌이 또 발생한다면 또 다시 그 다음 주소로 이동한다. 이렇게 해서 비어 있는 주소를 찾아내면 데이터를 입력한다.

55가 입력될 때 충돌이 발생하면 고정된 폭만큼 이동하면서 빈 주소를 찾는다.

 

빈 주소를 찾았다면 데이터를 입력한다.

제곱 탐색

 

제곱 탐색(Quadratic Probing)의 기본 개념은 선형 탐사와 비교해서 크게 다르지 않다. 선형 탐사가 다음 주소를 위해 고정폭만큼 이동하는 것에 비해 제곱 탐색은 이동폭이 제곱수로 늘어나는것 뿐이다.

충돌 발생 시 1^2, 2^2, 3^2 만큼 이동해가면서 빈 공간을 찾는다.

이중 해싱

 

이중 해싱(Double Hashing)은 탐사할 해시값의 규칙성을 없애버려서 클러스터링(해시 테이블의 특정 부분에 데이터가 몰리는 상황)을 방지하는 기법이다. 2개의 해시 함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다. 이렇게 되면 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 클러스터링을 완화할 수 있다.

 

리해싱

 

남은 공간이 없는 해시 테이블에서 충돌이 많이 발생하게 된다. 리해싱(Rehashing)은 이 문제를 해결하고자 해시 테이블의 크기 자체를 늘려서 늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱한다.

해시 테이블의 크기를 늘려 전체 데이터를 다시 해싱하는 기법

파이썬 Dictionary와 해시 테이블

 

자료 조사를 하면서 해시 테이블의 생김새나 기능이 파이썬의 Dictionary와 유사하다는 느낌을 많이 받았다. 그래서 찾아보니 파이썬의 Dictionary는 해시 테이블로 구현된 내장 자료구조라는 걸 알게되었다.

파이썬은 해시 테이블을 딕셔너리에 적용하면서 몇 가지 고유한 방식을 사용한다.

• 빠른 속도와 공간의 교환 : 키-값 쌍을 저장할 때 여유 공간(메모리)을 미리 할당해 탐색 시간을 줄인다.
• 해시 충돌 처리 : 서로 다른 키가 해시 함수를 거쳐 같은 같은 인덱스를 가리키는 해시 충돌이 발생하면, 파이썬은 다른 빈 공간을 탐색하여 데이터를 넣는 개방 주소법 중 선형 탐색 방법과 리해싱을 사용한다.
• 동적 크기 조절 : 테이블의 공간 일정 수준(약 2/3) 이상 차오르면, 자동으로 테이블 크기를 두 배로 늘리고 모든 데이터를 다시 해싱하여 재배치한다.(Rehashing)

해시 테이블의 장점과 단점

장점	단점
검색 및 접근 속도 : 키를 해시 함수를 통해 인덱스로 변환하므로, 평균 O(1)의 시간 복잡도로 데이터의 겁색, 삽입, 삭제가 가능	해시 충돌 : 서로 다른 키가 해시 함수를 거쳐 같은 인덱스를 가리키는 현상이 발생할 수 있다. 이 경우 체이닝이나 개방 주소법 등을 통해 해결해야 하며, 충돌이 잦아지면 성능이 O(N)으로 떨어진다.
키 중심의 데이터 관리 : 중복되지 않는 고유한 키를 통해 데이터를 다루기 때문에 직관적이고 관리가 편하다.	데이터 순서 미보장 : 데이터를 저장하는 인덱스가 해시 함수에 의해 무작위로 결정되므로, 데이터 간의 정렬이나 순차적 접근이 필요한 상황에는 적합하지 않다.
효율적인 중복 확인 : 특정 데이터가 이미 존재하는지 (중복 검사) 빠르게 확인할 수 있다.	공간 낭비 : 성능 저하를 방지하기 위해 데이터가 채워지기 전부터 미리 빈 메모리 공간(버킷)을 확보해 두어야 하므로 메모리 효율성이 떨어진다.
	해시 함수 의존도 : 해시 함수의 성능이 테이블 전체의 성능을 좌우한다. 함수가 복잡하면 해시 값을 계산하는데 시간이 더 소요된다.

해시 테이블의 실제 사용

• 데이터베이스 인덱싱 : 방대한 회원 정보 중 ID로 회원을 검색할 때 사용된다.
• 캐싱 : 웹 브라우저나 서버가 자주 찾는 이미지 / 데이터를 URL(Key)과 파일(Value) 형태로 저장해 두고 빠르게 꺼내 쓸 때 사용된다.
• 블록체인 및 암호화: 사용자의 비밀번호를 해시화해서 안전하게 저장하거나 데이터 위변조를 막을 때 사용된다.
• 라우팅 테이블 : 네트워크 라우터 안에는 목적지 IP 주소(Key)와 데이터를 보낼 다음 목적지 패킷 경로(Value)를 짝지어 놓은 '라우팅 테이블'에 사용된다.
• 컴파일러 및 인터프리터의 심볼 테이블 : 프로그래밍 언어를 실행 파일로 컴파일하거나 해석할 때, 컴퓨터는 사용자가 선언한 변수와 함수를 기억해야한다. 이때, 컴퓨터는 코드를 읽으면서 변수 이름(Key)과 그 변수가 메모리 어디에 위치해 있는지 혹은 어떤 값인지(Value)를 해시 테이블 형태인 심볼 테이블에 기록해 둔다.
• 데이터베이스의 해시 조인 : 대용량 데이터베이스에서 두 개의 거대한 테이블을 서로 연결(Join)하여 데이터를 뽑아내야 할 때 해시 테이블이 사용된다. 한쪽 테이블의 열(Column)을 기준으로 메모리에 해시 테이블을 먼저 빌드하고 반대쪽 테이블을 훑으면서 매칭되는 데이터가 있는지 탐색(Probe)하는 방식을 사용한다.
• 게임 및 그래픽스의 공간 분할 : 오픈월드 게임이나 수많은 유닛이 등장하는 게임에서 캐릭터 간의 충돌을 계산할 때 해시 테이블이 사용된다. 맵 전체 화면을 바둑판 모양의 격자로 나누고, 각 격자의 좌표(Key)에 현재 그 자리에 있는 유닛 리스트(Value)를 해시 테이블로 관리한다. 내 캐릭터가 공격할 때 맵 전체를 다 조사하는 것이 아니라, 캐릭터가 서 있는 격자 좌표(Key) 주변만 해시 테이블에서 확인하므로 게임이 끊기지 않고 부드럽게 돌아간다.