11. Hash Tables

11 Hash Tables

많은 프로그램들은 오직 dictionary operations들인 INSERT, SEARCH, 그리고 DELETE만을 지원하는 dynamic set을 요구한다. 예를들어, 프로그래밍 언어를 번역하는 한 컴파일러는 symbol table를 유지하고, 그 테이블에서, 원소들의 키들은 임의의 문자 스트링들인데, 그 문자열들은 그 언어에서 identifiers와 일치한다. 한 hash table은 dictionaries를 구현하는데 효과적인 자료구조이다. 해쉬 테이블에서 한 원소를 탐색하는 것이 링크드 리스트에서 한 원소를 탐색하는 만큼 길게 거릴ㄹ 수 있다. 최약의 경우에 theta(n) 시간. 실제로, hashing은 매우 잘 수행된다. 합리적인 가정하에서, 해쉬테이블에서 한 원소를 탐색하는 평균시간은 O(1)이다.

해쉬 테이블은 평범한 배열의 더욱 간단한 개념을 일반화 시킨다. 직접적으로 한 평범한 배열에 주소를 지정하는 것은 한 배열에서 임의의 위치를 검사하는 우리의 능력을 O(1)안에 효과적으로 만들어준다. Section 11.1은 좀 더 세부적으로 direct addressing에 대해 다룬다. 우리는 모든 가능한 키에 대해 하나의 위치를 가지는 한 배열을 할당할 여유가 있을 때, direct addressing의 이점을 취할 수 있다.

실제로 저장된 키의 개수가 가능한 키의 개수보다 상대적으로 적을 때, 해쉬 테이블은 한 배열을 직접적으로 주소 지정하는 것에 대해 효과적인 대안이 된다. 왜냐하면 해쉬 테이블은 일반적으로 실제로 저장되는 키의 개수와 비례한 사이즈의 한 배열을 사용하기 때문이다. 한 배열의 인덱스로서 직접적으로 키를 사용하는 대신에, 배열 인덱스는 키로부터 계산된다. Section 11.2는 그 주된 아이디어를 보여주고, "collisions"를 다루는 방법으로서의 "chaining"에 집중한다. "collisions"은 한 개 이상의 키가 같은 배열 인덱스에 매핑되는 것이다. Section 11.3은 어떻게 우리가 해쉬 함수를 사용하여 키로부터 배열 인덱스를 연산할 수 있는지를 묘사한다. 우리는 기본 주제에 대해 몇 가지 변형을 보여주고 분석한다. Section 11.4는 "open addressing"을 보게된다. 그것은 collisions를 다루는 또 다른 방법이다. 강조할 점은 hashing은 매우 효과적이고 실용적인 기법이라는 것이다: 기본 dictionary operations들은 평균적으로 오직 O(1) time을 요구한다. Section 11.5는 저장되어 있는 키들의 집합이 정적일 때 (즉, 키들의 집합들이 한 번 저장되면 바뀌지 않을 때) 어떻게 "perfect hasing"이 최악의 경우에 O(1) time안에 탐색을 지원할 수 있는지를 설명한다.

11.1 Direct-address tables
Direct addressing는 키의 universe U가 합리적으로 작을 때 잘 작동하는 간단한 기법이다. 한 프로그램이 각 원소가 universe U = {0, 1, ... , m -1 }로부터 오는 키를 가지는 dynamic set을 필요하다고 가정하자. 여기에서 m은 그렇게 크지 않다. 우리는 어떠한 두 원소가 같은 키를 갖지 않는다고 가정할 것이다.

dynamic set을 나타내기 위해, 우리는 T[0..,-1]로 나타내어지는 direct-address table인 한 배열을 사용한다. 거기에서 각 위치, 또는 slot,은 universe U에 있는 키와 동일하다. 그림 11.1은 그 접근법을 보여준다; slot k는 key k를 가진 집합에서 한 원소를 가리킨다. 만약 그 지합이 key k와 함께 어떠한 원소도 포함하지 않는다면, T[k] = NIL이다.

dictionary operations는 구현하기 쉽다:

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

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

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

이러한 연산들 각각은 오직 O(1) 시간이 걸린다.

