Hash Table

본 문서는 2022년 1월 4일 에 작성 되었습니다.

Key-Value 쌍으로 이루어진 자료구조인 Table 의 종류에 대해서 알아보고자 합니다.

알아볼 Table 의 종류는 다음과 같습니다.

1. 직접 주소화 테이블
2. 체이닝 해시 테이블
3. 개방 주소화 해시 테이블

위 테이블의 내용을 설명하기 위하여 다음의 내용들도 포함하고 있습니다.

1. 다양한 해시
   1.1. 나누기 휴리스틱 해시
   1.2. 곱하기 휴리스틱 해시
   1.3. 유니버셜 해시
   1.4. 완전 해시

위 내용들을 모두 다 학습하고 Java 와 비교해볼 생각이며,
그 비교 대상은 다음과 같습니다.

1. 알고리즘학과 Java(jdk 1.8~) Collection Framework 의 용어 차이
2. 의사코드와 Java Collection Framework 메서드 코드

---

Table

부제 | 용어정리

전술한 Table 들을 설명하기 이전에,
Table 의 정의 및 용어 사전 정의를 하겠습니다.

# Table 이란?

이는 어떠한 데이터가 담겨있는 공간을 의미합니다.
기준값이 될 Key 와 내용이 될 Value 로 이루어진 공간을 의미합니다.

아래의 설명은 이해를 돕기 위한 예시입니다.
전술한 Table 에 따라 Key, Value 들에 대한 디테일들이 다릅니다.

## Key 란?

Key 는 어떠한 Value 가 담겨있는 주소에 해당하는 값입니다.

배열을 예로 들면,
우리가 배열에 접근하기 위하여 index 를 사용하게 되었는데
완벽하게 동일한 개념은 아니지만 기능적으로 주소를 가리치는 값 이라는 점이 유사합니다

## Value 란?

Value 는 Key 를 통해 접근하여 얻어낼 수 있는 정보 덩어리를 의미합니다.

배열로 예를 들면,
문자열 배열에는 각 칸 안에 문자열이 들어있고
객체 배열에는 각 칸 안에 객체가 들어있 음을 예로 들면,
이러한 문자열 혹은 객체가 정보 덩어리 이라는 점이 유사합니다.

# 사전정의

1. U 키의 전체 집합
2. K 키의 사용중 집합

---

직접 주소화 테이블

사실 참고 도서인 Introduce to Algorithm 에서는 이 부분을 자세히 다루고 있지 않았다
그러나 내가 이해한 바로는, 이 친구는 그저 배열 이라는 것이다.

# 의사코드

직접 주소화 테이블의 핵심 프로시저는 다음과 같다.

## search

DIRECT ADDRESS SEARCH (T, k)
   return T[k]

## insert

DIRECT ADDRESS INSERT (T, x)
   T[x.key]=x

## delete

DIRECT ADDRESS DELETE (T, x)
   T[x.key]=NIL

# 분석

직접 주소화 테이블의 특성은 다음과 같다.

1. 길이가 10인 배열과 구조상 유사하다.
2. search, insert, delete 모두 O(1) 이다.
3. U 가 크고 K 가 작을수록 여집합에 대한 낭비가 발생 한다.
4. 최대 적재율이 1이다.

---

일반적으로 우리가 해시 테이블이라고 하면 다음과 같다.

1. 체이닝 해시 테이블
2. 개방 주소화 해시 테이블

체이닝 해시 테이블

어떠한 입력값에 대하여 해시 함수 를 사용하여 얻은 출력값을 key 로 가진다.

