[Python] 고급 - Dict 및 Set(1)

• 해시테이블
• 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]