[TIL] HASH TABLE

HASH TABLE은?

• 데이터의 키값을 해시함수를 통해 인덱스화하고 배열의 해당 인덱스에 값을 저장하는 자료구조

  • 파이썬에서는 딕셔너리 타입이 해쉬 테이블과 같은 구조이다.

• 해시 테이블의 검색 성능은 해시 함수의 성능과 해시 테이블의 크기에 의해 좌우됨

  

장점

• Hash Key를 가지고 배열의 인덱스로 사용하기 때문에 삽입, 삭제, 검색이 빠름

단점

• Hash Function을 사용하는 데 추가적인 연산이 필요하며, 함수 특성 상 중복되는 값으로 인해 해시 충돌(Hash Collision) 이 발생할 수 있음

Hash Collision 방지

Chaining 방식

• 한 버킷에 들어갈 수 있는 자료의 수를 제한하지 않는 방식으로, Linked List를 활용해 해당 버킷에 데이터가 이미 존재하더라도 노드를 추가하여 다음 노드의 값을 가리키는 방식으로 구현

검색 및 삭제

• 검색 : 해시 함수를 통해 인덱스를 구하고 해당 인덱스의 Linked List를 선형적으로 검사하여 키와 노드를 확인하여 값을 리턴

• 삭제 : 검색과 동일한 절차로, Linked List를 검사하여 키와 노드를 삭제

Open Addressing

• 충돌이 발생했을 경우 Linked List와 같이 추가적인 메모리를 사용하지 않고 해시 테이블의 빈 버킷을 이용

• 충돌이 발생했을 경우, Chaining 방식과는 달리 데이터의 주소 값이 바뀜

Linear Probing

• 충돌을 해결할 수 있는 가장 간단한 해결법으로, 충돌이 발생한 위치에서 선형적으로 검색해 첫 번째 빈 영역에 키를 저장
• 구조가 간단하고 캐시의 효율이 높으나, 해시 테이블 전체를 검색해야하는 상황이 발생할 수 있음

Quadratic probing

• 고정 폭으로 이동하는 선형 탑사와 달리 폭을 제곱수(1, 4, 9, 16,...)로 늘려 탐사를 시작함

  

Double Hashing

• 하나의 해시함수에서 충돌이 발생하면 2차 해시 함수를 이용해 검색 이동거리를 얻는 방법으로 많은 연산량을 요구