해시를 사용한 집합과 맵

해시 (Hash)

• 단방향 암호화 기법으로 해시 함수를 이용하여 생성되어진 고정된 길이의 비트열을 의미합니다. (복호화 불가능)

• Index

해시 함수 (Hash Function)

• 입력된 임의의 데이터를 고정된 길이의 데이터를 변경하여 출력해줍니다.

• 입력된 key값으로 고정된 길이의 Hash(index = 주소/색인)로 변경하여 출력하는 함수

  • 서로 다른 key를 Hashing 할 때 동일한 Hash값이 출력되는 경우가 발생 : 해시충돌은 해시테이블의 성능을 떨어뜨린다.

  • 해시 함수의 입력값은 무한하지만 출력값은 유한하므로 해시충돌은 반드시 발생합니다.(비둘기집 원리)

    ● 해시 충돌(Hash Collision) 해결방법

    • Chaining(체이닝) : 테이블의 구조를 변경해서 각 버킷이 하나 이상의 값을 저장할 수 있도록 하는 방식. 즉, 오버플로우 문제를 해결하는 방식을 기존의 각 버킷에 고정된 슬롯을 할당하는 대신 삽입과 삭제가 용이한 연결 리스트로 변경하여 해결하는 것. 탐색은 O(1), 최악의 경우 O(n)의 연산 속도를 가진다.
      

      • key의 해시 값을 계산
      • 해시 값으로 배열의 인덱스를 계산
      • 동일한 인덱스가 있을 경우 연결 리스트로 연결

    • open addressing(개방 주소법) : 해시 충돌이 발생했을때, 다른 버켓에 데이터를 삽입하는 방식. 전체 개수 이상은 저장할 수 없기 때문에 공간 안에서 탐색을 통해 빈 공간을 찾아서 해결한다.

해시 테이블 (Hash Table)

• key, value를 기반으로 1:1 매핑된 데이터를 저장하고 평균 O(1)의 시간복잡도를 가지고 있기 때문에 빠르게 값을 찾을 수 있다. ; 파이썬의 딕셔너리 자료형

• Hash(index)를 주소로 삼아서 데이터를 저장하는 자료구조

파이썬으로 구현하는 해시 테이블 클래스

class Hashtable:
	def __init__(self, length = 5):
    	self.max_len = length
        self.tabel = [[] for i in range(self.max_len)]
    
    # key에 대한 hash값 생성

	def _hash(self, key):
        # 각 문자의 ASCII값을 합하여 최대 길이로 나눈 나머지를 반환
    	result = sum([ord(s) for s in key])
        return result % self.max_len
        
    # (key, value) 값 추가
	def set(self, key, value):
    	index = self._hash(key)
        
        # 해시 충돌 발생 처리
        for pair in self.table[index]:
        	if pair[0] = key:
            	pair[1] = value
                return
                
        self.table[index].append((key,value))
        
        
        
    # 해당 값 탐색 , 없을 시 None 반환    
	def get(self, key):
    	index = self._hash(key)
        value = self.table[index]
        
        if not value:
        	return None
            
        for v in value:
        	if v[0] == key:
            	return v[1]
              
        return None

if __name__ == "__main__":
    capital = HashTable()
    country = ["Korea", "America", "China", "England", "Türkiye"]
    city = ["Seoul", "Washington", "Beijing", "London", "Ankara"]
    for co, ci in zip(country, city):
        capital.set(co, ci)

    print("해시 테이블의 상태")
    print("===============")
    for i, v in enumerate(capital.table):
        print(i, v)
    print()
    print("해시 테이블의 검색 결과")
    print("====================")
    print(f"Captial of America = {capital.get('America')}")
    print(f"Captial of Korea = {capital.get('Korea')}")
    print(f"Captial of England = {capital.get('England')}")
    print(f"Captial of China = {capital.get('China')}")
    print(f"Captial of Japan = {capital.get('Japan')}")
    print(f"Captial of Türkiye = {capital.get('Türkiye')}")

>> 해시 테이블의 상태
>> ===============
>> 0 [('America', 'Washington')]
>> 1 []
>> 2 [('England', 'London')]
>> 3 [('Korea', 'Seoul'), ('China', 'Beijing')]
>> 4 [('Türkiye', 'Ankara')]
>> 
>> 해시 테이블의 검색 결과
>> ====================
>> Captial of America = Washington
>> Captial of Korea = Seoul
>> Captial of England = London
>> Captial of China = Beijing
>> Captial of Japan = None
>> Captial of Türkiye = Ankara

내장 함수인 hash를 사용할 경우

class HashTable:
    def __init__(self, length = 5):
        self.max_len = length
        self.table = [[] for _ in range(self.max_len)]

    def set(self, key, value):
        index = hash(key) % self.max_len
        self.table[index].append((key, value))

    def get(self, key):
        index = hash(key) % self.max_len
        value = self.table[index]
        if not value:
            return None
        for v in value:
            if v[0] == key:
                return v[1]
        return None

if __name__ == "__main__":
    capital = HashTable()
    country = ["Korea", "America", "China", "England", "Türkiye"]
    city = ["Seoul", "Washington", "Beijing", "London", "Ankara"]
    for co, ci in zip(country, city):
        capital.set(co, ci)

    print("해시 테이블의 상태")
    print("===============")
    for i, v in enumerate(capital.table):
        print(i, v)
    print()
    print("해시 테이블의 검색 결과")
    print("====================")
    print(f"Captial of America = {capital.get('America')}")
    print(f"Captial of Korea = {capital.get('Korea')}")
    print(f"Captial of England = {capital.get('England')}")
    print(f"Captial of China = {capital.get('China')}")
    print(f"Captial of Japan = {capital.get('Japan')}")
    print(f"Captial of Türkiye = {capital.get('Türkiye')}")

>> 해시 테이블의 상태
>> ===============
>> 0 [('England', 'London')]
>> 1 [('Türkiye', 'Ankara')]
>> 2 []
>> 3 [('America', 'Washington'), ('China', 'Beijing')]
>> 4 [('Korea', 'Seoul')]

>> 해시 테이블의 검색 결과
>> ====================
>> Captial of America = Washington
>> Captial of Korea = Seoul
>> Captial of England = London
>> Captial of China = Beijing
>> Captial of Japan = None
>> Captial of Türkiye = Ankara