[Python] 해시 (Hash)

해시 (Hash)

개념

데이터를 빠르게 넣거나 가져올 때 사용하는 기법

• 최솟값/최댓값을 찾을 때 (전체 자료를 모두 검색하는 경우) 효율이 떨어짐
• 파이썬의 딕셔너리가 해시 테이블로 구현되어 있음
• 리스트를 쓸 수 없을 때 사용 = 인덱스 값을 숫자가 아닌 다른 값 '문자열, 튜플'을 사용할 때 딕셔너리를 사용
• 빠른 접근 /탐색이 필요할 때 => 딕셔너리 함수의 시간 복잡도는 대부분 O(1)
• 집계가 필요할 때 => 원소의 개수를 세는 문제는 코테에 많이 출제됨. 이때, collections 모듈의 Counter 클래스를 사용하면 빠르게 문제 풀이 가능

---

딕셔너리 vs 리스트

: 원소를 넣거나 삭제, 찾는 일이 많을 때는 딕셔너리를 사용하는 것이 효율적임

---

딕셔너리, 집합 개념 및 문법

[Grammer] Dictionary vs Set
링크를 들어가시면 딕셔너리와 집합 개념 및 사용하는 메서드가 잘 나와 있습니다!

---

해시 관련 문제 (프로그래머스)

해시 테이블 (Hash Table)

파이썬에서는 해쉬를 별도 구현할 이유 없이 -> 딕셔너리 타입을 사용하면 됨

용어

• 해시 (Hash) : 임의 값을 고정 길이로 변환하는 것
• 해시 테이블 (Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수 (Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해시 값 (Hash Value) 또는 해시 주소 (Hash Address) : Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
• 슬록 (SLot) : 한 개의 데이터를 저장할 수 있는 공간

1. 해시 테이블을 위한 데이터 저장공간 만들기

data = list([0 for i in range(8)]) #[0, 0, 0, 0, 0, 0, 0, 0]

2. 내장 함수 hash()로 해시키 만들기

hash('Dave') #-7514196283267883902
hash('Dave') % 8 #2

3. 해시 함수 만들기

# 임의로 8개의 해싱함수 만들어보기
def hash_function(string):
    return hash(string) % 8

4. 해시 함수를 사용해서 데이터 (Value) 저장하기

data[hash_function('Dave')] = '000-1111-2222'
data[hash_function('David')] = '000-2222-3333'

5. 해시 함수를 사용해서 데이터 (Value) 읽어오기

data[hash_function('Dave')] # '000-1111-2222'

참고 사이트