Hash Table(해쉬 테이블)의 구현

Hash Table(해쉬 테이블)

Introduction

• 테이블에 저장되는 데이터는 Key와 Value가 한 쌍을 이룸
• Key가 존재하는 Value는 저장할 수 없으며, 모든 key는 중복되지 않음
• 좋은 해쉬 함수는 '충돌을 덜 일으키는 해쉬 함수'
• 일반적인 해쉬 함수(remainder method)의 개선안
  1. 자릿수 폴딩(Folding Method): 자릿수를 균등한 조각으로 나누어 각각의 값을 더한 후, 그 값의 remainder를 key값으로 설정
     • ex) 436-555-4601이라는 값을 두 자리로 쪼깨어 더함
     • 43 + 65 + 55 + 46 + 01 = 210
     • 210 % 11 = 1으로 1의 key값을 가지게 됨
     • 각각의 조각을 reverse하여 더하는 folding method도 존재
       • ex) 43 + 56 + 55 + 64 + 01 = 219
  2. 중간 제곱법(Mid-Square Method): Value를 제곱한 후 가운데 값의 remainder를 key값으로 설정
     • ex) 44 ^ 2 = 1,936
     • 93 % 11 = 5로 5의 key값을 가지게 됨
  3. Ordinal Value의 활용: 문자열을 구성하는 각각의 문자의 ASCII 값을 모두 더해 나온 결과의 remainder를 key 값으로 설정하는 방법
     • ex) 'cat' = 99 + 97 + 116 = 312
     • 312 % 11 = 4로 4의 key값을 지니게 됨
     • 그러나 이는 anagram의 단어들이 모두 같은 값을 지니게 된다는 단점이 있음
       • 해결 방안: weighting factor의 추가
       • 'cat' = 99*1 + 97*2 + 116*3
• 충돌 문제의 해결안

• Open Addressing: 해쉬 테이블에서 다음 open된 slot을 찾는 방법

  1. 선형 조사법(Linear Probing): hash function에 의해 저장되어야 하는 slot의 다음 slot들을 차례로 확인하며 빈 slot을 찾아가는 방법
     • ex) 77, 44, 55는 모두 0번 index에 들어가야 하는 value들
     • 그러나 77이 0번 index를 차지하고 있기 때문에 44는 1번 index에, 55는 0, 1번 index가 꽉찬 것을 확인하고 비어있는 2번 index에 저장하는 방법
     • 선형 조사법의 단점은 Clustering이 생긴다는 것
       • 즉, slot들을 골고루 사용하는 것이 아닌 특정 지역의 slot들만 과도하게 사용되는 경향이 생김
  2. 이차 조사법(Quadratic Probing): hash function에 의해 저장되어야 하는 slot 위치에 + 1, + 4, + 9 등을 더해 slot들이 고르게 분배되도록 하는 방법
     • ex) 77, 44, 55의 value들을 저장해야 함
     • 77은 0번 index에 44는 0 + 1으로 1번 index에 그리고 55는 0 + 4로 4번 index에 저장시키게 됨

• Close Addressing(Chaining): 각각의 slot에 item들이 여러 개 저장될 수 있도록 구현하는 방법

• http://blog.chapagain.com.np/hash-table-implementation-in-python-data-structures-algorithms/ 

해쉬 테이블 구현에 필요한 기본 연산

• HashTable(): 새로운 HashTable을 생성
• put(key, val): key와 value을 쌍으로 HashTable에 추가함. Key 값이 이미 존재하면 old value를 new value로 변경
• get(key): key가 주어지면 그에 맞는 value값을 반환
• del: Key 값을 이용하여 Key-Value 쌍을 삭제
• len(): Key-Value 쌍의 크기 반환
• in: HashTable에 Key 값이 있는지의 여부를 반환

해쉬 테이블의 로직

class HashTable:
	def __init__(self):
		self.size = 11
		self.slots = [None] * self.size
		self.data = [None] * self.size

• Key 값들을 담는 slots라는 list 생성
• slots라는 list와 평행하게 존재하며, value를 담을 data list 생성
• HashTable의 크기는 소수로 설정하는 것이 충돌 문제 해결에 효과적

