비선형 데이터구조, 해시(Hash) #6 체이닝(Chaining)

이전글

https://yonghwankim-dev.tistory.com/175

비선형 데이터구조, 해시(Hash) #5 충돌 해결(Collision Solution)

 

개요

이전 글에서는 해시 충돌이 발생하였을 경우 해결하는 방법에 대해서 알아보았습니다. 대표적인 해시 충돌 해결방법은 선형조사법, 2차식 조사법, 이중 해시 방법이 존재하였습니다. 그런데 이 방법들에는 공통적인 단점이 존재합니다. 그것은 테이블의 데이터가 빠르게 차기 때문에 테이블의 크기를 자주 변경해주어야 합니다. 이번글에서는 따라서 이러한 문제를 해결하기 위해서 체이닝(chaining)을 소개하겠습니다.

 

1. 체이닝(chaining)이란 무엇인가?

체이닝은 일반적인 테이블에 데이터를 직접 넣는 대신 연결리스트를 넣어 각각의 요소의 연결리스트에 데이터를 추가하거나 제거하는 해시 저장 방식입니다. 아래의 그림은 체이닝의 구조입니다.

2. 체이닝의 특징

• 상수 시간으로 어떤 요소든 추가하고 제거하고 탐색이 가능함
• 연결리스트 기반이기 때문에 동적인 크기임
• 테이블의 크기 변경을 자주할 필요가 없음
• 체이닝 해시의 적재율(λ)
  • λ = num entries / num possible chains
  • λ>=1이 가능함
• 해시 값이 같은 숫자를 반환하여 하나의 체인이 너무 길어져 시간복잡도가 연결리스트와 같아지는 단점이 있을 수 있음
  • Best Case : O(1)
  • Worst Case : O(n)

References

[부스트코스] 자바로 구현하고 배우는 자료구조