Hash Table
해시 함수를 사용하여 변환한 값을 인덱스로 감아 key와 value를 저장하는 자료구조기본연산
- 탐색(Search)
- 삽입(Insert)
- 삭제(Delete)
Direct Address Table
가장 간단한 형태의 해시 테이블로 이름 뜻대로 키 값을 주소로 사용하는 테이블탐색, 삽입, 삭제 연산을 모두 O(1)에 할 수 있지만 다음과 같은 한계점이 있다.
- 최대 키 값에 대해 알고 있어야 한다.
- 최대 키 값이 작을 때 실용적으로 사용할 수 있다.
- 키 값들이 골고루 분포되어있지 않다면 메모리 낭비가 심할 수 밖에 없다.
ex)
키 값: 100
배열의 인덱스: 100에 원하는 데이터 저장
Hash Table
해시 함수를 사용해 특정 해시 값을 알아내고 그 해시 값을 인덱스로 변환하여 키 값과 데이터를 저장하는 자료구조적재율
해시 테이블의 크기 대비, 키의 개수키의 개수: K
해시 테이블의 크기: N
적재율: K/N
Direct Address Table은 키 값을 인덱스로 사용하는 구조이기 때문에 적재율이 1 이하이며 적재율이 1 초과인 해시 테이블의 경우는 반드시 충돌이 발생하게 된다.
해시 충돌
충돌이 발생하지 않았을 때 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 실행되지만,
충돌이 발생했을 때엔 탐색과 삭제 연산이 O(K)만큼 걸리게 된다.
예)
ARGOS와 MINIBEEF가 같은 해시 값을 가지며 충돌이 발생
해시 충돌 완화
개방 주소법으로 해시 테이블 크기는 고정하면서 저장할 위치를 찾거나,
분리 연결법으로 해시 테이블의 크기를 유연하게 만드는 방법이 대표적
개방 주소법
한 버킷 당 들어갈 수 있는 엔트리는 하나이지만 해시 함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용하는 방법하지만 이 방법은 부하율이 높을수옥 성능이 급격히 저하된다.
개방 주소법의 주요 목적은 저장할 엔트리를 위한 다음의 slot을 찾는 것인데 이방법으로 2가지가 있다.
선형 탐사법
가장 간단하게 선형으로 순차적 검색을 하는 방법해시 함수로 나온 해시 인덱스에 이미 다른 값이 저장되어 있다면, 해당 해시 값에서 고정 폭을 옮겨 다음 해시 값에 해당하는 버킷에 액세스한다.
이 경우엔 특정 해시 값의 주변이 모두 채워져 있는 일차 군집화 문제에 취약하다. 따라서 이 방법은 해시 충돌이 해시 값 전체에 균등하게 발생할 때 유용한 방법이다.제곱 탐사법
선형 탐사법과 동일한데, 고정폭이 아닌 제곱으로 늘어남따라서 제곱 탐사법을 이용한 경우 데이터의 밀집도가 선형 탐사법보다 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 가능성이 적다.
하지만 선형 탐사법보다는 캐시의 성능이 떨어져서 속도의 문제가 발생한다.이중 해싱
탐사할 해시값의 규칙값을 없애서 클러스터링을 방지즉 해시 함수를 이중으로 사용하는데, 하나는 최초의 해시값을 얻을 때, 다른 하나는 해시 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다.
이렇게 되면 최초 해시값이 같더라도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라져 위의 두 방법을 모두 완화할 수 있다.
분리 연결법
한 버킷(슬롯) 당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음이때 버킷에는 링크드 리스트(linked list)나 트리(tree)를 사용
해시 충돌이 일어나더라도 linked list로 노드가 연결되기 때문에 index가 변하지 않고 데이터 개수의 제약이 없다는 장점이 있다.
하지만 메모리 문제를 야기할 수 있으며, 테이블의 부하율에 따라 선형적으로 성능이 저하된다. 따라서 부하율이 작을 경우에는 open addressing 방식이 빠르다.
참고한 블로그 링크
