[자료구조] Hashing 개념, collision 개념(Ch.05 Hashing)

자료구조에서 Hashing과 Collision은 데이터 저장과 검색 효율을 높이기 위한 중요한 개념이다.

- Hashing (해싱)

Hashing은 키(key)를 입력으로 받아 해시 함수(hash function)를 통해 고정된 크기의 해시 값(hash value) 또는 해시 코드(hash code)를 생성하는 과정이다. 이 해시 값을 사용하여 데이터를 해시 테이블(hash table) 내의 특정 위치에 저장하거나 검색할 수 있다. 해싱의 주요 목적은 데이터를 빠르게 저장하고 검색하는 것이다.

- 해시 함수 (Hash Function)

해시 함수는 키를 해시 값으로 변환하여 해시 테이블의 인덱스를 결정한다. 해시 함수는 결정적이어야 하며 동일한 키에 대해 항상 동일한 해시 값을 반환해야 한다. 또한, 효율적으로 해시 값을 계산할 수 있어야 하고 입력 키가 고르게 해시 테이블의 모든 슬롯에 분포되도록 해야 한다.

- 해시 테이블 (Hash Table)

해시 테이블은 배열 형태로 구성된 데이터 구조이다. 배열의 각 위치를 슬롯이라고 하며, 해시 값이 가리키는 위치에 데이터를 저장한다.

- Collision (충돌)

Collision은 서로 다른 두 개 이상의 키가 동일한 해시 값을 가지게 되어 해시 테이블의 동일한 슬롯에 저장되려는 현상을 말한다. 해시 함수가 완벽하지 않기 때문에 충돌은 불가피하다.

- Collision 해결 방법

Collision을 해결하는 방법에는 체이닝(Chaining)과 오픈 어드레싱(Open Addressing) 기법이 있다.

1. 체이닝 (Chaining)

체이닝은 각 슬롯을 연결 리스트(linked list)로 관리한다. 동일한 슬롯에 저장될 데이터들을 연결 리스트로 연결하여 저장한다. 체이닝의 장점은 해시 테이블의 크기에 관계없이 충돌된 데이터를 저장할 수 있다는 점이다. 하지만 연결 리스트가 길어질 경우 검색 시간이 길어질 수 있다.

 

2. 오픈 어드레싱 (Open Addressing)

오픈 어드레싱은 충돌 시 해시 테이블 내의 다른 슬롯을 찾아 데이터를 저장한다. 오픈 어드레싱에는 여러 기법이 있다.

• 선형 탐사 (Linear Probing): 충돌이 발생하면 고정된 간격(보통 1)을 더해 다음 슬롯을 검사한다.
• 이차 탐사 (Quadratic Probing): 충돌이 발생하면 제곱수 간격을 더해 다음 슬롯을 검사한다.
• 이중 해싱 (Double Hashing): 두 번째 해시 함수를 사용하여 새로운 슬롯을 결정한다.