[자료구조] HashTable (해시테이블)

CS공부/자료구조

이숭간 2021. 7. 11. 18:50

728x90

해시테이블은 (key, Value)로 데이터를 저장하는 자료구조로, 빠르게 데이터를 검색할 수 있는 자료구조이다.

해시테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기때문이다.

각각의 key값에 해시함수를 적용해 배열의 고유index를 생성하고 이 index를 활용해 값을 저장,검색한다.

저장과정

1. key가 John Smith일때, 해시함수를 이용해 index를 계산한다.

2. array[index] = "521-1234"를 저장한다.

이렇게 저장하게되면 Key값으로 데이터를 찾을때 해시함수를 한번만 수행하면 바로 키값을 찾을수 있으므로 O(1)시간에 데이터를 저장.삭제,조회할수 있다.

즉, 특정 데이터를 검색하는데 있어 배열을 순차적으로 탐색할 필요없이 해시함수를 거쳐 생성된 해시값(인덱스)로 데이터를 바로 접근할수 있게되는것이다.

해시함수는 고유한 인덱스값을 설정하기위한 함수이다.

종류는 다음과같다.

1. Division Methond

2. Digit Folding

3. Multiplication Method

4. Univeral Hashing

John Smith를 해시함수에 넣어 얻어낸 결과값과 Lisa Smith를 해시함수에 넣어 얻어낸 결과값이 같은경우???

이러한 경우의 해결법은 다음과 같다.

1. 분리연결법

동일한 버킷으로 접근시, 추가메모리를 사용해 데이터를 연결해서 관리한다.

분리연결법의 경우 해시테이블의 확장이 필요없고, 구현이 간단하지만 데이터의 수가 많아지면 동일한 버킷에 연결되는(chaining)되는 데이터가 많아지며 그에따라 캐시 효율서이 감소한다는 단점이 있다.

2. 개방주소법

추가메모리를 사용하는 체이닝방법과는 다르게 비어있는 해시테이블 공간을 활용한다.

개방주소법을 구현하기위한 방법은 다음과 같다.

Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

평균적으로 O(1)의 시간을 갖지만 충돌이 일어나 연속적으로 검색되는경우 O(N)까지 시간복잡도가 증가될수 있다.

통계적으로 해시테이블의 공간사용률이 7~80%가 되면 충돌이 빈번하게 발생하여 성능이 저하되기 시작한다.

자바에서는 (키, 값)구조로 저장하는 자료구조인 HashMap이 있다. 이때 HashTable과의 차이는 동기화 지원여부이다.

따라서 병렬처리 상황에서 자원의 동기화를 고려해야 하는 상황이면 해시테이블을,

그렇지 않은 상황이라면 해시맵을 사용하는것이 좋다.

파이썬에서는 딕셔너리라는 자료구조를 제공해주기때문에 해시테이블을 직접 구현하지 않아도 간편하게 이용할수있다.