AI/Codestates
[자료구조와 알고리즘] Hash Table
JooJaeHwan
2022. 6. 15. 23:51
728x90
반응형
해시테이블이란?
- 해시테이블은 키를 활용하여 값에 직접 접근이 가능한 구조
- 해싱의 장점 : 데이터 양에 영향을 덜 받으면 성능이 빠름 ( 키를 통해 값을 검색함 )
- 파이썬의 딕셔너리는 내부적으로 해시테이블 구조로 구현되어있음
- 해시테이블은 검색을 위한 역할도 하고, 딕셔너리를 위한 자료구조의 역할도 함
- 해시테이블은 키를 빠르게 저장 및 검색할 수 있는 테이블형태의 자료구조
- 해시함수는 여러 키를 분할하기 위해 키를 해시값 ( 정수값 ) 으로 매칭시키는 역할
- 해싱 ( Hashing ) 은 쉽게 말해서 다 흩뜨려놓고, 키와 매칭되는 값을 검색하는 과정
class hash_table:
def __init__(self):
self.table = [None for _ in range(256)]
def hash_function(self, name):
return ord(name[0])
def hash_put(self, name, num):
self.table[self.hash_function(name)] = num
def hash_search(self, name):
return self.table[self.hash_function(name)]
▶ 해시성능
- 해시테이블 자체는 충돌을 해결해주지 않음
- O(1) 시간복잡도 안에 검색, 삽입, 삭제를 할 수 있음
▶ 해시충돌
- 해시충돌은 키가 들어갈 자리 ( 버킷 ) 가 없는 경우에 발생함
- 충돌이 적은 해시함수를 만드는 것이 해시테이블의 가장 중요한 목적
- 충돌상황을 방지하기 위한 방법으로 체이닝과 오픈어드레싱이 있음
■ 충돌 방지 방법 - 체이닝 ( Chaining )
- 해시 테이블에서 동일한 해시값에 대해 충돌이 일어나면, 그 위치에 있던 버킷에 키값을 뒤이어 연결함
- 체이닝의 원리
- 키의 해시값을 계산함
- 해시값을 이용해 리스트의 인덱스를 구함
- 같은 해시값이 있다면 ( 충돌 한다면 ) 리스트로 연결함
- 충돌을 줄이기 위해, 각 리스트에 대해 연결 ( 리스트 형태 ) 하도록 함
■ 충돌 방지 방법 - 오픈어드레싱 ( Open Addressing )
- 다른 로직의 함수를 활용하기 때문에 Open Addressing 이라 함
- 오픈어드레싱은 비어있는 배열 슬롯이 발견될 때까지 Array의 위치를 검색하여 해시 충돌을 해결함
- 충돌이 일어나는 경우, 탐사 ( Probing ) 를 진행하면서 빈 공간을 찾아야 해결이 됨
▶ 좋은 해시함수란?
- 해시함수를 어떻게 구현하는지에 따라 해시의 성능이 결정됨
- 키와 값의 계산과정이 쉬워야 함
- 충돌을 피할 수 있어야함
▶ 해시를 사용할 때 주의할 점
- 키 데이터타입에 맞는 좋은 해시함수가 있는지 확인
- 적절한 해시테이블 크기 ( 배열크기 )
728x90
반응형