해시테이블

해시테이블이란?

해시테이블 , 해시맵, 해시 표는

키를 값에 매칭할 수 있는 구조인 연관 배열 주가에 사용되는 자료구조이다.

해시테이블은 해시함수를 사용하여 index 를 bucket이나 slot의 배열로 계산한다.

버킷/ slot은 실제 값이 저장되는 장소이다.

빠르게 데이터를 검색할 수 있다고 한다.

빠른 검색속도를 제공하는 이유는 내부적으로 배열을 사용하여 데이터를 저장하기 때문이다. 특정 값을 search하는데 데데이터 고유의 인덱스로 접근게 되어 평균적인 case에 대해 time complexity가 O(1)이 된다.

하지만 데이터의 충돌이 발생하는 경우 Chaining에 연결된 리스트 까지 검색해야 할 경우 O(N)까지 시간복잡도가 증가 할 수 있다. (Chaining은 아래에서 다룬다.)

인덱스로 저장되는 key값은 불규칙하다.

해시 함수(hash function) 또는 해시 알고리즘(hash algorithm) 또는 해시함수알고리즘(hash函數algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

해시 함수에 의해 얻어지는 값을 해시값, 해시코드 , 해시체크섬 또는 간단히 해시 라고 한다.

해시테이블에서 사용되는 대표적 해시함수는 아래 3가지가 있다.

1. Division Method : 나눗셈을 이용하여 입력값을 테이블 크기로 나누어 계산한다.

2. Digit Folding : 각 key의 문자열을 ASCII코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법

3. Multiplication Method : 숫자로 된 key 값 k와 0~1사이의 실수 A, 그리고 2 의 제곱수인 m 을 사용 다음과 같은 계산을 한다.

h(k) = (k A mod1) * m

4. Univeral Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고 무작위로 해시함수를 선택, 해시값을 만드는 기법.

위와같이 서로 다른 입력값이 주어졌으나 출력이 동일하게 나오는 경우가 생길 수 있다.

이러한 문제를 크게 2가지 방법으로 해결하는 데 하나는 분리 연결법, 이며 다른하나는 개방 주소법이다.

분리 연결법은 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것으로 위의 그림에서 보듯 동일한 버킷으로 접근시 데이터들을 연결하여 관리한다.

java8의 hash테이블은 Self-Balancing Binary Search Tree 자료구조를 사용하여 Chaining 방식을 구현한다고 한다.

이러한 Chaining 방식은 해시 테이블의 확장이 불필요하고 간단히 구현 가능하며 손쉽게 삭제할 수 있다는 장점이 있으나 데이터의 수가 많아지면 동일한 버킷에 chaining된 데이터가 많아져 캐시의 효율성이 감소한다는 단점이 있다.

개방 주소법은 추가 메모리를 사용하는 Chaining기법과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. 대표적으로 3가지 방식이 존재한다.

현재의 버킷 인덱스로부터 고정폭 만큼 이동하여 차례대로 검색해 비어있는 버킷에 데이터를 저장하는 방법

해시의 저장순서 폴을 제곱으로 저장하는 방법

ex) 처음 충돌이 발생한 경우 1만큼 이동, 그다음 충돌 발생시 2^2. 3^2칸씩 옮기는 방법

해시된 값을 한번 더 해싱, 해시의 규칙성을 없애버리는 방식, 해싱된 값을 한번더 해싱하므로 다른방법보다 연산이 많아진다.