데이터 구조 - 해쉬 테이블(Hash Table)

오늘 배울 것

 1. 해쉬테이블 이란?

 2. 해쉬테이블 관련 용어(구조)

 3. 해쉬테이블의 장단점

 4. 해쉬테이블 충돌을 해결하기 위한 방법

   - Chaining 알고리즘

   - 

 

해쉬테이블

 = key값과 1:1로 연결된 value data를 저장하는 데이터 구조

 = key를 통해 데이터를 받아올 수 있기 때문에, 검색 속도가 획기적으로 빨라짐

 

해쉬테이블 관련 용어(구조)

 1. key = 고유한 값으로 해시함수의 input value이다. 다양한 길이를 가질 수 있음

 2. 해시함수(Hash Function) = key를 hash로 변환하는 역할. 서로 다른 key가 동일한 hash를 가지지 않는 것이 중요

 3. 해시값(Hash value) = 해시함수의 결과물, 고정된 길이를 지니게됨

 

해쉬테이블의 장단점

• 장점
  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움
• 단점
  • 일반적으로 저장공간이 좀더 많이 필요하다. (저장할 데이터 보다는 많은 공간 필요)
  • 만약, 여러 데이터가 공통 키를 가질경우 충돌을 해결하기 위한 별도 자료구조가 필요
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시 (중복 확인이 쉽기 때문)

해쉬테이블 충돌을 해결하기 위한 방법

 

 1. Chaining 알고리즘

• 개방 해슁 또는 Open Hashing 기법 중 하나: 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

hashTable = list([0 for i in range(9)])

def getKey(data):
    return hash(data) # 내재함수"hash"를 활용하여 key값 생성

def hashFunction(key): # key값을 활용하여 hash값 생성
    return key % 8

def save(data, value):
    key = getKey(data)
    address = hashFunction(key)
    if hashTable[address] != 0:
        for index in range(len(hashTable[address])):
            if hashTable[address][index][0] == key:
                hashTable[address][index][1] = value
                return
        hashTable[address].append([key, value])
    else:
        hashTable[address] = [[key, value]]
        
def find(data):
    key = getKey(data)
    address = hashFunction(key)
    if hashTable[address] != 0:
        for index in range(len(hashTable[address])):
            if hashTable[address][index][0] == key:
                return hashTable[address][index][1]
        return None
    else:
        return None

활용 (hash 값이 같은 두 data를 넣었을 때)

save('ks', 'first')
save('db', 'second')
hashTable

결과값 = 3번째에 리스트로 중복된 hash값의 value가 들어간 것을 확인 할 수 있다.

[0,
 0,
 0,
 [[-6312230525200437093, 'first'], [4303847275293549387, 'second']],
 0,
 0,
 0,
 0,
 0]

 

2.  Linear Probing 기법

• 폐쇄 해슁 또는 Close Hashing 기법 중 하나: 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
  • 저장공간 활용도를 높이기 위한 기법

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

def getKey(data):
    return hash(data)

def getHash(key):
    return key % 8

def save(data, value):
    key = getKey(data)
    address = getHash(key)
    if table[address] != 0:
        for index in range(address, len(table)):
            if table[index] == 0:
                table[index] = [key, value]
                return
            elif table[index][0] == key:
                table[index][1] = value
                return
    else:
        table[address] = [key, value] #이부분이 Chaining방법과 다름
        
def find(data):
    key = getKey(data)
    address = getHash(key)
    if table[address] != 0:
        for index in range(address, len(table)):
            if table[index] == 0:
                return None
            elif table[index][0] == key:
                return table[index][1]
    else:
        return None

활용 (hash 값이 같은 두 data를 넣었을 때)

save('Db', '1201023010')
save('Dc', '3301023010')
table

결과값 = 동일한 hash값을 가진 데이터가 기존 저장된 데이터의 바로 다음에 저장된 것을 확인 할 수 있다.

[0,
 0,
 0,
 0,
 0,
 [776271043394594213, '1201023010'],
 [-6007464399106437019, '3301023010'], <---
 0]

활용2 = 다음칸에 이미 데이터가 있을때

save('Db', '1201023010')
table[6] = "aaa"
save('Dc', '3301023010')

결과 = 한칸 떨어진 곳에 저장되는 것을 확인

[0,
 0,
 0,
 0,
 0,
 [776271043394594213, '1201023010'],
 'aaa',
 [-6007464399106437019, '3301023010']] <---

 

3. 기타 방법

• 저장공간을 확대