SW마에스트로 서포터즈입니다!
이번 콘텐츠는 오랜만에 돌아온
알.자.구 알고리즘 자료구조 콘텐츠 입니다!
오늘은 해시테이블(Hash Table)에 대한 설명을
드리려고 합니다!
해시 테이블은 데이터베이스, 캐싱, 프로그래밍 언어의 내부 구현 등 여러 분야에서 중요하게 사용되는 자료구조 인데요! 그럼 한 번 알아보러 가시죠~!
해시 테이블은 해시함수를 사용하여 변환한 값을
색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는
자료구조 입니다.
키를 값에 매핑하는 데이터 구조로, 데이터의 저장과
검색을 매우 빠르게 수행할 수 있습니다.
해시 함수는 해시 테이블의 핵심 구성 요소입니다.
해시 함수는 데이터의 '키'를 '해시 코드'라는 고유한 숫자 값으로 변환합니다. 이를 통해 해시 코드는 해시 테이블 내에서 데이터의 위치를 결정하는 데 사용됩니다.
좋은 해시 함수의 특징과 중요성은 다음과 같습니다.
1. 고유성: 좋은 해시 함수는 각기 다른 키에 대해 가능한 한 유니크한 해시 값을 생성해야 합니다. 이는 데이터의 빠른 검색과 효율적인 저장 공간 활용에 기여합니다.
2. 균일한 분포: 해시 함수는 데이터를 해시 테이블 전체에 균일하게 분포시켜야 합니다. 이는 해시 충돌을 최소화하고 해시 테이블의 성능을 최적화합니다.
3. 속도: 해시 함수는 매우 빨라야 합니다. 데이터 처리 속도가 느린 해시 함수는 해시 테이블의 전체적인 성능을 저하시킬 수 있습니다.
즉 해시 함수의 설계는 해시 테이블의 성능에 직접적인
영향을 미치기 때문에 가장 핵심이라고 볼 수 있습니다.
하지만 해시 테이블에서 두 개의 다른 키가 동일한 해시
값을 갖는 '충돌'이 발생할 수 있습니다.
이에 대해 자세히 설명하기 전 ‘적재율’이라는 개념에 대해
먼저 알아야 합니다.
적재율은 해시 테이블에서 사용 중인 버킷(또는 슬롯)의
비율을 나타냅니다. 키의 개수를 K, 해시 테이블의 크기를
N 이라고 했을 때 적재율은 K/N 이다.
즉 해시 테이블의 크기 대비, 키의 개수 입니다.
Direct Address Table은 키 값을 인덱스로 사용하는 구조이기 때문에 적재율이 1 이하이며 적재율이 1 초과인
해시 테이블의 경우는 반드시 충돌이 발생하게 됩니다.
일반적으로 적재율은 0.7 정도가 이상적입니다. 이 수치 이상이 되면 해시 테이블의 크기를 늘려 적재율을 낮추는
'재해싱(rehashing)'을 고려할 수 있습니다.
해시 테이블에서 충돌은 쉽게 말해 2개 이상의 키가 동일한
해시 값을 가질 때 발생 합니다.
위의 사진처럼 ‘소마’ , ‘스트로’ 라는 key 값들이 모두 동일한 15라는 곳을 가리키게 될 때 충돌이 발생했다고
하는 것 입니다.
충돌 해결 방법에는 크게 두 가지가 있습니다.
체이닝(Chaining) 기법과
개방주소 방법(Open Addressing)이 있습니다.
먼저 체이닝 기법에 대해 알아보겠습니다.
체이닝이란 충돌이 발생했을 때 이를 동일한 버킷(Bucket)에 저장하는데 이를 연결리스트 형태로 저장하는 방법을
말합니다.
위 그림을 보면 ‘소마’ 와 ‘스트로’ 의 인덱스가 15 로 충돌하게 된 경우인데, 이 때 ‘스트로’ 를 ‘소마’ 뒤에 연결함으로써 충돌을 처리하는 것을 볼 수 있습니다.
장점: 간단하고 직관적입니다. 충돌이 빈번하게 발생하더라도, 리스트를 통해 효율적으로 관리할 수 있습니다.
단점: 연결 리스트의 길이가 길어지면 검색 시간이 증가할 수 있습니다. 또한, 추가적인 메모리 공간이 필요합니다.
개방 주소 방법은 충돌이 발생했을 때 다른 버킷에 해당 요소를 저장하는 방식입니다. 즉 다른 주소에도 저장을 할 수 있게 해주는 방식 입니다. 작동 방식은 충돌이 발생하면, 다른 버킷을 탐색하여 빈 공간을 찾는 방법인데요.
여기서 다양한 탐사 기법이 사용될 수 있습니다.
예시로는
선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 이 있습니다
장점: 추가적인 메모리 할당 없이 해시 테이블 내에서 모든 작업이 이루어집니다.
단점: 클러스터링(버킷들이 그룹을 형성하는 현상) 문제가 발생할 수 있으며, 이는 성능 저하를 초래할 수 있습니다. 특히 선형 탐사 방식에서 이 문제가 두드러집니다.
즉 정리하자면 체이닝은 구현이 간단하고 충돌에 강하지만 메모리 사용이 늘어날 수 있습니다. 반면, 개방 주소 방법은 메모리를 효율적으로 사용하지만, 클러스터링으로 인한 성능 저하가 문제가 될 수 있습니다.
해시테이블의 시간복잡도에서 이상적인 조건에서는 이러한 연산들을 평균적으로 상수 시간(O(1)) 내에 수행할 수 있습니다.
그러나 최악의 경우, 특히 모든 키가 동일한 해시 값을 갖게 되는 경우에는 이러한 연산들이 선형 시간(O(n))이 걸릴 수 있습니다.
오늘은 '해시테이블'에 대해 알아봤습니다!
어떠셨나요~?
해시 테이블은 그 유연성과 효율성 덕분에 현대 컴퓨팅과 데이터 관리에서 빼놓을 수 없는 중요한 요소입니다.
적절하게 구현되고 관리된다면, 해시 테이블은 대량의 데이터를 빠르고 효율적으로 처리할 수 있는 강력한 도구가 됩니다.
따라서 한 번 알아두면 좋겠죠 ~?
그럼 다음에 더 좋은 알자구 콘텐츠로 돌아오겠습니다!
감사합니다!