Direct-Address tables

크기가 U인 테이블 T를 생성하고 key k를 slot k에 저장하는 방식
중복되는 key 가 없다.

주요 특징
시간복잡도가 정말 빠르다.
키 값에 연결되어있다면 키에 연결된 값을 바로 들고올 수 있다.

대신, 공간 복잡도가 크다.

• $\theta(|U|)$
  공간을 미리 잡아놓도 실제로 사용하는 키 값만을 사용하기 때문에 공간을 낭비하게 된다.
• 실제 공간 사용을 전체 공간으로 나눈 $|K|/|U|$를 적재율이라고 한다.
• 만약 적재율이 낮다면, 실제로 대부분의 공간은 낭비된다.

Hash Tables

해슁(Hashing)

• key $k$를 저장할 때 slot $k$에 저장하는 것이 아니라 slot $h(k)$에 젖아한다.

동일한 해쉬 값을 가지는 키가 존재할 수 있음. - Collision

수행시간 분석

• $Insertion:O(1)$
• $Deletion: O(1)$
• $Search: O(1)$

Collision

• 두 개의 key가 동일한 hash 값을 갖는 경우 - 충돌

체인을 이용한 충돌 해결법

• 중복되는 key 값이 있을 경우 해당 슬롯을 연결리스트로 저장한다.

길이가 긴 리스트가 생성된다면 특정한 키 값을 찾기 위해서는 해당 하는 슬롯에 가서 링크드 리스트를 따라가며 원하는 값을 찾아야 하는 경우가 생김.

• 리스트 탐색 시간 복잡도 : $O(n)$
  체인이 생겨 n 시간만큼의 시간복잡도가 생기면 사용한 이유가 모순됨.

Worst case
$\theta(n)$

Average Case
$\theta(1+a)$
적재율 $a = n/m$
$n$은 테이블의 원소 개수이고 m은 slot의 수

좋은 해쉬 함수

simple uniform hashing을 만족하는 해쉬 함수

• 각가의 key는 중복 없이 m 개의 slot으로 동일한 확률로 해쉬 되며(simple)
• 각각의 key는 다른 key값의 해쉬값과 관계없이 해쉬 된다.(Uniformly)

해쉬 함수

나눗셈 방법

• $h(k) = k \mod m$
  m = 12, k = 100
  $h(k) = 100 \mod 12 = 4$

효율적인 m의 선택 방법

$m = 2^p$인 경우는 피하는 것이 좋다.

• $m = 2^p$다 되면 해쉬 함수 h(k)는 키 k의 하위 p비트가 된다.

$m = 2^p -1$ 도 피하는게 좋다. 2의 지수에 가까운 소수를 선택하는것이 제일 좋음.