몇 가지 적용에 대해, direct-address table은 그 자체로 dynamic set에서의 원소들을 유지할 수 있다. 즉, 그 direct-address table의 외부에 있는 한 오브젝트에 있는 한 원소의 key와 satellite data를 유지하기보다 오히려 테이블에서 한 slot에서 그 object를 향하는 포인터로, 우리는 그 오브젝트를 자체를 슬롯에 저장할 수 있다. 따라서 이것은 공간을 절약한다. 우리는 비어있는 slot을 나타내기 위해서, 한 오브젝트 내에 특별한 key를 사용할 것이다. 게다가, 그 오브젝트의 key를 저장하는 것은 불필요하다. 왜냐하면 만약 우리가 테이블에서 한 오브젝트의 인덱스를 가진다면, 우리는 그것의 키를 가지고 있기 때문이다. 그러나 만약 키가 저장되지 않는다면, 우리는 그 슬랏이 empty하는지 구분할 몇 가지 방법을 가져야 한다.

Exercises
11.1-1
동적 집합 S가 길이가 m인 direct-address table T에의해 나타내진다고 가정하자. S의 최대 크기 원소를 찾는 절차를 묘사해라. 너의 절차의 최악의 경우 성능은 어떤가?
-> table에서 맨 뒤에서 부터 찾는다고 가정한다. 그 원소가 첫 번째에 있는 경우 O(m)이다.

11.1-2
bit vector는 간단히 비트들의 한 배열이다. (0들과 1들로 된) 길이가 m인 비트 벡터는 m개의 포인터를 가진 배열보다 공간을 덜 차지한다. satellite data가 없는 별개의 원소로 구성된 dynamic set을 나타내기 위해 bit vector를 어떻게 사용할지를 묘사해라. Dictionary operations는 O(1) 시간안에 작동해야만 한다.
-> data n을 저장할 때, n번째 비트를 1로 설정한다.

11.1-3
저장된 원소들의 키들이 구별될 필요가 없고, 그 원소들이 satellite data를 가질 수 있는 direct-address table를 어떻게 구현할지 제안해라. 모든 이러한 dictionary operations(INSERT, DELETE, and SEARCH)는 O(1) 시간 안에 작동해야만 한다. (DELETE가 키가 아닌 지워질 오브젝트에 대한 포인터를 인자로 받아야 하는 것을 잊지마라.)
-> 우선 direct-address table에 저장될 원소가 한 링크드리스트의 head에 대한 포인터라고 하면 문제에서 제시한 대로 구현할 수 있다.

11.1-4
 우리는 큰 배열에서 direct addressing을 사용하여 dictionary를 구현하길 원한다. 처음에, 그 배열 entries들은 garbage값을 포함할지도 모른다. 그래서 전체 배열을 초기화 하는 것은 비 실용적이다. 그것의 사이즈 때문에. 큰 배열에 대한 direct address dictionary를 구현하는 전략을 묘사해라. 각 저장된 오브젝트는 O(1) space를 사용해야만 한다; SEARCH, INSERT, 그리고 DELETE 연산들은 각각 O(1) 시간이 걸려야만 한다; 그 자료구조를 초기화하는 것은 O(1) 시간이 걸려야 한다. (Hint: 어느정도 스택처럼 다뤄지는 부가적인 배열을 사용해라. 그 스택의 사이즈는 dictionary에 실제 저장되는 키들의 개수이다. 이것은 큰 배열에서 주어진 entry가 유효한지 또는 그렇지 않은지를 결정하는 것을 돕기 위해서이다.)
-> 잘모르겠다..

11.2 Hash tables
direct addressing의 단점은 명백하다: 만약 universe U가 크다면, size |U|인 테이블 T를 저장하는 것은 비실용적일지도 모르고, 또는 심지어 불가능할지도 모른다. 일반적인 컴퓨터에서의 이용가능한 메모리를 고려한다면. 게다가, 실제로 저장된 key들의 집합 K는 U를 기준으로 너무 작을지도 몰라서, T를 위해 할당된 공간의 대부분이 낭비될지도 모른다.

