[자료구조] 해시 테이블

해시 테이블

• Key-Value 구조로 분할 상환 분석에 따른 시간 복잡도가 O(1)이다. (자료를 찾을 때 속도가 매우 빠름)
• 데이터 양에 관계없이 빠른 성능을 낼 수 있다.
• Python에서 딕셔너리 자료형이 이에 속한다.

해시

해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수이다.

• ABC -> A1
• 1234BC -> CV
• AF32B -> D5

다음과 같이 해시 함수를 통해 Key값을 지정해 Value를 저장해 놓는다.
그러나 여기서 문제점이 발생한다. 만약 Key값이 중복된다면 ?
그래서 해시에서는 충돌을 처리해줘야 한다.

로드 팩터

해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것

load factor = m / k

로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소한다.
로드 팩터가 증가한다는 의미는 데이터 수 증가량 < 버킷의 증가량 이기 때문에 그만큼 들어갈 공간이 줄어들기 때문이다.

충돌을 처리하는 방법

• 개별 체이닝
  - 충돌 발생 시 연결 리스트로 연결하는 방법
• 오픈 어드레싱
  - 충돌 발생 시 탐사를 통해 빈 공간을 찾는 방식

파이썬에서는 오픈 어드레싱 방법을 사용하고 있다.

---

Reference

• 파이썬 알고리즘 인터뷰