[Basic C++] #40_해시함수, 비순차 연관 컨테이너, 해시 테이블

 

[Basic C++] #40_해시 함수, 비순차 연관 컨테이너, 해시 테이블

 

C++ 개발에서 "해시 함수"에 대해 알아보겠습니다.

"전문가를 위한 C"의 16 항목, "컨테이너와 반복자 이해하기"에 해당하는 내용입니다.

 

---

 

Overview

 

1. 비순차 연관 컨테이너
2. 해시 함수
3. 해시 충돌, 해시 문제점

 

#0. 비순차 연관 컨테이너

 

• C++의 STL(표준 라이브러리)의 비순차 연관 컨테이너는 해시 함수를 사용합니다.
• 비순차 연관 컨테이너에는 "unordered_map", "unordered_multimap", "unordered_set", 그리고 "unordered_multiset"이 있습니다.
• 이들은 모두 항목을 저장할 때, 정렬 작업을 수행하지 않습니다.

 

#1. 해시 함수

 

출저: 전문가를 위한 C

 

• 해시 테이블을 구현하기 위해 "버킷(Bucket)"이라는 배열에 대한 배열을 사용합니다.
• 해시 함수는 키를 이 버킷의 인덱스와 매핑합니다. 그리고 키와 쌍을 이루는 항목 값은 해당 인덱스 위치에 저장되죠. 

 

키 -> 해쉬 함수 -> 버킷 인덱스 -> 항목 값 저장

 

#2. 해시 충돌

 

• 이때, 우리는 "해시 충돌"에 대해 알고 있어야합니다.
• 해시 충돌이란 두 개 이상의 키에 대한 해시 함수의 결과 값이 같을 경우를 얘기합니다.
• 즉, 버킷의 인덱스 번호가 같은 두 개 이상의 항목이 존재하는 것을 의미합니다.
• 이 충돌 문제를 해결하기 위해 대부분의 구현에서 "리니어 체이닝"을 사용하고 있습니다.
• 리니어 체이닝 방법에 따르면, 먼저, 해시 값의 결과로 나온 버킷의 인덱스는 연결 리스트를 포인팅 합니다.
• 해당 연결 리스트는 저장하고자 하는 최초의 키 값과 데이터를 함께 저장합니다.
• 따라서, 우리는 항목 값에 접근하기 위해 연결 리스트를 순회하며 우리가 찾고자 하는 키와 데이터가 합치하는 항목을 찾게 되죠.
• 리니어 체이닝의 수행 과정은 아래와 같습니다. 

 

 키 -> 해시 함수 -> 버킷 인덱스 -> 연결 리스트 -> 키 + 항목 값