Hash Table Algorithm

1. 해쉬 구조

Hash Table : Key , Value 로 구성됨. 파이썬에서는 딕셔너리라는 이름으로 구현 되어 있음.딕셔너리가 없는 언어에서의 구현 순서

1. 배열로 hashTable 생성.
2. hashFunc(key) -> hashValueaddressFunc(hashvalue) -> hashAddress
3. 저장기능 , 읽기기능 구현

• 함수로 구현

# 1. 배열로 hashTable 생성.
hash_table = [0 for i in range(10)]

# 2. hashFunc(key) -> hashTableIndex
def hash_func(key):
    hashValue=ord(key) # 여기서는 ord()가 hashFunc
    hashAdress = hashValue%10 # 여기서는 나머지연산이 addressFunc
    return hashAdress

# 3. 저장기능 , 읽기기능 구현 
def save_data(key,value):
    idx=hash_func(key)
    hash_table[idx]=value
def read_data(key):
    idx = hash_func(key)
    return hash_table[idx]

Hash Table의 장점 및 단점은 ?

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

list의 어떤 자료를 검색할 때 드는 시간복잡도 O(n)Hash Table의 자료를 검색할 때 드는 시간복잡도 O(1)

충돌 해결

1. Chaining 기법 (개방 Hashing , Open Hashing)

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

hash_table = [0 for i in range(10)]
def hash_func(key):
    hashValue=ord(key)
    hashAddress = hashValue%10
    return hashAddress

def save_data(key, value):
    hashAddress = hash_func(key)
    if hash_table[hashAddress] != 0:
        for index in range(len(hash_table[hashAddress])):
            if hash_table[hashAddress][index][0] == key:
                hash_table[hash_address][index][1] = value
                return #기존의 존재하는 key의 value를 재입력하는 상황 
        hash_table[hash_address].append([key, value])
    else:
        hash_table[hash_address] = [[key, value]]
        # 오픈해슁은 3차원 hash_table을 가진다. 

def read_data(key):
    hashAddress = hash_function(key)
    if hash_table[hashAddress] != 0:
        for index in range(len(hash_table[hashAddress])):
            if hash_table[hashAddress][index][0] == key:
                return hash_table[hashAddress][index][1]
        return None
    else:
        return None

2. Linear Probing

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

hash_table = [0 for i in range(8)]
def hash_func(key):
    hashValue=ord(key)
    hashAddress = hashValue%10
    return hashAddress

def save_data(key, value):
    hashAddress = hash_func(key)
    if hash_table[hashAddress] != 0:
        for index in range(hashAddress, len(hash_table)):
            if hash_table[index] == 0:
                hash_table[index] = [key, value]
                return
            elif hash_table[index][0] == key:
                hash_table[index][1] = value
                return
    else:
        hash_table[hashAddress] = [key, value]

def read_data(key):
    hashAddress = hash_func(key)
    if hash_table[hashAddress] != 0:
        for index in range(hashAddress, len(hash_table)):
            if hash_table[index] == 0:
                return None
            elif hash_table[index][0] == key:
                return hash_table[index][1]
    else:
        return None

• 출처 : https://wikidocs.net/154782