• A[“kreplach”] = “tasty stuffed dough”

• 정수 n이 insert되면 n번 인덱스 값을 1로 수정
• 정수 n이 delete되면 n번 인덱스 값을 0으로 수정
• 정수 n search시 n번 인덱스가 1인지를 리턴

• 낭비되는 메모리가 너무 크다. 예를 들어, 가능한 입력값이 1000개지만 실제로 저장되는 원소 개수는 10개 정도라면, 99%의 메모리가 낭비된다.
• 키값으로 0이상의 정수만 사용 가능하다.

해시 함수 : 키값 집합 → 배열 인덱스

1. 0이상의 정수를 리턴해야 한다.
2. O(1)시간에 빠르게 계산되어야 한다.
3. 낭비하는 공간이 없어야 한다.
• 즉, 해시 함수가 리턴할 수 있는 최대 정수가 n이라면, 0<=k<=n 인 임의의 k에 대해, 해시 함수가 k를 리턴하도록 하는 입력 가능한 키값이 존재해야 한다.
• 예를 들어, 0부터 10까지의 정수를 리턴하는 해시 함수인데 7을 리턴하도록 하는 키값이 없다면, 해당 공간이 낭비되므로 좋은 해시 함수가 아니다.
4. 충돌이 최소로 발생해야 한다.
• 가능한 입력 키값의 개수가 실제로 저장되는 원소 개수에 비해 훨씬 클 수 있다. 해시 함수가 이러한 키값들마다 인덱스를 하나씩 대응시킨다면, 메모리 공간이 너무 많이 필요할 것이다.
• 메모리 낭비를 줄이기 위해, 해시 함수의 치역(인덱스)은 정의역(키값)보다 작다. 이로 인해 서로 다른 키값이 해시 함수에 의해 같은 인덱스로 대응되는 경우가 발생한다. 이것이 충돌이다.
• 이러한 충돌을 해결하고 충돌 키값을 저장하는 방법이 있지만, 이러한 해결 뒤에는 해시 테이블의 수행 속도 저하가 뒤따른다. 따라서 충돌을 최대한 피해야 한다.
• 충돌을 줄이기 위해서는, 키를 인덱스 값들에 최대한 고르게 대응시켜야 한다. 특정 인덱스에 키값이 몰리면 안 된다.

• Hash(x) = x % TableSize

문자열의 해시 함수

• 크기가 3인 문자열을 저장한다면, 아스키 코드 기준 128³ 종류의 입력이 가능하다. 이러한 입력에 대해 인덱스가 0~10000인 해시 테이블을 준비했다고 하자. 그런데 문자열을 다 더했을 때 최댓값은 128 * 3 = 384  밖에 안 된다. 그 뒤의 공간 385~10000은 쓰이지 않는다.
• 키값에 특정 문자가 자주 나올 수 있다. 예를 들어 a, b, c가 자주 나온다고 하자. 이때, 위 해시 함수는 “abc”, “bca”, “cab” 에 모두 같은 인덱스를 대응시켜 버린다.

• Hash(“abc”) = (‘a’*128² + ‘b’*128¹ + ‘c’) % TableSize

• Hash(“abc”) = (‘a’*32² + ‘b’*32¹ + ‘c’) % TableSize

• Hash(x) = x % 17

1. Separate Chaining
2. Closed Hashing

• Quadratic Probing
• 기본 closed hashing에서는 인덱스 i에서 k번째로 충돌한 키값을  i+k 인덱스에 저장했다. Quadratic Probing에서는 i + k²에 저장한다.
• 예를 들어, Hash(a) = Hash(b) = Hash(c) = Hash(d) = Hash(e) = 10 이라 하자.
• a, b, c, d, e를 순서대로 insert 한다면, a는 10, b는 11, c는 14, d는 19, e는 26에 저장된다.
• Double Hashing
• 또다른 해시 함수 Hash2(x)를 준비한다.
• 충돌이 발생하면, Hash2 값만큼 더해준 인덱스에 값을 저장한다.
• 해당 자리도 차 있다면, 빈 자리가 나올 때까지 Hash2를 더한다.