1️⃣ Hash Table
해시 테이블의 구조
- key에 value를 저장하는 데이터 구조
-
key를 통해 바로 데이터를 받아오기 때문에, 다른 자료구조에 비해 검색 속도가 빨라진다.
-
보통 배열로 미리 해시 테이블의 크기를 생성한 후에 사용한다.
-
Python - Dictionary (파이썬에선는 해시를 별도로 구현하지 않고 딕셔너리를 사용)
-
해시 테이블의 장단점
- 장점
- 검색 속도가 빠르다. (저장/읽기 속도)
- 데이터의 중복 처리가 쉽다. → 배열처럼 하나씩 데이터를 거쳐가며 확인할 필요 없이, 키에 대한 데이터만 확인하면 되므로
- 단점
- 저장공간이 일반적으로 더 많이 든다.
→ 해시테이블이 데이터가 없더라도 저장공간을 마련해 둔다.
- 충돌(여러 키가 동일한 주소를 갖는 경우)을 해결하기 위한 별도의 조치가 필요하다.
- 저장공간이 일반적으로 더 많이 든다.
- 활용
-
검색이 잦은 경우
-
저장, 삭제, 읽기가 많은 경우
-
캐시 구현 (중복 확인이 유용하기 때문에)
-
용어
-
Hash : 임의의 값을 고정길이로 변환
-
Hash Table : 키값이 해시 함수 연산을 거쳐 직접 접근이 가능하도록 한 데이터 구조
-
Hashing Function : key를 넣으면 산술 연산을 실행해 찾고자 하는 데이터의 위치를 알아내는 함수
-
Hash Value / Hash Address : key의 hashing function 연산 결과로 해시값을 구하고, 이를 통해 해시 테이블에서 해당 key에 대응하는 데이터의 위치를 일관성 있게 찾을 수 있다.
-
Slot : 한 개의 데이터를 저장할 수 있는 공간
2️⃣ 해시테이블 구현하기 예제
hash_table = list([0 for i in range(8)])
def get_key(data):
return hash(data)
def hash_func(key):
return key % 5
def save_data(data, value):
hash_address = hash_func(get_key(data))
hash_table[hash_address] = value
def read_data(data):
hash_address = hash_func(get_key(data))
return hash_table[hash_address]3️⃣ 충돌(Collision) 해결 알고리즘
추가 예정
📂 참고 자료
https://www.fun-coding.org/post/Chapter09-hashtable-live.html#gsc.tab=0