dictionary에 저장된 keys들의 집합 K가 모든 가능한 keys들의 universe U보다 작을 때, hash table은 direct address table보다 더 적은 storage를 요구한다. 더 자세히 해서, hash table에서 한 원소를 탐색하는 것이 오직 O(1)시간을 요구한다는 장점을 유지하면서 우리는 저장 요구사항을 Ө(|K|)로 줄일 수 있다.  중요한 점은, 이 제한이 average-case time이라느 ㄴ것이다. 반면에, direct addressing은 worst-case time에 대해 유효하다.

direct addressing과 함께, key k를 가진 한 원소는 slot k에 저장된다. hasing으로는, 이 원소는 slot h(k)에 저장이된다; 즉, 우리는 hash function h를 key k로부터 slot을 연산하기 위해 사용한다. 여기에서 h는 key들의 universe U를 hash table T[0..m-1]의 slots들로 사상시킨다:

h : U -> {0, 1, ... , m-1},

여기에서 hash table의 사이즈 m은 일반적으로 |U|보다 작다. 우리는 key k를 가진 한 원소가 slot h(k)로 hashes한다고 말한다; 우리는 또한 h(k)는 key k의 hash value라고 말한다. 그림 11.2는 기본적인 아이디어를 보여준다. 그 해쉬 함수는 배열 인덱스들의 범위를 줄이고, 그러모르 배열의 사이즈를 줄인다. |U|의 사이즈 대신에, 그 배열은 m의 사이즈를 갖는다.

한 가지 문제가 있다: 두 개의 키들이 같은 slot에 해쉬할지도 모른다. 우리는 이 상황을 collision이라고 부른다. 운 좋게도, 우리는 충돌에 의해 말들어진 문제를 해결하는 효과적인 기법을 가지고 있다.

