[Python] 해쉬(Hash Table)

간단용어

해쉬 : 임의 값을 고정길이로 변환하는 것 

해쉬함수 : 특정연산을 이용하여 키 값을 받아서 value를 가진 공간의 주소로 바꾸어주는 함수

해쉬테이블 : 해쉬구조를 사용하는 데이터구조

해쉬값 : key값을 해쉬함수에 넣어서 얻은 주소값. 

슬롯 : 한개의 데이터를 저장할 수 있는 공간(아래에선 buckets)

 

해쉬구조

Key와 Value 쌍으로 이루어진 데이터구조 

Key를 이용해서 데이터를 찾아서 속도를 빠르게 만드는 구조 

 

파이썬에서는? '딕셔너리 타입'이 해쉬테이블과 같은 구조

 

언제 사용하는가? 검색이 많이 필요한경우, 저장/삭제/읽기가 많은 경우, 캐쉬를 구현할 경우

 

장점은?
데이터저장/검색 속도가 빠르다

키에 대한 데이터 중복확인이 쉽다.

 

단점은?

저장공간이 좀더 많이 필요하다

여러 키에 대한 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요하다(충돌해결알고리즘)

 

시간복잡도는 어떻게 되는가?

충돌이 없는 일반적인 경우 : O(1)

충돌이 발생하는 최악의 경우 : O(n)

 

해쉬예제

문자열개수Count하기 

a= input()
str1 = dict()
for x in a:
    str1[x]=str1.get(x,0)+1
print(str1)

#input : AbaAeCe
#결과 : {'A': 2, 'b': 1, 'a': 1, 'e': 2, 'C': 1}

dict[A] = dict.get('A',0) + 1 

dict[A] = 1, dict[A] = dict[A] + 1 하고 싶은데, dict[A]가 없을수도 있어서 오류남

이때, dict[A] 가 없다면 대신 0을 넣어서 연산을 수행하라며 dict[A] = dict.get('A',0) + 1 을 쓴다. 

 

사용하는 문자열 비교하기

a= input()
b= input()
check = dict()
for x in a:
    check[x]=check.get(x,0)+1
for x in b:
    check[x]=check.get(x,0)-1
    
 for x in a:
    if check.get(x)!=0:
        print("NO")
        break
else:
    print("YES")

dict[A] = dict.get('A',0) + 1 
dict[A] = dict.get('A',0) - 1 

문자열 비교하기 위해, 처음비교문자열에 있는 알파벳들의 키에 +1 해두고, 다음비교문자열에도 같은게 있으면 -1을 함.

결국 문자열의 구성이 모두 같다면 key의 값이 모두 0

 check.get(x) 

딕셔너리에서 x라는 키 값으로 value를 가지고 올때 사용

 

프로그래머스 문제