[파이썬 알고리즘] Ch 6-4. 해싱(Hashing) (1) Hashing

참고 도서: 최영규, ⌜파이썬 알고리즘⌟ 생능츨판, 2021

1. 해싱(Hashing)이란?

• 공간을 이용해 시간 벌기 전략의 탐색 기법이다.
• 이상적인 경우의 시간 복잡도: $O(1)$
  
  

< 해싱의 기본 전략 >
지금까지의 탐색 방법들은 탐색키를 테이블에 저장된 각 레코드의 키값과
하나씩 비교하여 원하는 항목을 찾는 방식이었다.
반면, 해싱은 이와는 전혀 다른 전략을 사용한다.

해싱에서는 탐색키를 테이블의 모든 레코드와 비교하지 않는다.
대신 키값에 산술적인 연산을 적용하여 해당 레코드가 저장되어야 할 위치를 직접 계산한다.

즉, 탐색키로부터 레코드가 있어야 할 위치를 바로 구한 뒤,
그 위치에 레코드가 존재하는지만 확인하면 된다.

2. 해싱의 구조

키(key)

• 데이터를 식별하기 위한 값
• 해시 함수(hash function)의 입력값이 된다.
• 키의 길이가 일정하지 않을 수 있다.

해시 함수(hash function)

• 키를 입력으로 받아서 해시 주소(hash address)를 생성하는 함수
• 임의의 키를 고정된 길이의 해시값으로 변환해주는 역할을 한다.
• 서로 다른 키가 같은 해시값을 갖는 경우가 있다. → 해시 충돌(hash collision)

값(value)

• 키에 대응되어 해시 테이블에 저장되는 실제 데이터
• key-value 쌍을 이루어 저장된다.

해시 테이블(hash table)

• 해시 함수를 통해 생성된 해시값을 주소로 사용하여 데이터를 저장하는 자료구조
• 내부적으로 버킷(bucket)과 슬롯(slot)으로 구성된다.

버킷(bucket)

• 하나의 해시 주소에 대응되는 저장 단위
• 동일한 해시 주소로 매핑(mapping)된 데이터들이 저장된다.
• 해시 충돌이 발생하면 하나의 버킷에 여려 데이터가 저장될 수 있다.

슬롯(slot)

• 버킷 내부의 개별 저장공간
• 실제 데이터가 저장되는 위치
• 하나의 버킷 안에서 데이터를 담는 최소 단위
  
  
  
  
  

3. 오버플로

오버플로(overflow)

• 해시 충돌이 버킷의 슬롯 수보다 많아서, 그 버킷에 항목을 더 이상 저장할 수 없는 상황
  
  

오버플로 해결 방안

• 개방 주소법: 선형 조사법, 이차 조사법, 이중 해싱법
• 체이닝(chaining): 하나의 슬롯에 여러 항목을 저장하는 방법
  
  
  
  

다음 편에서는 오버플로 해결 방법인 선형 조사법과 체이닝(chaining)에 대해서 알아보도록 하자.