[자료구조] 해시 테이블 (Hash Table), 해싱 (Hashing), 해시 충돌 - 체이닝 (Chaining) & 오픈 어드레싱 (Open Addressing)
자료구조
해시 테이블과 해싱의 기본 개념
1. 해시 테이블 (Hash Table)
o 해시 테이블은 키(Key)와 데이터 값(Value) 쌍을 저장하는 자료구조로, 각 키를 해시 함수(Hash Function)를 통해 특정 위치(index)로 변환하여 빠르게 값에 접근할 수 있도록 합니다.
o 해시 테이블은 배열과 유사하게 인덱스를 사용해 데이터에 접근하므로, 특정 키에 대해 매우 빠른 검색 속도를 가질 수 있습니다.
데이터의 크기에 관계없이 삽입 및 검색에 매우 효율적
2. 해싱 (Hashing)
해싱이란 임의의 길이의 값을 해시함수(Hash Function)를 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다.
o 해싱은 키를 해시 함수에 넣어 고정된 크기의 해시 값을 생성하는 과정입니다. 생성된 해시 값은 해시 테이블에서 데이터가 저장될 위치를 결정하는 데 사용됩니다.
o 예시: "apple"이라는 키를 해시 함수에 넣었을 때 결과가 4라면, 해시 테이블의 4번 위치에 "apple"의 값을 저장하게 됩니다.
해시 함수 (Hash Function)
해시 함수는 임의의 길이를 가진 데이터를 입력받아 고정된 길이의 해시 값(또는 해시 코드)을 반환하는 함수입니다. 해시 함수는 다음과 같은 특징이 있어야 합니다:
• 고속 처리: 입력된 키를 빠르게 해시 값으로 변환해야 합니다.
• 고유성: 서로 다른 키는 가급적 다른 해시 값을 반환해야 합니다.
• 균등 분포: 해시 값이 고르게 분포되어, 해시 테이블의 특정 위치에만 데이터가 몰리지 않도록 해야 합니다.
그러나 현실적으로 서로 다른 키가 동일한 해시 값을 가질 수 있는데, 이를 해시 충돌(Hash Collision)이라고 합니다.
해시 충돌과 충돌 해결 방법
해시 충돌은 서로 다른 키가 동일한 해시 값을 가지는 상황으로, 해시 테이블에서 두 데이터가 같은 위치에 저장되려 할 때 발생합니다. 충돌이 발생하면 이를 해결하기 위한 여러 방법이 있습니다.
1. 체이닝 (Chaining)
체이닝이란 충돌이 발생했을 때 이를 동일한 버킷(Bucket)에 저장하는데 이를 연결리스트 형태로 저장하는 방법을 말한다. 위 그림을 보면 John Smith 와 Sandra Dee 의 인덱스가 152 로 충돌하게 된 경우인데, 이 때 Sandra Dee 를 John Smith 뒤에 연결함으로써 충돌을 처리하는 것을 볼 수 있다.
o 체이닝은 충돌이 발생한 위치에 연결 리스트(Linked List)를 사용하여 여러 개의 데이터를 저장하는 방식입니다.
o 예를 들어, "apple"과 "banana"가 해시 값 4를 반환한다면, 해시 테이블의 4번 위치에 ["apple", "banana"]와 같은 형태로 리스트를 만들어 데이터를 저장합니다.
o 장점: 해시 테이블의 크기와 관계없이 데이터를 계속 추가할 수 있습니다.
o 단점: 동일한 위치에 많은 데이터가 몰리면 탐색 속도가 느려질 수 있습니다.
2. 오픈 어드레싱 (Open Addressing)
위에서 살펴본 동일한 충돌에 대해서 이번엔 체이닝 방식을 적용하지 않고 그 다음으로 비어있는 주소인 153 에 저장하는 것을 볼 수 있다. 이러한 원리로 탐색, 삽입, 삭제가 이루어지는데 다음과 같이 동작한다.
o 오픈 어드레싱은 충돌이 발생하면 다른 빈 공간을 찾아 데이터를 저장하는 방식입니다. 체이닝과 달리, 한 위치에 여러 데이터를 저장하지 않고, 다른 위치를 활용합니다.
o 방법:
선형 탐사 (Linear Probing)
충돌이 발생하면, 바로 다음 위치에 데이터를 저장합니다. 계속 충돌이 발생하면 순차적으로 다음 위치를 탐색합니다.
선형탐사는 가장 기본적인 충돌해결기법으로 위에서 설명한 기본적인 동작방식입니다. 선형탐사는 바로 인접한 인덱스에 데이터를 삽입해가기 때문에 데이터가 밀집되는 클러스터링(Clustering) 문제가 발생하고 이로인해 탐색과 삭제가 느려지게 됩니다.
제곱 탐사, 이차 탐사 (Quadratic Probing): 충돌이 발생하면, 1칸씩이 아닌, 제곱수 간격으로 다음 위치를 탐색합니다. 예를 들어, 1칸, 4칸, 9칸 등으로 떨어진 위치를 탐색합니다.
o 제곱탐사는 말 그대로 1^2, 2^2, 3^3… 으로 탐사를 하는 방식으로 선형탐사에 비해 더 폭넓게 탐사하기 때문에 탐색과 삭제에 효율적일 수 있습니다. 하지만 이는 초기 해시값이 같을 경우에 탐사하는 역시나 클러스터링 문제가 발생하게 됩니다.
이중 해싱 (Double Hashing)
충돌이 발생하면, 다른 해시 함수를 사용해 새로운 위치를 찾습니다.
o 이중해싱은 선형탐사와 제곱탐사에서 발생하는 클러스터링 문제를 모두 피하기 위해 도입된 것이다. 처음 해시함수로는 해시값을 찾기 위해 사용하고 두번째 해시함수는 충돌이 발생했을 때 탐사폭을 계산하기 위해 사용되는 방식입니다.
o 장점: 모든 데이터를 해시 테이블 내부에 저장하므로 추가 메모리를 사용하지 않습니다.
o 단점: 테이블이 꽉 차면 새로운 데이터를 저장하기 어려워지고, 성능이 저하될 수 있습니다.
해시 테이블의 활용 예
• 데이터베이스 인덱스: 특정 레코드를 빠르게 찾기 위해 해시 테이블을 사용합니다.
• 캐시: 최근 사용한 데이터를 해시 테이블로 저장하여 빠르게 접근할 수 있습니다.
• 사전(Dictionary) 자료구조: 키-값 쌍으로 데이터를 저장하고 빠르게 검색할 때 사용합니다
출저 : https://bnzn2426.tistory.com/115
https://baeharam.netlify.app/posts/data%20structure/hash-table
https://en.wikipedia.org/wiki/Hash_table#Separate_chaining
https://kor-shin.github.io/java/hashing/
