HashTable (해시테이블)

해시테이블?

• key, value로 데이터를 저장
• 빠른 검색속도를 제공. O(1)
• 각각의 key갑셍 해시함수를 적용해 배열의 고유한 index를 생성하고 이 index를 활용해 value를 저장/탐색한다.

해시함수

• key를 해시함수에 넣어서 가공하면 index값이 출력된다.
• 해시함수의 성능이 곧 hastTable의 성능이라고 할 수 있다.
• Division Method : 나눗셈을 이용. 입력값을 테이블의 크기로 나누어 계산
• Digit Folding : 각 key의 문자열을 ASCII코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용
• Multiplication Method : 숫자로 된 key값 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 계산. h(k) = (kAmod1) x m
• Univerail Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고 무작위로 해시함수를 선택해서 해시값 생성

해시충돌

만약 'Jon Smith'를 해시함수로 돌려서 나온 값과 'Tony Stark'를 해시함수로 돌려서 나온 값이 동일하다면?

이러한 문제를 해결하기 위해 크게 두가지의 방법을 사용한다

Separate Chaining(분리 연결법)

동일한 버킷 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 방식. Java8에서는 Self-Balancing Binary Search Tree 자료구조를 사용해서 Chaining방식을 사용하고 있다. Separate Chaining방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하다.  그러나 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소하는 단점이 있다.

Separate Chaining

Open Addresing (개방 주소법) 

추가적인 메모리를 사용하는 Chaining방식과 다르게 비어있는 해시테이블의 공간을 활용하는 방법이다.

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

Open Addresing

해시테이블 구현

충돌해결

• linkdelist를 이용한 Seperate Chaining방식 사용
• storage에 각각의 키값에 대한 linkedlist를 만들어주었다. (키값이 3개라면 linkedlist도 3개)
• storage에 저장된 linkedlist의 value는 [key, value]로 저장하였다.
• key값을 받으면 해시함수에 넣어서 index를 받은 후 해당 index의 storage에 찾아가서 [key, value]를 저장한다. 이 때, index에 값이 이미 존재 (key값을 해시함수에 넣어서 나온 값이 중복 - 충돌발생) 한다면 기존의 tail뒤에 [key, value]를 추가한다.
• linkedlist를 이용하면서 insert, retrieve메서드도 수정하였다. retrieve메서드를 호출하면 해시함수를 거쳐서 index를 얻은 후 해당 storage에 가서 key값에 해당하는 값을 검색 후 반환한다.

충돌의 경우의 수

 1) 여러개의 insert가 사용 된 경우
  a) key값을 해시함수에 돌렸을 때 index가 중복되는 경우
  b) key값을 해시함수에 돌렸을 때 index가 중복되지 않는 경우
 2) remove를 할 경우
  a) 중복되는 index에서의 remove
  b) 중복되지 않는 index에서의 remove
    b-1) 맨 앞의 key를 remove하는 경우
    b-2) 중간의 key를 remove하는 경우
    b-3) 맨 뒤의 key를 remove하는 경우

어려웠던 점

• 해시테이블의 기능 구현은 간단하였지만 충돌을 고려하는 순간 linkedlist와 hashtable의 다양한 요소들(객체, 배열)이 혼합되면서 원하는 요소를 어떻게 불러오고 사용해야 할 지가 가장 어려웠던 점이다.
• 충돌을 해결하기 위해 linkedlist를 이용한 Separate chaining을 사용하였는데, 기존의 linkedlist의 코드를 수정하면서 상당한 시간을 소요하였다.