def put(self, key, value):
	hashval = self.hashfunction(key, len(self.slots))

	if self.slots[hashvalue] == None:
		self.slot[hashvalue] = key
		self.data[hashvalue] = data

	else:
		# original key값이 같을 경우 replace
		if self.slots[hashvalue] == key:
			self.data[hashvalue] = data
		else:
			nextslot = self.rehash(hashvalue, len(self.slots))
			# slot이 차있고, original key값과 rehash 값이 다르면 계속 rehash
			while self.slots[nextslot] != None and \
							self.slots[nextslot] != key:
				nextslot = self.rehash(nextslot, len(self.slots))
		
			# slot이 비어있으면 slot에 key와 data 입력
			if self.slots[nextslot] == None:
				self.slots[nextslot] = key
				self.data[nextslot] = data

			# rehash 값과 original key 값이 같을 경우 replace
			# 즉, rehash 통해 이미 자리한 경우
			else:
				self.data[nextslot] = data

def hashfunction(self, key, size):
	return key % size

# Linear Probing 사용
def rehash(self, oldhash, size):
	return (oldhash+1) % size

• nextslot의 rehash를 탈출하는 조건은 2가지로 분류
  1. rehash를 통해 얻은 slot이 비어있는 경우: 빈 자리에 key와 data를 삽입
  2. rehash를 통해 얻은 slot의 key값과 입력 값의 key 값이 같은 경우: value를 replace
• rehash function으로는 Linear Probing 사용

def get(self, key):
	startslot = self.hashfunction(key, len(self.slot))

	data = None
	stop = False
	found = False
	position = startslot

	while self.slots[position] != None and
					not found and not stop:
		# 값을 찾은 경우 while문 탈출
		if self.slots[position] == key:
			found = True
			data = self.data[position]
		else:
			position = self.rehash(position, len(self.slots))
			# 최초의 slot으로 돌아오지 않도록 제어
			if poisition == startslot:
				stop = True

	return data

def __getitem__(self, key):
	return self.get(key)

def __setitem__(self, key, data):
	self.put(key, data)

• position의 rehash를 탈출하는 조건은 3가지로 분류
  1. rehash를 통해 얻은 position 값이 입력 값의 key 값과 일치하는 경우: 검색에 성공한 case
  2. rehash를 통해 얻는 position 값이 hashfucntion으로 얻은 값과 일치하는 경우: 원값으로 돌아올 때 까지 탐색에 실패한 case
  3. rehash를 통해 얻은 position 값의 slot이 비어있는 경우: Linear Search를 하다가 값이 존재하지 않는 case
• [] 연산의 사용을 위해 __getitem__과 __setitem__ method를 overloading

전체 코드

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size
 
 
    def put(self, key, data):
        hashvalue = self.hashfunc(key, len(self.slots))
 
        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        else:
            if self.slots[hashvalue] == key:
                self.data[hashvalue] = data
            else:
                nextslot = self.rehash(hashvalue, len(self.slots))
                while self.slots[nextslot] != None and \
                                self.slots[nextslot] != key:
                    nextslot = self.rehash(nextslot, len(self.slots))
 
                if self.slots[nextslot] == None:
                    self.slots[nextslot] = key
                    self.data[nextslot] = data
                else:
                    self.data[nextslot] = data
 
 
    def hashfunc(self, key, size):
        return key % size
 
 
    def rehash(self, oldhash, size):
        return (oldhash+1) % size    
 
 
    def get(self, key):
        startslot = self.hashfunc(key, len(self.slots))
 
        data = None
        stop = False
        found = False
        position = startslot
        while self.slots[position] != None and \
                            not found and not stop:
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            else:
                position = self.rehash(position, len(self.slots))
                if position == startslot:
                    stop = True
        return data
 
 
    def __getitem__(self, key):
        return self.get(key)
 
 
    def __setitem__(self, key, data):
        self.put(key, data)

[Reference]
Problem Solving with Algorithms and Data Structure
윤성우의 열혈 자료구조