Hash Table
- Hash Table은 컴퓨터 과학에서 가장 중요하면서도 검색, 삽입, 삭제 작업에 효율적인 자료구조 중 하나입니다.
- Key-value 형태의 데이터를 저장하고 검색하기 위한 자료구조로, 각 Key에 해당하는 값을 빠르게 찾을 수 있도록 해줍니다.
- 예를 들어, 색상 정보를 저장하고 검색하는 상황에서 배열을 사용하면 검색에 의 시간이 걸리고, 원하는 값을 찾기 어려울 수 있습니다. 하지만 Hash Table은 이를 해결해줍니다.
Hash Table 동작 원리
- Hash Table은 해시 함수를 사용하여 Key 값을 기반으로 데이터를 저장하고 검색합니다.
- 해시 함수는 Key를 특정 인덱스로 변환하는 역할을 합니다. 예를 들어, "Yellow"이라는 Key에 대한 RGB 값을 저장하고자 할 때, { "Yellow": "#FFFF00" } 형태로 저장하고 이를 빠르게 조회할 수 있습니다.
- 해시 함수는 Key를 특정 인덱스로 변환하는데, 이때 인덱스는 해시 테이블의 크기에 따라 결정됩니다.
- 해시 테이블의 크기는 일반적으로 2의 거듭제곱에 가깝지 않은 소수(prime number)로 선택하며, 이렇게 하면 데이터가 더 고르게 분포되어 효율적인 작동을 도와줍니다.
Hash Table 사용 사례
- 데이터에 빠른 검색, 삽입, 삭제 작업이 필요한 상황에서 사용됩니다.
- 키-값 쌍의 데이터를 관리할 때 유용하며, 중복 데이터 검사와 제거도 가능합니다.
- 캐싱(Caching) 시스템에서도 사용되며, Redis와 같은 캐싱용 서버 내부에서 Key-value 쌍을 저장할 때 해시 테이블이 활용됩니다.
Hash Table의 장점과 단점
장점
- 빠른 데이터 접근 속도: 평균적으로 O(1)의 시간 복잡도로 조회, 삽입, 삭제를 수행
- 키-값 쌍 저장: 데이터의 연관 관계를 명확하게 관리 가능
- 중복 방지: 키의 유일성을 통해 데이터의 중복 방지
단점
- 충돌 발생 가능성: 두 개 이상의 키가 동일한 해시 값을 가질 경우 충돌 발생
Hash Collision
- 해시 테이블 내에 어떤 키가 이미 자리 잡고 있는 상태에서 다른 키가 삽입을 시도하는 경우, 해시 함수가 서로 다른 입력에 대해 동일한 값을 반환하는 경우 Hash Collision 발생합니다.
Hash Collision이 발생하는 이유
- 해시 함수는 입력을 고정 크기의 해시 값으로 변환하는데, 이때 출력 공간이 입력 공간보다 작을 수 있어서 동일한 해시 값이 발생할 수 있습니다.
해결 방법 1) Separate Chaining
- 충돌이 발생하면 연결 리스트(Linked List)를 사용하여 충돌된 항목을 저장하는 방식입니다.
- 같은 해시 값에 대한 데이터는 연결 리스트에 추가되어 관리됩니다.
해결 방법 2) Open Addressing
- Separate Chaining과 달리 추가 공간을 사용하지 않고 충돌을 해결하는 방법입니다.
- 충돌이 발생하면 다른 위치에 데이터를 저장합니다.
- 세 가지 주요 방법으로 해결할 수 있습니다: 선형 탐색 (Linear Probing), 이차원 탐색 (Quadratic Probing), 더블 해싱 (Double Hashing).
- Open Addressing에서 데이터 삭제 시 주의가 필요하며, 삭제된 데이터에 자리가 비어있으면 검색 문제가 발생할 수 있습니다.
Load Factor
Load Factor는 해시 테이블에 저장된 항목의 수를 해시 테이블의 전체 크기로 나눈 값으로, 해시 테이블의 "가득 찬 정도"를 나타냅니다. 예를 들어, 로드 팩터가 0.5라면 해시 테이블의 절반만 항목으로 채워져 있다는 것을 의미합니다.
앞의 충돌 해결 방법이였던 Separate Chaining과 Open Addressing 모두에서 Load Factor는 중요한 역할을 합니다. 그러나 각 방식에서 Load Factor의 의미와 그에 따른 영향이 약간 다릅니다.
Separate Chaining
- Load Factor가 증가하면 각 버킷에 저장된 연결 리스트의 평균 길이가 길어집니다.
- 검색 성능은 load factor에 비례해서 저하될 수 있습니다.
- 이로 인해 충돌 시 처리하는 데 필요한 시간이 증가할 수 있습니다.
- 따라서, Load Factor가 특정 임계값 (예: 0.75)을 초과하면 해시 테이블의 크기를 늘려서 리사이징하는 것이 일반적입니다.
Open Addressing
- Load Factor가 증가하면 해시 테이블 내의 사용 가능한 빈 슬롯이 줄어들게 됩니다. 이로 인해 새로운 항목을 삽입하거나 기존 항목을 찾을 때 발생하는 충돌의 수가 증가하게 되며, 이는 성능 저하로 이어질 수 있습니다.
- 검색 성능은 load factor가 1에 가까워 질 수록 지수적으로 커집니다.
- Open Addressing에서는 Load Factor가 너무 높아지면 성능이 크게 저하될 수 있으므로, 일반적으로 Load Factor의 임계값을 Separate Chaining보다 낮게 설정합니다 (예: 0.5 또는 0.6).
- 따라서, 두 해시 테이블 구현 방식 모두에서 Load Factor는 중요한 역할을 합니다.
Dynamic Resizing (동적 리사이징)
동적 리사이징은 해시 테이블의 크기를 동적으로 조정하는 과정입니다. 초기에 할당된 배열의 크기가 고정되어 있기 때문에, 데이터의 양이 증가하면서 배열의 크기를 초과할 가능성이 있습니다.
이럴 때, 해시 테이블의 크기를 증가시켜 (보통 두 배로) 새로운, 더 큰 배열에 기존의 데이터를 재해시하여 저장하는 과정을 동적 리사이징이라고 합니다.
- 동적 리사이징은 주로 해시 테이블의 로드 팩터가 특정 임계값 (예: 0.75)을 초과할 때 발생합니다.
동적 리사이징 과정
- 로드 팩터를 주기적으로 확인하거나 삽입/삭제 작업마다 확인합니다.
- 로드 팩터가 일정 임계값을 초과하면 새로운 배열을 할당하고 기존 데이터를 재해시하여 새 배열에 저장합니다.
- 이후에는 새 배열을 사용하여 데이터를 관리합니다.
동적 리사이징을 통해 해시 테이블의 성능을 최적화할 수 있으며, 효율적인 데이터 관리를 위한 중요한 요소 중 하나입니다.
공부!