[자료구조] hash table(해시 테이블) python class 구현하기

[자료구조] hash table(해시 테이블) python class 구현하기

 

 

 

살펴볼 주요 개념:

- 해시 테이블의 개념, 특징, 용도

- 해시 함수

- 해시 충돌 회피

- 해시 테이블 클래스 구현(python)

1. 해시 테이블의 개념, 용도, 중요 요소

(1) 해시 테이블의 개념

 

: 해시 테이블이란 키값에 데이터를 저장하는 데이터 구조이다. key를 통해 데이터(value)를 받아올 수 있으므로 삽입, 삭제, 탐색 연산이 획기적으로 빨라진다. 파이썬에서는 딕셔너리 타입이 해시 테이블의 특징을 가지고 있다.

출처 : https://velog.io/@2seunghye/파이썬과-자료구조해쉬-테이블

: 해시 테이블은 테이블 사이즈 만큼 배열을 생성하여 사용한다. 특정한 함수(해시 함수)를 통해 key를 인덱스로 mapping을 하고, 테이블 내의 공간에 데이터를 저장하는 것이다.

 

: 파이썬에서는 해시를 구현할 필요는 없다. 딕셔너리가 곧 해시 테이블이기 때문이다.

 

 

(2) 해시 테이블의 용도

 

: 데이터 검색이 많이 필요한 경우에 자주 사용한다.

: 저장, 삭제, 읽기가 빈번한 경우에 많이 사용한다.

: 캐시를 직접 구현할 경우 중복확인이 쉽기 때문에 많이 사용한다.

 

 

(3) 중요 요소

 

: Table(테이블, 데이터 저장 장소)

: Hash function(해시 함수)

: Collision resolution method(해시 함수 충돌 회피)

 

2. 해시 함수(Hash function)

 

(1) 정의

 

특정 key에 대해 산술 연산을 이용해서 데이터의 인덱스를 찾을 수 있는 함수를 의미한다.

예를 들어,

## pseudo code

hash_table = [None for i in range (10)] # 10개의 데이터 저장 공간
func(key) = key % len(hash_table) # 해시 함수
hash_table[func(3)] = 3 # 해시 함수를 통해 얻어진 인덱스 3의 공간에 3을 저장

이런 식으로 키값이 해시 함수를 거쳐서 어떤 숫자를 만들어내게 되고, 해시 테이블의 특정한 인덱스에 데이터 값을 저장할 수 있게 되는 것이다.

 

그러나 이런 경우, 해시 함수를 통해 얻어진 값이 동일한 경우가 많이 일어난다. 위의 함수의 경우, 나머지가 0~9인 경우는 너무나 많기 때문이다. 그래서 하나의 key 값에 하나의 value만 매칭시킬 수 없는 경우가 많다. 이를 '해시 함수 충돌'이라고 한다.

 

 

(2) 좋은 해시 함수

 

이상적인 해시 함수는 key의 개수와 slot(한 개의 데이터를 저장할 수 있는 table 공간) 개수가 같고, 충돌을 일으키지 않는 특징을 가질 것이다. 그러나, 이는 이상적인 것에 불과하며, 현실로는 실현해내기 어려운 것이다.

 

현실적인 좋은 해시 함수의 기준은

 

1) less collision(적은 충돌) / 2) fast computation(빠른 연산)

두 가지 조건을 충족하면 된다.

 

이 두 가지는 거래관계에 있는 것으로 충돌이 적게 일어나면 연산을 많이 요할 수 있고,

빠른 연산이 되면 충돌이 비교적 많이 일어날 수 있다.

 

 

(3) 해시 함수의 종류

해시 함수의 여러 종류
Division	Extraction
Multiplitcation	Addtive
Folding	Rotation
Mid-squares	Universal

등등... 많다.

 

 

3. 해시 충돌 회피

두 가지의 방법이 있다.

- Open Addressing : 데이터를 주위의 빈 슬롯에 삽입하는 방법

- Chaining(Close Addressing) : 각 슬롯 당 한 방향 연결리스트를 만들어 저장하는 방법

 

(1) Open Addressing (python, ruby 활용)

 

해시 충돌이 일어나면, 다른 비어있는 해시 버킷에 해당 자료를 삽입한다. 남은 버킷의 용량이 적을 경우에는 효율이 떨어질 수 있다.

해시 테이블 내에 데이터가 연속적으로 군집하고 있는 것을 클러스터라고 하는데, 클러스터는 되도록 작을 수록 성능이 좋다.

 

linear probing : 충돌이 일어나면 바로 밑의 슬롯에 데이터를 저장

gurdratic probing : 2차 함수를 이용하여 탐색할 위치를 찾음

double hashing probing : 하나의 해시 함수에서 충돌이 발생하면 2차 해시함수를 이용해 새 주소 할당

 

 

(2) Chaining (C++, java 활용)

 

별도의 자료구조를 버킷에 덧붙이는 방식이다.

 

 

Linked List 활용 : 버킷들을 연결리스트로 만들어서 충돌 발생 시 해당 버킷에 노드를 추가해주는 방법이다.

Red-Black Tree 활용 : 버킷에 저장된 데이터가 많을 수록 연결 리스트의 순차 접근 방식이 비효율 적이기에 이진 트리구조를 활용하여 O(logN)시간으로 복잡도를 낮추는 방법이다.

 

4. 해시 테이블 클래스 구현(python)

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

print(get_key('dk898')) # 7304751607806598621

def hash_func(key):
    return key % 8


def save_data(data, value):
    hash_address = hash_func(get_key(data))
    hash_table[hash_address] = value


def read_data(data):
    hash_address = hash_func(get_key(data))
    print(hash_address)
    print(hash_table[hash_address])



save_data('dk898', 'gold') 
save_data('dh227', 'silver') 

read_data('dk898') # 5 # gold
read_data('dh227') # 0 # silver

print(hash_table) # ['silver', 0, 0, 0, 0, 0, 'gold', 0]

기본적으로 구현을 하면 위와 같다. 8개의 슬롯을 가진 테이블을 만들고, 해시 값을 생성한 다음, 해시 함수를 통해 인덱스 값을 만들어서 각각 데이터를 저장하거나 읽는 메소드를 추가하면 아래와 같이 해시 테이블 활용이 가능하다.

 

 

해시 충돌 회피를 위에서는 쓰지 않았는데, save_data 메소드와 read_data 메소드를 수정, 발전 시키면 다음과 같다.

같은 키 값을 가지고 있다면, 

def save_data(data, value):
    index_key = get_key(data) # index_key 추가
    hash_address = hash_func(index_key) # 해싱 함수에 index_key 대입

	## 인덱스 키를 활용해서 이차원 배열을 만들어 다음 노드로 삼을 수 있게 하는 것.
    
    if hash_table[hash_address] != 0: # 해쉬 테이블 슬롯에 기존 데이터가 있으면
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return
        hash_table[hash_address].append([index_key], value)
    else:
        hash_table[hash_address] = [[index_key, value]]


def read_data(data):
    index_key = get_key(data)
    hash_address = hash_func(index_key)

    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                print(hash_table[hash_address][index][1])
        return None
    else:
        return None