1. 해시 테이블 정의

해시 테이블 (Hash Table):

  • 키와 값을 매핑하는 연관 배열 추상 데이터 타입.
  • 해시 함수를 사용하여 버킷 또는 슬롯 배열의 인덱스를 계산하고, 해당 위치에 값을 저장.

작업:

  • 검색 (Search): 키를 사용하여 값 검색.
  • 삭제 (Delete): 키를 사용하여 값 삭제.
  • 삽입 (Insert): 키와 값을 삽입.

시간 복잡도:

  • 최악의 경우: O(size)
  • 기대 시간: O(1)

2. 이상적인 해싱 (Ideal Hashing)

구조:

  • 1차원 배열(table[0]) 사용.
  • 각 위치는 버킷을 나타내며, 일반적으로 하나의 딕셔너리 쌍을 저장.
  • 해시 함수 f를 사용하여 각 키 k를 인덱스 범위 [0, b-1]로 변환.
  • 딕셔너리 쌍 (key, element)는 키의 홈 버킷에 저장.

예제:

  • 키-값 쌍: (22,a), (33,c), (3,d), (73,e), (85,f)
  • 해시 테이블 크기: 8
  • 해시 함수: key/11
[0] [1] [2] [3] [4] [5] [6] [7]
    (85,f)(22,a) (33,c)(3,d) (73,e)


3. 해시 테이블 문제

충돌 (Collision):

  • 동일한 홈 버킷에 다른 키가 저장될 때 발생.

오버플로우 (Overflow):

  • 홈 버킷이 가득 차서 새로운 쌍을 저장할 수 없을 때 발생.

해결 방법:

  • 오버플로우 처리 방법 필요.

4. 해시 함수

구성:

  • 키를 정수로 변환하는 함수 hash().
  • 정수를 홈 버킷으로 매핑하는 함수 f(k).

문자열을 정수로 변환:

  • 각 문자는 1바이트, 정수는 4바이트.
  • 2문자 문자열 key[0:1]을 고유한 4바이트 정수로 변환.
int stringToInt(char *key) {
    int number = 0;
    while (*key) {
        number += *key++;
        if (*key)
            number += ((int)*key++) << 8;
    }
    return number;
}


홈 버킷으로 매핑:

  • 가장 일반적인 방법은 나눗셈.
  • homeBucket = hash(theKey) % divisor;

5. 균등 해시 함수

정의:

  • 키 공간의 모든 키를 버킷에 균등하게 매핑.
  • 균등 해시 함수는 오버플로우 가능성을 최소화.

나눗셈을 이용한 해싱:

  • 키 공간 = 모든 정수.
  • 모든 정수가 균등하게 버킷에 분포.

나눗셈 선택:

  • b가 짝수인 경우, 키의 홀수/짝수에 따라 편향 발생 가능.
  • b가 홀수인 경우, 더 균등한 분포 가능.
  • 이상적으로는 소수를 선택.

6. 오버플로우 처리

방법:

  • 선형 조사법 (Linear Probing)
  • 제곱 조사법 (Quadratic Probing)
  • 랜덤 조사법 (Random Probing)
  • 체이닝 (Chaining)

선형 조사법 예제:

void insert(int table[], int size, int key) {
    int index = key % size;
    while (table[index] != -1) {
        index = (index + 1) % size;
    }
    table[index] = key;
}

삭제 예제:

void delete(int table[], int size, int key) {
    int index = key % size;
    while (table[index] != key) {
        index = (index + 1) % size;
        if (table[index] == -1) return;
    }
    table[index] = -1;
}


7. 선형 조사법 성능

성능:

  • 최악의 경우: O(n)
  • 기대 성능: α(로딩 밀도)에 따라 달라짐.

로딩 밀도 (α):

  • α = (저장된 쌍의 수) / 버킷 수

기대 성능:

  • 성공적 검색: Sn ~ ½ (1 + 1/(1 – α))
  • 실패한 검색: Un ~ ½ (1 + 1/(1 – α)^2)

8. 해시 테이블 설계

설계 기준:

  • 최대 허용 로딩 밀도 설정.
  • 동적 크기 조정 필요 시 구현.
  • 고정 테이블 크기의 경우, 최대 쌍의 수에 따라 크기 설정.

동적 크기 조정:

  • 로딩 밀도가 임계값을 초과하면 테이블 크기를 두 배로 늘리고 재해싱.

9. 체이닝 (Chaining)

구조:

  • 각 버킷이 해당 홈 버킷에 속하는 모든 쌍의 리스트를 유지.
  • 리스트는 정렬될 수도 있고, 정렬되지 않을 수도 있음.

예제:

[0] [4] [8] [12] [16]
 0   6  34  12  28
     23 29  11  30
        33      45

기대 성능:

  • α >= 0
  • 성공적 검색: Sn ~ 1 + α/2
  • 실패한 검색: Un ~ α