해시 함수를 통과 할 경우 해시 충돌 이 일어날 수 있으며, 이 경우 Linked List 로 이를 해결한다. 이 경우 구현 상의 단순성을 위해서 Doubly Linked List(양방향 링크드 리스트로 구현해야 한다.

이것을 바로 Chaining (체이닝) 이라고 한다.

# 의사코드

체이닝 해시 테이블의 핵심 프로시저는 다음과 같다.

## insert

CHAINED HASH INSERT (T, x)
   Linked List T[ h(x.key) ] 의 맨 앞에 x 삽입

## search

CHAINED HASH SEARCH (T, k)
   Linked List T[ h(k) ] 에서 Key k 를 가지는 원소 검색

## delete

CAHINED HASH DELETE (T, x)
   Linked List T[ h(x.key) ] 에서 x로 삭제

# 분석

체이닝 해시 테이블의 특성은 다음과 같다.

1. insert 는 기본적으로 O(1) 이지만,
   Linked List 가 길어지면 해당 길이 m 만큼 늘어나 O(1+m) 이 된다.
2. delete 는 기본적으로 O(1) 이다.
3. 해시 충돌이 일어난 경우 Linked LIst 의 insert 와 delete 를 실행하게 되고
   이 과정에서 타켓 원소 x 의 앞 뒤에 x-1.next 및 x+1.prev 를 수정해야 한다.
   따라서 전술하였 듯이 Doubly Linked List (양방향 링크드 리스트) 를 사용해야 한다.
4. 해시 충돌이 최악의 경우를 만족한다면,
   Hash Table 의 모든 원소가 해시 충돌을 일으켰다는 것을 의미하고
   이는 모든 과정이 O(Hash Table) + O(Doubly Linked LIst) 된다는 것을 의미한다.
5. 최대 적재율이 1이 넘어갈 수 있으며, 제한이 없다.

---

개방 주소화 해시 테이블

Chaining 을 통해서 Hash Table 을 구현하는 과정에서 생기는 한계점인
해시 충돌 및 적재율에 관한 이슈를 해결하기 위한 방법으로 개방 주소화 를 사용하였다.

# 의사코드

개방 주소화 해시 테이블의 핵심 프로시저는 다음과 같다.

## insert

HASH INSERT (T, k)

   i=0
   
   reapeat
      j=k(k, i)
      
      if T[j]==NIL
         T[j]=k
         return j
         
      else
         i=i+1
         
   until j==m
   
   error "해시 테이블 포화"

## search

HASH SEARCH (T, k)

   i==0
   
   repeat
      j=h(k, i)
      
      if T[j]==k
         return j // Table 에 일치하는 key 가 있을 경우 리턴
      
      i=i+1
      
   until j==m OR T[j]==NIL
   
   return NIL // Table 에 일치하는 key 가 없을 경운

## delete

개방 주소화 해시 테이블에서의 삭제는 난이도가 높다.
삭제와 관련된 이슈는 다음과 같다.

1. 삭제 원소 DELETE 로 넣는다.
2. 삭제 횟수가 많아지면 체이닝 해시 테이블로 구현한다.

HASH DELETE (T, k)

   T[j]==DELETE // Table 에 일치하는 key 가 있을 경우, 해당 원소를 경계원소 DELETE 로 교체

---

Hash Basic

다양한 해시 함수를 학습하기 이전에 다음의 개념을 먼저 짚고 넘어가려고 합니다.

1. 좋은 해시 함수란?
2. 휴리스틱이란?
3. 자연수를 이용한 해시란?
4. 해시 충돌이란?

---

좋은 해시 함수란?

좋은 해시 함수는 일반적으로 단순 균등 해싱의 가정 을 만족하는 것을 의미한다.
그러나 이를 만족하지 못할 경우에는 휴리스틱을 사용하기도 한다.

단순 균등 해싱의 가정은 다음과 같다.

1. 다른 키와 해시된 위치 와는 무관하게
   키가 m 개의 자리 중 하나에 균등한 확률로 해시된다

단순 균등 해싱은 다음과 같든 한계점을 가진다.

1. 키가 추출되는 확률 분포를 알기 어려워서, 이를 증명하기 어렵다.

---

휴리스틱이란?

휴리스틱은 사람들이 빠르게 사용할 수 있는 간편 추론법 혹은 문제 해결법 을 의미한다.

휴리스틱은 다음의 경우에 사용한다.

1. 불충분한 시간, 정보 등으로 합리적인 판단을 할 수 없을 때
2. 체계적 및 합리적 판단이 중요하지 않을 때

---

자연수를 이용한 휴리스틱

이 내용은 휴리스틱에 대한 감을 잡기 위한 단순 예제에 불과하고
실제로 해시 테이블에서 휴리스틱을 사용하는 것은 아래에 따로 필기 하였다.

어떠한 문자열을 128진법으로 표기하는 방법을 휴리스틱 으로 해결할 수 있을까?

이에 대해서 Instroduce to Algorithm 은 다음의 방법을 예로 들었다.

1. String 을 ASCII Code 로 변환
2. ASCII Code 를 10진법 행렬로 표기
3. 10진법 행렬을 휴리스틱으로 128진법으로 표기

문자열 pt 로 예를 들어보면,
아래와 같이 간단한 휴리스틱을 찾을 수 있다.

1. p=112(ASCII Code)
   t=116(ASCII Code)
2. 10진법 행렬=(112,116)=(112*10)+116 ...?
3. 128진법=(112*128)+116=14452

---

해시 충돌이란?

뒤에서 언급할 해시 함수는 간단하게 설명하면 다음과 같다.

익명 입력값 k1 을
해시 함수 h 에 넣으면
익명의 출력값 h(k1) 을 반환한다.

그러나 드문 경우로 익명 익력값 k1, k2 가 충돌이 일어날 수도 있다.
이러한 경우를 해시 충돌이라고 말하며 다음의 함수식으로 표기할 수 있다.

h(k1)==h(k2)

주로 바로 뒤에서 설명할 휴리스틱 해시 기법을 사용할 시 발생한다.

이러한 해시 충돌을 악의적으로 노리는 경우도 있으며 이를 방지하기 위해 유니버셜 해시 기법 이 사용되기도 한다.

자세한 내용은 아래에서 확인해보자.

---

Several Hash Functions

다음과 같은 해시 함수에 대해서 알아볼 생각입니다.

1. 휴리스틱을 이용한 해시 함수
   1.1. 나누기 해시 함수
   1.2. 곱하기 해시 함수
2. 유니버셜 해시 함수
3. 완벽 해시 함수

---

휴리스틱 - 나누기 해시 함수

# 의사코드

h(k) = k mode m // Key k 를 기준값 m 으로 나눈 나머지

# 분석

1. 나누기 해시는 매우 빠르다.
2. 해시 기준값 m 에 대한 제약조건이 존재한다.
   2.1. m 은 소수(1과 본인으로만 나누어지는 자연수) 로 해야 한다.
   2.2. m 은 k의 특성을 고려하여 특정 값을 피해야 한다.

위 2 번에 대한 예시로는,
만약 Key k 가 문자열 이라면 이는 2^p 기수법으로 표기될 것이다.

따라서 m은 2로 나누어 떨어지는 숫자 즉, 2^n(n 은 익명의 값) 여서는 안된다.
또한 m은 2^n +- 1(b는 익명의 상수) 여서도 안된다.

그 이유는 위 조건을 무시할 경우 해시 충돌이 많이 발생 하기 떄문이다.

더 디테일한 수치를 들어보면,
n=2000 개의 문자열이 key 로 존재한다면
권고되는 해시함수는 701 이고 이 경우 최악의 경우 3 번의 해시 충돌이 발생할 수 있다.
임의의 값 k1, k2, k3 가 h(x) 를 통해서 산출된 h(k1)=h(k2)=h(k3) 가 될 수 있다는 뜻이다.

그러나,
701 은 소수이며 2^n(n은 익명의 값)과 꽤나 먼 거리를 유지하고 있는데,
이 값과 가장 가까운 2의 제곱수인 512, 1024 를 생각해보면 중앙에 가까움을 알 수 있다.

---

휴리스틱 - 곱하기 해시 함수

# 의사코드

아래는 곱하기 해시 함수를 의미하며 각 알파벳은 다음의 값을 의미한다.

1. m
2. Key k
3. 0 < A <1 범위 상수
4. └ ┘ 소수점 이하를 내린다는 의미

h(k) = └ m (k*A mod 1) ┘
// 키 값을 소수점 값과 곱하고, mod 1로 소수점 이하만 남긴다.
// 이에 m 을 곱하고 다시 소수점 이하를 없애고 나면 그 값을 최종 Key 값으로 사용한다.

# 분석

나누기 해시 함수와는 달리 m 이 중요하지 않다.
일반적으로 2의 지수승 값(2^p) 을 선택한다.

---

유니버셜 해시 함수

후술하겠다.

---

완벽 해시 함수

후술하겠다.