파이썬 알고리즘 인터뷰 - 해시 테이블

해시테이블

• 해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 추상 자료형(ADT)를 구현하는 자료구조이다.
• 대부분 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점이다.
• 데이터 양에 관계 없이 빠른 성능을 가진다.

 

해시

• 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 말한다.
• 해싱 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱이라 하며, 해싱은 정보를 가능한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법이다.
• 체크섬, 손실 압축, 무작위화 함수, 암호 등에 쓰이고 서로 혼용되기도 한다.

성능 좋은 해시 함수들은 다음의 특징을 가진다.

• 해시 함수 값 충돌의 최소화
• 쉽고 빠른 연산
• 해시 테이블 전체에 해시 값이 고르게 분포
• 사용할 키의 모든 정보를 이용하여 해싱
• 해시 테이블 사용 효율이 높을 것 

 

로드 팩터

로드 팩터의 공식

• 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 m으로 나눈 것이다.
• 로드 팩터 비율에 따라서 해시 함수 재작성, 해시 테이블 크기를 조정해야 할지 정하고 해시 함수들이 키들을 잘 분산해 주는지를 말하는 효율성 측정에도 사용된다.

 

해시 함수

 

해시 함수를 통해 키가 해시로 변경되는 과정

• 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱이라고 한다.
• 해싱 알고리즘에는 여러가지 종류가 있지만 대표적으로 한 가지만 소개하면 모듈로 연산을 이용한 나눗셈 방식이 있다.

h(x) = x mod m  
# 모듈로 연산을 이용한 나눗셈 방식(Modulo-Division Method)
# h(x)는 입력값 x의 해시 함수를 통해 생성된 결과이고, m은 해시 테이블의 크기
# 일반적으로 2의 멱수에 가깝지 않은 소수를 택하는 것이 좋다

 

 

개별 체이닝

입력값이 다음 표와 같을 때 

키	값	해시	충돌 여부
윤아	15	2	충돌
유리	47	1
서현	17	2	충돌
수영	7	4

이 표를 개별 체이닝 방식으로 구현하면 다음 그림과 같다.

 

개별 체이닝 방식

• 해시 테이블의 기본 방식이기도 한 개별 체이닝은 충돌 발생 시 이 그림과 같이 연결리스트로 연결하는 방식이다.
• 기본적인 자료구조와 임의로 정한 알고리즘만 있으면 되므로, 자주 쓰이며, 원래 해시 테이블 구조의 원형이기도 하다.
• 최선의 경우 O(1)만에 탐색이 끝나지만, 최악의 경우(모든 해시 충돌이 발생할 경우) O(n)이 된다.

원리 :

1. 키의 해시 값을 계산한다.
2. 해시 값을 이용해 배열의 인덱스를 구한다.
3. 같은 인덱스가 있다면 연결 리스트로 연결한다.

 

 

 

오픈 어드레싱

오픈 어드레싱 방식

• 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식이다 -> 모든 원소가 반드시 자신의 해시값과 일치하는 주소가 보장 되지 않는다.
• 개별 체이닝과 달리 전체 슬롯의 개수 이상은 저장 할 수 없다.
• 버킷 사이즈보다 큰 경우에는 삽입 x, 기준 로드 팩터 비율을 넘어서게 되면 그로스 팩터(Growth Factor) 비율에 따라 더 큰 크기의 버킷 생성후 복사하는 리 해싱(Rehashing) 작업이 일어난다.

 

각 언어별 해시 테이블 구현

언어	방식
C++	개별 체이닝
자바	개별 체이닝
고	오픈 어드레싱
파이썬	오픈 어드레싱