[자료구조] 해시(Hash) 2
in Study on Data Structure
해시 테이블에서 충돌을 피하려면?
키(Key) 값을 통해서 데이터를 저장하는 해시 테이블. 검색속도가 빠르고 저장과 삭제가 편하다는 장점이 있지만, 같은 키 내에 다른 데이터(혹은 Value)를 저장할 수 없기 때문에 키 값이 같으면 충돌이 일어나버린다.
그렇다면 필요한 것은 충돌이 일어나지 않도록 코드를 추가하는 것이다.
이러한 기법으로 두 가지를 배웠는데 아래와 같다.
- Chaining (Open Hashing)
- 충돌이 일어나면 먼저 들어간 값에 링크를 연결하여 링크드리스트를 형성하는 기법
- Close Hashing (Linear Probing, Open Addressing)
- 키 값이 같으면 먼저 들어온 값을 저장한 후, 뒤 쪽에서 빈 공간을 찾아 나중에 들어온 값을 저장하는 기법
- 키 값이 같으면 먼저 들어온 값을 저장한 후, 뒤 쪽에서 빈 공간을 찾아 나중에 들어온 값을 저장하는 기법
이번 포스팅에선 Chaining (Open Hashing)기법에 대해서 포스팅해보고자 한다.
Chaining (Open Hashing)
Key 값이 중복되면, 먼저 저장한 값에서 나중에 저장할 값으로 링크를 걸어 링크드리스트를 형성하는 기법이다.
코드로 구현하기
table = [0 for i in range(8)]
def get_key(data):
return hash(data)
def hash_func(key):
return key % len(table)
def get_address(key):
index_key = get_key(key)
hash_address = hash_func(index_key)
return hash_address
1편에서 썼던 코드 중 일부를 바꿔보면, table의 길이를 8로 바꾸고, python 자체에 내장된 hash함수를 써보기로 했다.
그리고 hash_func(key)에서도 table의 길이에 따라서 해시 함수가 작동하도록 len(table)을 설정했다. 단, len(table)변수는 새로운 table을 형성할 때 마다 일일이 다른 변수를 쓸 필요가 없도록 하기 위함이다. 기존에 있던 table의 길이가 도중에 바뀌어버리면 저장과 읽기에 오류가 생길 수 있다.
또한, 저장하는 과정과 찾는 과정에서 중복코드가 많기 때문에 중복되는 부분을 위와 같이 로컬함수로 빼내었다.
class table:
def __init__(self, table_len):
self.len = table_len
self.hash_table = [0 for i in range(table_len)]
def get_key(self, data):
return hash(data)
def hash_func(self, key):
return key % self.len
def get_address(self, key):
index_key = self.get_key(key)
hash_address = self.hash_func(index_key)
return hash_address
어.. 그리고보니 그러면 이렇게 클래스로 하면 더 이쁘겠다.
######### 데이터 추가 코드 ###########
def save_data(self, key, value):
hash_address = self.get_address(key)
if self.hash_table[hash_address] != 0:
# 해당 주소에 데이터가 이미 저장되어 있다면?
for index in range(len(self.hash_table[hash_address])):
if self.hash_table[hash_address][index][0] == key:
self.hash_table[hash_address][index][1] = value
# 완벽하게 동일한 키에 다른 값을 저장하지는 못하므로 값을 덮어 씌움.
# dict = {'아야': 1, '라라' : 2} 라는 딕셔너리에서
# ditc['아야'] = 3 을 실행하는 것과 같은 이치.
# 결과는 dict = {'아야' : 3, '라라' : 2}
return
self.table[hash_address].append([key, value])
# 그래도 키가 완벽하게 동일하지 않다면 같은 분류에 값을 추가함.
else:
self.hash_table[hash_address] = [[key, value]]
# 해당 주소에 데이터가 저장되어 있지 않고 비어있다면 키와 값을 새로 저장함.
return
######### 데이터 읽기 코드 ###########
def get_data(self, key):
hash_address = self.get_address(key)
if self.hash_table[hash_address] != 0:
for index in range(len(self.hash_table[hash_address])):
if self.hash_table[hash_address][index][0] == key:
return self.hash_table[hash_address][index][1]
return
else:
return
######### 데이터 삭제 코드 ###########
def delete_data(self, key):
hash_address = self.get_address(key)
if self.hash_table[hash_address] != 0:
for index in range(len(self.hash_table[hash_address])):
if self.hash_table[hash_address][index][0] == key:
if len(self.hash_table[hash_address]) == 1:
self.hash_table[hash_address] = 0
else:
del self.hash_table[hash_address][index]
return
print('해당 키 없음.')
return
else:
print('해당 키 없음.')
return
Chaining 기법에서 데이터를 저장, 읽기, 삭제하는 파이썬 코드이다.
save_data(key, value)에서 key 값과 저장할 데이터 값을 받은 후, 동일한 키가 있는지 판별한 후에 값을 저장, 읽기, 삭제한다.
# Test Code
data1 = 'Nyago'
data2 = 'Miko'
data3 = 'Karen'
data4 = 'Nyako'
cats = table(8)
cats.save_data(data1, '0101111####')
print(cats.hash_table)
cats.save_data(data4, '0101234####')
print(cats.hash_table)
print(cats.get_data(data1))
cats.delete_data(data2)
cats.delete_data(data1)
print(cats.get_data(data1))
print(cats.hash_table)
위의 테스트 코드를 실행해보았다.
# 출력 결과
[0, 0, [['Nyago', '0101111####']], 0, 0, 0, 0, 0]
[0, 0, [['Nyago', '0101111####']], [['Nyako', '0101234####']], 0, 0, 0, 0]
0101111####
해당 키 없음.
None
[0, 0, 0, [['Nyako', '0101234####']], 0, 0, 0, 0]
원하는 대로 결과가 잘 출력되었다!
다음 포스팅에선 Close Hashing에 대해서 다루겠다.
3편에서 계속..