물론, 이상적인 해결책은 전적으로 충돌을 피하는 것일 것이다. 우리는 적절한 해쉬 함수 h를 선택하여 이 목표를 달성하려고 노력한다. 한 가지 아이디어는 h가 "무작위"인 것처럼 보이게 만드는 것이다. 따라서 이것은 충돌을 피하거나 또는 적어도 그 충돌 횟수를 최소화한다. 무작위하게 섞이고 잘라진 것의 이미지를 불러일으키는 "to hash"한다는 용어는 이 접근법의 정신을 가지고 있다. (물론, 해쉬 함수 h는 주어진 input k가 항상 같은 output h(k)를 만들도록 결정적이여야만 한다. 그러나, |U| > m이기 때문에, 같은 hash value를 갖는 적어도 두 개의 keys들이 있음에 틀림없다; 충돌을 전적으로 피하는 것은 그러므로 불가능하다. 따라서, 잘 설계되고, "무작위"하게 보이는 hash function이 충돌의 횟수를 줄일 수 있는 반면에, 우리는 여전히 발생하는 충돌을 해결하는 방식이 필요하다.

이 섹션의 나머지는 가장 간단한 충돌 해결 기법을 보여준다. 소위 chaining이라고 불리는. Section 11.4는 open addressing이라고 불려지는 충돌을 해결하는 다른 방법을 소개한다.

Collision resolution by chaining
chaining에서, 우리는 같은 slot으로 hash하는 모든 원소들을 같은 linked list에 배치한다. 그림 11.3 에서 보여주듯이. Slot j는 j로 해쉬하는 모든 저장된 원소들의 list의 head에 대한 포인터를 포함한다. 만약 그러한 원소가 없다면, slot j는 NIL을 포함한다.

hash table T에서 dictionary operations는 충돌이 chaining으로 해결될 때, 구현하기에 쉽다.

CHAINED-HASH-INSERT(T,x)
1 insert x at the head of list T[h(x.key)]

CHAINED-HASH-SEARCH(T,k)
1 search for an element with key k in list T[h(k)]

CHAINED-HASH-DELETE(T,x)
1 delete x from the list T[h(x.key)]

insertion에서 최악의 작동시간은 O(1)이다. 삽입 절차는 부분적으로 빠르다. 왜냐하면 삽입되고 있는 원소 x가 이미 테이블에 존재하지 않다고 가정하기 때문이다; 필요하다면, 우리는 이 가정을 확인할 수 있다 (부가적인 비용으로). 이 때 우리가 삽입하기 전에 key가 x.key인 한 원소를 찾아야 한다. 탐색에 대해서, 최악의 작동 시간은 리스트 길이에 비례한다; 우리는 이 연산을 아래에서 좀 더 자세하게 분석할 것이다. 우리는 리스트가 더블 링크드 리스트라면 O(1) 시간에 한 원소를 지울 수 있다. 그림 11.3가 묘사하듯이. (CHAINED-HASH-DELETE가 key k가 아닌, 원소 x를 받는다는 것에 유의해라. 이것은 우리가 x를 처음에 탐색할 필요 없는 것이다. 만약 해쉬테이블이 deletion을 지원한다면, 그것의 linked lists는 더블 링크드 리스트여야만 한다. 이것은 우리가 한 item을 빠르게 지울 수 있게 하기 위해서이다. 만약 그 lists가 singly linked라면, 그러면 element x를 지우기위해서, 우리는 처음에 T[h(x.key)]에 있는 list에서 x를 찾아야만 한다. 이것은 우리가 x의 predecessor의 다음 next attribute를 업데이트할 수 있게 하기 위해서이다. singly linked lists로, deletion과 searching은 같은 asymptotic running times를 갖게 된다.)

Analysis of hashing with chaining
hashing은 chaining으로 어떻게 잘 수행하는가? 특히, 주어진 key가 있는 한 원소를 찾는데 얼마나 걸리는가?

n개의 원소들을 저장하는 m개의 slots을 가진 해쉬테이블 T를 고려하면, 우리는 T에 대해 load factor a를  n/m으로 정의한다. 즉, 한 chain에 저장된 원소의 평균 개수이다. 우리의 분석은 이 a의 관점ㅇ네서 될 것이다. 이것은 1보다 작거나 동일하거나 또는 더 클 수도 있다.

chaining으로 hashing하는 것의 최악의 경우 행동은 끔찍하다: 모든 n keys들이 같은 slot에 hash하고, n개의 길이의 list를 만드는 것이다. 탐색의 worst-case time은 따라서 Ө(n) + hash function 연산시간이다. - 만약 우리가 모든 원소들에 대해 one linked list를 사용했다면 더 나쁘다. 명백히, 우리는 worst-case performance 때문에 hash tables를 사용하지 않는다. (Section 11.5에서 묘사되는 Perfect hasing은 key의 집합이 정적일 때, 좋은 worst-case performance를 제공한다. 그러나.)

hashing의 평균 케이스 perforamance는 hash함수가 m개의 slot 사이에서 얼마나 잘 저장될 키들의 집합을 분산 시키는가에 의존한다 평균적으로.

Section 11.3은 이러한 문제들을 다루지만, 지금은 우리는 어떤 주어진 원소가 동일하게 m개의 slots들로 hash into할 가능성이 높다고 가정할 것이다. 이것은 어떤 다른 원소가 어디로 hashed to하는 거와 독립적이다. 우리는 이것을 simple uniform hashing의 가정이라고 부른다.

j = 0, 1, ..., m - 1 에 대해, T[j] 리스트의 길이를 n_j라고 표기하자. 다음과 같이 하기 위해서
n = n_0 + n_1 + .... + n_m-1

그리고 n_j의 기대되는 값은 E[n_j] = a = n/m.

우리는 O(1) 시간이 해쉬 값h(k)를 연산하는데 충분하다고 가정한다. 이것은 key k를 가진 한 원소를 탐색하는데 요구되는 시간이 선형으로 list T[h(k)]의 길이 n_h(k)에 의존하도록 하기 위해서이다. 해쉬 함수를 연산하고, h(k) slot에 접근하는데 요구되는 O(1) time을 제쳐두고, 우리가 search algorithm에 의해 조사되는 원소들이ㅡ 예상되는 개수를 고려해보자. 즉, list T[h(k)]에서의 원소들이ㅡ 개수이다. 그 때 알고리즘은 어떤 것이 k와 동일한 값을 가지는지를 보기 위해 그 리스트를 체크한다. 우리는 두 가지 경우를 고려할 것이다. 첫 번째, 그 search가 성공적이지 않을 때: 그 테이블에 어떠한 원소도 key k를 가지지 않는다. 두 번째, search가 성공적으로 key k를 가진 원소를 찾는다.

Theorem 11.1
충돌이 chaining으로 해결되는 hash table에서, 성공적이지 않은 탐색은 평균 시간 Ө(1 + a)의 시간이 걸린다. simple uniform hashing의 가정하에서.

Proof simple uniform hashing가정 하에서, 테이블에 이미 저장되지 않은 어떤 키 k는 동일하게 m개의 slots중에 어떤 것으로 hash할 가능성이 높다. key k에 대해 성공적이지 못하게 탐색하는 예상되는 시간은 list T[h(k)]의 끝까지 탐색하는데 걸리는 예쌍된 시간이고, 이것은 legnth E[n_h(k)] = a를 기대하게 된다. 따라서, 성공하지 못한 탐색에서 조사되는 원소들이ㅡ 예쌍되는 개수는  a이고, 요구되는 총 시간 (h(k)를 연산하는 시간을 포함해서)
Ө(1 + a)이다.

성공적인 탐색에 대한 상황은 조금 다르다. 왜냐하면 각 list는 동일하게 탐색될 가능성이 높지 않기 때문이다. 대신에, 한 리스트가 탐색될 가능성은 그것이 포함하고있는 원소들의 개수와 비례하다. 그럼에도 불구하고, 예상되는 탐색 시간은 여전히 Ө(1+ a)로 밝혀진다.

Theorem 11.2
충돌이 chaining으로 해결되는 hash table에서, 성공적인 평균 케이스 탐색 시간은 Ө(1+a)이다. simple uniform hashing의 가정하에서.

Proof 탐색되고있는 원소가 동일하게 그 테이블에 저장된 n개의 원소들 중 어떤 것일 가능성이 높다고 우리는 가정한다. 한 원소 x에 대해 성공적인 탐색 동안에 검사되는 원소들의 수는 x의 list에서 x전에 나타나는 한 개 이상의 원소들의 수이다. 새로운 원소들은 그 list의 앞에 배치되기 때문에, 리스트에서 x 이전에 원소들은 모두 x가 삽입된 이후에 삽입된 것이다. 조사되는 원소들의 예상된 숫자를 알기 위해서, 우리는 테이블에서 n개의 원소들 x에 대해서 (1 + x가 리스트에 들어간 이후의 x의 list에 더해진 원소의 개수)의 평균을 취한다. x_i가 테이블에 삽입된 i번쨰 원소라고 표기하자. i = 1,2,..., n,이고. k_i = x_i.key라고 하자. keys들 k_i와 k_j에 대해, 우리는 indicator random variable X_ij = I{h(k_i) = h(k_j)}라고 정의한다. simple uniform hashing의 가정 아래에서, 우리는 Pr{h(k_i) = h(k_j)} = 1/m을 갖는다. 그래서 Lemma 5.1에 의해, E[X_ij] = 1/m이 된다. 따라서  ~~~

이 분석이 무엇을 의미하는가? hash-table slots의 개수는 적어도 테이블에 있는 원소들의 개수와 비례한다면, 우리는 n = O(m)을 갖게되고, 결과적으로 a = n/m = O(m)/m = O(!)이다. 따라서, 탐색은 평균적으로 상수 시간이 걸린다. 삽입이 O(1)의 worst-case time이 걸리고, 삭제가 O(1) worst-case time이 걸리기 때문에 리스트가 더블링크드리스트일 때, 우리는 평균적으로 O(1) 시간안에 모든 dictionary operations를 지원할 수 있다.

Exercises
11.2-1
우리가 n개의 다른 키들을 길이가 m인 배열 T에 hash하는 해쉬 함수를 사용한다고 가정하자. simple uniform hashing을 가정하여, 예상되는 충돌 횟수는 무엇인가? 좀 더 정확하게,
-> pass

11.2-2
우리가 key 5, 28, 19, 15, 20, 33, 12, 17, 10을 chaining으로 해결되는 collisions을 가진 해쉬테이블에 넣을 때 무슨일이 일어나는지 묘사해라. 테이블은 9개의 슬랏을 가지고, 해쉬 함수는 h(k) = k mod 9라고 하자.

0
1 10 19 28
2 20
3 12
4
5 5
6 27 15
7
8 17

11.2-3
Marley 교수는 그가 정렬된 순서에서 각 리스트를 유지하도록 chaining scheme을 수정하여 상당한 성능 향상을 얻을 수 있다고 가설을 세운다. 그 교수의 수정이 성공적인/성공적이지 않은 탐색, 삽입, 삭제의 running time에 영향을 어떻게 미치는가?

~~~

11.3 Hash functions
이 섹션에서, 우리는 좋은 해쉬 함수의 설계와 관련된 문제를 이야기하고, 그러고나서 그것들을 만드는데 있어서 세 가지 전략을 보여준다. 그 전략중에 두 가지인 hashing by division과 hashing by multiplication은 기본적으로 heuristic이다. 반면에 세 번째 전략인 universal hashing은 증명적으로 좋은 성능을 제공하는 랜덤화를 사용한다.

what makes a good hash function?
좋은 해쉬 함수는 (대략적으로) simple uniform hashing의 가정을 만족시킨다: 각 key는 동등하게 m개의 slots중에서 어떤 것으로 동등하게 hash할 가능성이 높다, 어떤 다른 키가 hashed하는 곳과 상관없이. 불행하게도, 우리는 일반적으로 이 조건을 확인할 방법이 없다. 왜냐하면 우리는 거의 키가 끌어와지는 확률 분포를 모르기 때문이다. 게다가, 키들은 독립적으로 끌어와지지 않는다.

때때로, 우리는 분포를 안다. 예를들어, 만약 우리가 그 키들이 범위 0<= k <=1에서 독립적으로 그리고 균등하게 분산되는 무작위 실수 k라는 것을 안다면, 그 해쉬함수는
h(k) = floor(km)는 simple uniform hashing의 조건을 만족한다.

실제로, 우리는 종종 잘 작동하는 해쉬 함수를 만들기위해서 heuristic techniques을 이용할 수 있다.  keys들의 분산에 대한 질적 정보는 이 설계 프로세스에서 유용할지도 모른다. 예를들어, 컴파일러의 심볼 테이블을 고려해라. 거기에서 keys들은 한 프로그램에서 identifiers를 나타내는 문자 strings이다. pt와 pts와 같은 가까이 관련된 symbols들은 종종 같은 프로그램에서 발생한다. 좋은 hash function은 그러한 variants가 같은 slot으로 hash할 가능성을 최소화 할 것이다.

좋은 접근법은 우리가 데이터에 존재할지도 모르는 어떤 패턴과 무관하도록 기대하는 hash value를 끌어낸다. 예를들어, (Section 11.3.1에서 이야기되는) "division method"는 key가 특정한 소수로 나누어질 때의 나머지로서 해쉬값을 연산한다. 이 방식은 자주 좋은 결과를 준다. 이것은 우리가 keys들의 분포에서 어떤 패턴과 상관없이 소수를 선택한다고 가정하는 것이다.

마지막으로, 우리는 해쉬 함수들의 몇몇 적용은 simple uniform hashing에 의해 제공되는 더 강항 특징을 요구한다는 것을 주목해라. 예를들어, 우리는 어떤 의미에서 꽤 떨어진 hash values를 만들어내기 위해 가까운 키들을 원할지도 모른다. (이 특징은 Section 11.4에서 정의된 우리가 linear probing을 할 때, 특히 바람직하다.) Section 11.3.3에서 묘사되는 Universal hashing은 종종 바람직한 특징을 제공한다.

Interpreting keys as natural numbers
대부분의 해쉬 함수들은 keys들이ㅡ universe가 자연수 집합N = {0, 1, 2, ... }이라고 가정한다. 따라서, 만약 keys가 자연수가 아니라면, 우리는 그것들을 자연수로 해석할 한 방법을 찾는다. 예를들어, 우리는 적절한 radix notation에서 표현되는 정수로서 문자열을 해석할 수 있다.  따라서, 우리는 그 identifier pt를 10진수의 쌍 (112, 116)으로 해석할 수 있따. 왜냐하면 ASCII 문자셋에서 p = 112이고, t = 116이기 때문이다; 그러고나서, radix-128로서 표현되는 pt는 (112 * 128) + 116 = 14452가 된다. 주어진 적용의 문맥에서, 우리는 보통 각 키를 (가능하게 큰) 자연수로 해석하는 그러한 방법들을 끌어낼 수 있다. 다음에서, 우리는 키들이 자연수라고 가정한다.

11.3.1 The division method
해쉬 함수들을 만드는 division method에서, 우리는 한 키 k를 k를 m으로 나눈 것의 나머지를 취하여 m개의 slots중에 하나로 매핑한다. 즉, 그 해쉬 함수는 h(k) = k mod m이다.

예를들어, 만약 hash table이 size m = 12이고, 그 key k = 100이라면, 그러면 h(k) = 4가 된다. 그것은 오직 한 번의 나누기 연산을 요구하기 때문에, hashing by division은 꽤 빠르다.

그 나누기 방법을 사용할 때, 우리는 보통 m의 어떤 값을 피한다. 예를들어, m는 2의 지수승이 되어선 안된다. 왜냐하면 만약 m = 2^p라면, 그러면 h(k)는 k의 p의 가장 낮은 비트이기 때문이다. 만약 우리가 모든 low-order의 p-bit patterns이 동일하게 가능성이 있다는 것을 모른다면, 우리는 키의 모든 비트들을 의존하는 해쉬함수들을 만드는게 더 낫다. Exercise 11.3-3에서 너에게 보여달라고 묻듯이, k가 radix 2^p에서 해석이되는 문자열일 때m = 2^p - 1을 고르는 것은 나쁜 선택일지도 모른다. 왜냐하면 k의 문자들을 permuting하는 것은 그것의 해쉬값을 바꾸지 않기 때문이다.

2의 한 정확한 지수 승에 너무 가깝지 않은 소수는 종종 m에 대해 좋은 선택이다. 예를들어, 우리가 한 hash table을 할당한다고 가정하자. chaining으로 해결되는 collisions과 함께, 대강 n = 2000 문자열을 보유하는, 거기에서 한 문자는 8비트이다. 우리는 성공적이지 않은 탐색에서 3개의 원소들이 평균을 검사하는 것을 꺼려하지 않는다. 그래서 우리는 사이즈 m = 701인 hash table을 할당한다. 우리는 m = 701을 선택할 수 있다. 왜냐하면 그것은 2000 / 3에 가까운 소수이지만, 2의 어떤 지수승과 가깝지 않기 때문이다. 각 키 k를 하나의 정수로 다루어서 우리의 해쉬 함수는 다음과 같이 된다.

h(k) = k mod 701

11.3.2 The multiplication method
해쉬 함수들을 만드는 multiplication method는 두 가지 단계로 작동한다. 첫 번째로, 우리는 key k를 범위 0 < A < 1의 상수 A를 곱한다. 그리고 kA의 소수부분을 추출한다. 그러고나서, 우리는 이 값에 m을 곱하고, 그 결과의 floor를 취한다. 요악해서 그 해쉬 함수는

h(k) = floor(m * (k * A mod 1))

여기에서 "kA mod 1"은 kA의 소수 부분을 의미한다. 즉, kA - floor(kA)이다.

multiplication method의 한 이점은 m의 값이 중요하지 않다는 것이다. 우리는 일반적으로 그것이 2의 지수승이 되도록 선택하는데, (어떤 정수 p에 대해 m = 2^p) 애ㅗ냐하면 우리는 그러고나서 쉽게 대부분의 컴퓨터에서 다음과 같이 함수를 구현할 수 있기 때문이다. machine에서 word size가 w bits라고 하고, k가 단일 word에 딱 맞는다고 가정하자. 우리는 A를 s / 2^w의 형태의 소수부분으로 제한하자, 여기에서 s는 0 < s <2^w 범위에 있는 정수이다. 그림 11.4를 참조하여, 우리는 처음에 k에 w-bit integer인 s = A * 2^w를 곱한다. 그 결과는 2w-bit 값인 r_1 * 2^w + r_0이다. 여기에서 r_1은 그 곱의 high-order word이고, r_0는 그 곱의 low-order word이다. 요구되는 p-bit hash value는 r_0의 p개의 상위 비트들로 이루어져있다.

비록 이 방식이 상수 A의 어떤 값과도 작동할지라도, 그것은 다른 것들것보다 어떤 값들에 더 잘 작동한다. 최적의 선택은 해쉬되는 데이터의 특징에 의존한다. Knuth[211]은

A ~ (root(5) - 1)/2 = 0.6180339887...

이 합리적으로 잘 작동할 가능성이 높다고 제안한다.

한 예시로, k = 12345, p = 14, m = 2^14 = 16384, 그리고 w =32라고 가정해보자. Knuth의 제안을 적용하여, 우리는 A가 (root(5) - 1)/2와 가까운 s/2^32의 소수가 되도록한다. A = 2654435769/2^32가 되게하기 위해서이다. 그러고나서 k * s = 327706022297664 = (76300 * 2^32) + 17612864이고, 그래서 r_1 = 76300이고 r_0 = 17612864이다. r_0의 14개의 상위 비트들은 h(k) = 67의 값을 만든다.

11.3.3 Universal hashing
만약 한 악의가 있는 상대방이 어떤 고정된 해쉬 함수에 의해 키가 해쉬되도록 선택한다면, 그러면 그 상대방은 모두 같은 slot으로 해쉬하도록 n개의 키들을 선택할 수 있다. 이것은
Ө(n)의 평균 retrieval time을 만들어 낸다. 어떤 고정된 해쉬 함수는 그러한 끔찍한 worst-case behavior에 취약하다; 그 상황을 개선시키는 유일한 효과적인 방식은 실제 저장될 키들과는 독립된 방식으로 무작위로 해쉬 함수를 선택하는 것이다. universal hashing이라고 불려지는 이 접근법은 증명적으로 평균적으로 좋은 성능을 낸다. 상대방이 어떤 키를 선택하든지.

universal hashing에서, 실행하는 초기에, 우리는 세심히 설계된 함수의 클래스로부터 무작위로 해쉬 함수를 선택한다. quick sort의 경우에서 처럼, 랜덤화는 어떠한 단일 input이 항상 worst-case behavior를 이끌어내지 않도록 보장한다. 우리가 무작위로 hash function을 고르기 때문에, 그 알고리즘은 각 실행시에 다르게 행동할 수 있다. 심지어 같은 input에 대해서도. 이것은 어떤 input에 대해서든지 average-case performance를 보장한다. 한 컴파일러의 symbol table의 예로 돌아가면, 우리는 identifiers의 프로그래머의 선택이 이제 끊임없이 좋지 않은 hashing performance를 발생시키지 않을 수 있다는 것을 안다. 나쁜 성능은 오직 그 컴파일러가 identifiers의 집합이 나쁘게 해쉬하도록 야기시키는 무작위 해쉬 함수를 고를 때 발생한다. 하지만, 이 상황이 발생할 가능성은 작고, 같은 크기의 identifiers들의 어떤 집합에 대해서도 같다.

H가 주어진 keys들의 universe U를 범위 {0,1, ..., m-1}로 매핑하는 해쉬 함수의 유한 집합이라고 하자. 만약 U에 있는 별개의 key들 k, l의 각 쌍에 대해, h(k) = h(l)인 H에 있는 h의 수가 최대 |H| / m이라면, 그러한 집합은 universal하다고 말해진다. 다시 말해서, H로부터 무작위하게 선택된 한 해쉬함수로, 별개의 키들 k와 l사이의 충돌의 가능성은 한 충돌의 1/m의 확률보다 작다. 만약 h(k)와 h(l)이 무작위하고 독립적으로 집합 {0,1,...,m-1}로부터 선택된다면.

다음의 정리는 hash functions의 universal class가 average-case behavior를 준다는 것을 보여준다. n_i가 리스트 T[i]의 길이를 표기한다는 것을 회상해라.

Theorem 11.3
해쉬 함수 h가 해쉬 함수들의 universal collection으로부터 무작위로 선택되고, collisions을 해결하기 위해 chaining을 사용하여 크기가 m인 테이블 T로 n개의 키들을 해쉬하기 위해 사용된다고 가정하자. 만약 키 k가 테이블에 없다면, 그러면 key k가 hash하는 리스트의 예상되는 길이 E[n_h(k)]는 최대 load factor a = n/m이다. 만약 key k가 테이브렝 있다면, 그러면 key k를 포함하는 리스트의 예쌍 길이 E[n_h(k)]는 최대 1 + a이다.