- 해시테이블
- Key에 Value 를 저장하는 구조
- 파이썬 dict 해쉬 테이블 예
- 키 값의 연산 결과에 따라 직접 접근이 가능한 구조
- key 값을 해싱함수 -> 해쉬주소 -> key 에 대한 value 참조
# Dict 구조
# print(__builtins__.__dict__)
# Hash 값 확인
t1 = (10, 20, (30, 40, 50))
t2 = (10, 20, [30, 40, 50])
print(hash(t1))
# 오류 발생
print(hash(t2)) # 리스트는 변경가능하므로 해쉬값을 확인 불가능함.
--------------------------------------------[result]
5737367089334957572
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
<ipython-input-3-6c22227c87da> in <module>
7
8 print(hash(t1))
----> 9 print(hash(t2)) # 리스트는 변경가능하므로 해쉬값을 확인 불가능함.
TypeError: unhashable type: 'list'
Dict Setdefault 미사용 예제
# Dict Setdefault 미사용 예제
source = (('k1', 'val1'),
('k1', 'val2'),
('k2', 'val3'),
('k2', 'val4'),
('k2', 'val5'))
new_dict1 = {}
new_dict2 = {}
# No use setdefault
for k, v in source:
if k in new_dict1:
new_dict1[k].append(v)
print('중복키 있음: ', k, v)
else:
new_dict1[k] = [v]
print('중복키 없음')
print(new_dict1)
--------------------------------------------[result]
중복키 없음
중복키 있음: k1 val2
중복키 없음
중복키 있음: k2 val4
중복키 있음: k2 val5
{'k1': ['val1', 'val2'], 'k2': ['val3', 'val4', 'val5']}
Dict Setdefault 사용 예제
# Use setdefault
for k, v in source:
new_dict2.setdefault(k, []).append(v)
print(new_dict2)
--------------------------------------------[result]
{'k1': ['val1', 'val2'], 'k2': ['val3', 'val4', 'val5']}
주의 사항
# 주의, 마지막 값으로 덮어쓰기 됨.
new_dict3 = {k : v for k , v in source}
print(new_dict3)
--------------------------------------------[result]
{'k1': 'val2', 'k2': 'val5'}
해시 테이블 예시 코드(출처 : https://jinyes-tistory.tistory.com/10?category=841411)
# Hash Table
class HashTable:
def __init__(self, table_size):
self.size = table_size
self.hash_table = [0 for a in range(self.size)]
def getKey(self, data):
self.key = ord(data[0])
return self.key
def hashFunction(self, key):
return key % self.size
def getAddress(self, key):
myKey = self.getKey(key)
hash_address = self.hashFunction(myKey)
return hash_address
def save(self, key, value):
hash_address = self.getAddress(key)
self.hash_table[hash_address] = value
def read(self, key):
hash_address = self.getAddress(key)
return self.hash_table[hash_address]
def delete(self, key):
hash_address = self.getAddress(key)
if self.hash_table[hash_address] != 0:
self.hash_table[hash_address] = 0
return True
else:
return False
#Test Code
h_table = HashTable(8)
print(h_table.hash_table)
h_table.save('a', '1111') # 중복으로 overwrite 됨, h_table.save('i', '9999')
h_table.save('b', '3333')
h_table.save('c', '5555')
h_table.save('d', '7777')
h_table.save('h', '8888')
h_table.save('i', '9999')
print(h_table.hash_table)
print(h_table.read('d'))
h_table.delete('d')
print(h_table.hash_table)
--------------------------------------------[result]
[0, 0, 0, 0, 0, 0, 0, 0]
['8888', '9999', '3333', '5555', '7777', 0, 0, 0] <== 사이즈가 8개라서 중복 발생있음
7777
['8888', '9999', '3333', '5555', 0, 0, 0, 0]
'Python > Intermediate' 카테고리의 다른 글
[Python] 일급함수 (0) | 2021.05.24 |
---|---|
[Python] 고급 - Dict 및 Set(2) (0) | 2021.05.24 |
[Python] 고급 - 리스트 및 튜플(2) (0) | 2021.05.23 |
[Python] 고급 - 리스트 및 튜플(1) (0) | 2021.05.22 |
[Python] NamedTuple (0) | 2021.05.21 |