Hash

Hash

• Hash table은 Dynamic set을 구현하는 효과적인 방법중에 하나이다.
  • 적절한 가정하에 평균적으로 탐색, 삽입, 삭제의 시간복잡도가 O(1)
  • 보통 최악의 경우에는 시간복잡도가 Θ(n)
    • 빅세타는 빅오와 빅오메가의 공통부분이다. 최소와 최악의 중간인 평균적인 복잡도를 의미한다.

Hash function

• Hash function “h”를 사용하여 Key “k”를 이용하여 데이터를 T[h(k)]에 저장한다.
  • h:v → {0, 1, … …, m-1} 여기서 m은 table의 크기, v는 모든 가능한 Key들의 집합
  • Key “k”가 h(k)로 hashing 되었다고 말한다.

Example)

• Hash function
  • 모든 Key를 자연수라고 가정 → 어떠한 Data이던 자연수로 해석 가능
  • 예) 문자열
    • ASCII Code : C=67, L=76, R=82, S=83
    • 문자열 “CLRS” → 67x128³ + 76x128² + 82x128 + 83x1 = 141764947 (128진수로 생각하여 표현)
  • Hash function의 간단한 예)
    • h(k) = k%m 즉 Key를 하나의 자연수로 해석한 뒤, Table 크기 m으로 나눈 나머지
    • 항상 0 ~ m-1 사이의 값을 갖는다.

하지만 Key값에 중복이 발생한다면?

Collision

• Collision
  • 두개 이상의 Key가 동일한 위치로 hashing 되는 경우 (즉 서로 다른 두 Key k1, k2에 대해서 h(k1) = h(k2)인 경우)
  • 일반적으로 |v| » m 이므로 항상 발생 가능 즉 단사함수가 아니다

  • 만약

    k

    > m이라면, 당연히 발생 가능 여기서 k는 실제로 저장된 Key들의 집합

  • 충돌이 발생할 경우 대처 방법이 필요 → 대표적인 해결 방법 : Chaining, Addressing
• Chaining에 의한 collision 해결
  • Idea : 동일한 index로 hashing된 모든 key들을 하나의 linked-list로 저장한다.
  • Insert
    • Key k를 리스트 T[h(k)]의 맨 앞에 삽입 : 시간복잡도 O(1)
    • 중복된 Key가 올 수 있고,
    • 중복 저장이 허용되지 않으면 삽입 시 List를 검색해야 하므로, 시간복잡도는 리스트의 길이에 비례
  • Search
    • List T[h(k)]에서 순차검색 시간복잡도는 키가 저장 된 리스트의 길이에 비례
  • Delete
    • List T[h(k)]로 부터 Key를 검색 후 삭제, 일단 Key를 찾으면 O(1)에 삭제 가능
  • 최악의 경우는 모든 Key가 하나의 Slot으로 hashing 되는 경우이다.
    • 길이가 n인 하나의 연결리스트가 만들어지고, 이 때 탐색시간은 Θ(n) + hashing function의 계산시간
  • 평균시간 복잡도는 Key들이 여러 Slot에 얼마나 잘 배가 분되는지에 따라 결정된다.

Example)

• SUHA (Simple uniform hashing assumption)
  • 각각의 Key가 모든 Slot에 균등확률로(Equally likely) 독립적으로(Independently) hashing 된다는 가정
    • 성능 분석을 위해 주로 하는 가정
    • Hashing 함수는 Deterministic 하므로 현실에서는 불가능
  • Load factor α = n/m
    • n Table에 저장된 Key의 개수
    • m Hash Table의 크기, 즉 연결리스트의 개수
    • 각 Slot에 저장된 Key의 평균 개수
  • 연결리스트 T[j]의 길이를 n_j라고 하면 E[n_j] = α
  • 만약 n = O(m)이면 평균 검색 시간은 O(1)이 된다.
• Open addressing에 의한 Collision 해결
  • Idea : 모든 Key를 Hash Table에 저장, Table에 각 Slot에는 1개의 Key만 저장
  • 충돌 해결 방법   * Linear probing
    • Quadratic probing
    • Double probing
    • Linear probing
    • h(k), h(k) + 1, h(k) + 2 … 순으로 검사하여 처음으로 빈 Slot에 저장
      • Table의 끝에 도달하면 다시 처음으로 Circular하게 돌아감
    • Linear probing의 단점
      • Primary cluster(키에 의해서 채워진 연속된 Slot)이 생성된다.
      • 이러한 Cluster가 생성되면 이 Cluster는 점점 더 커지는 경향이 있다.
  • Quadratic probing
    • 충돌 발생 시 h(k), h(k) + 1², h(k) + 2², h(k) + 3² … 순서로 시도
  • Double Hashing
    • 서로 다른 두 Hash function(h₁, h₂)을 이용하여 h(k, j) = (h₁(k) + ixh₂(k)) mod m
    
  • Open addressing에서의 Key 삭제
    • 단순하게 Key를 삭제한 경우 문제 발생
    • 예를 들어서 A₂, B₂, C₂로 Insert되어 Linear probing 되었을 때 B₂를 삭제하면?

Hash function (Cont’d)

• 현실에서는 Key들이 random 하지 않음.
• 만약 Key들의 통계적 분포에 대해 알고 있다면 이를 이용해서 Hash function을 만들 수 있지만 현실적으로 불가능
• Key들이 어떤 특정한(가시적인) Pattern을 갖더라도 Hash function 값이불규칙이 되도록 하는게 바람직
  • Hash function의 값이 Key의 특정부분에 의해서만 결정되지 않아야 한다
• Division 기법
  • h(k) = k mod m : 값을 0 ~ m-1 사이의 값으로 바꿈(모든 hash f의 마지막 단계)
  • example) m = 20 and k = 91, h(k) = 11
  • 장점 : 한번의 mod 연산으로 계산하므로 속도가 빠름.
  • 단점 : 어떠한 m값에 대해서는 hash function의 key값이 특정 부분에 의해 결정되는 경우가 존재한다
    • example) m = 2^p이면 Key값이 하위 P비트에 의해 결정 → 하위 P비트가 hash function의 값이 되어 버린다.
• Multiplication 기법
  • 0 ~ 1 사이의 상수를 선택 (A) : 0 < A < 1
  • KxA 의 소수 부분만 남기고 m을 곱한 뒤 소수점 아래를 버린다.
    • → h(x) = ( KxA mod 1 ) x m : m은 꼭 소수일 필요는 없다 보통 2^P로 정한다
  • c++ stdlib unordered_set class → Hash library
  • example) hash function example

public final class string {
    private final char[] s;
    public int hashcode(){
        int hash;
        for(int i = 0; i < length(s); i++)
            hash = s[i] + (31 * hash);
        return hash;
    }
}

Hash 구현

• Datastructure

typedef struct HASH {
    char key[MAX_KEY + 1]; // Hash Key를 저장
    char data[MAX_DATA + 1]; // Key에 매치되는 Data를 저장
} HASH_t

HASH_t tbl[MAX_TABLE]; // HASH_t의 배열 → Collision 발생 시 open addressing로 해결하기 위해

• Hash function

unsigned long hash_function (const char *str) {
    unsigned long hash = PRIME_NUMBER; // 기본값으로 보통 소수를 사용한다.
    int c;
    
    while(c = *str++)
        //ASCII code 비트수만큼을 Shift하여 이전 문자를 Key 만드는데 반영한다.
        hash = (((hash << 5) + hash ) + c) % MAX_TABLE;

    return hash % MAX_TABLE;
}

• Insert

int insert(const char *key, char *data) {
    unsigned long h = hash_function(key);// Key에 대한 hash값을 구한다.

    while(tbl[h].key[0] is not null) {
        if(strcmp(tbl[h].key, key) == 0)
            return = 0; // 중복된 Key가 들어 왔으므로 return

        //Open Addressing Linear Probing
        h = (h + 1) % MAX_TABLE;
    }
    
    strcpy(tbl[h].key, key); // key  복사
    strcpy(tbl[h].data, data); // data  복사
    
    return 1;
}

• Search

int Search(const char *key, char *data) {
    unsigned long h = hash_function(key);// Key에 대한 hash값을 구한다.
    int cnt = MAX_TABLE;

    while(tbl[h].key[0] is not 0 and cnt --) {
        if(strcmp(tbl[h].key, key) == 0) {
            strcpy(tbl[h].data, data);
            return = 1; // key를  찾아 Data를 복사했으므로
        }

        //Open Addressing Linear Probing
        h = (h + 1) % MAX_TABLE;
    }

    // MAX_TABLE 수만큼 Linear하게 Probing 했음에도 Key를 못찾았기 때문에
    return 0;
}

• Delete
  • Delete를 위해선  Table의 Data structure와 함수들에 변화가 있어야 한다.

typedef struct HASH {
    char key[MAX_KEY + 1]; // Hash Key를 저장
    char data[MAX_DATA + 1]; // Key에 매치되는 Data를 저장
    bool valid; // Data 삭제 여부를저장하기 위해 유효성을 저장
} HASH_t

HASH_t tbl[MAX_TABLE]; // HASH_t의 배열 → Collision 발생 시 open addressing로 해결하기 위해

int insert(const char *key, char *data) {
    unsigned long h = hash_function(key);// Key에 대한 hash값을 구한다.
    int cnt = MAX_TABLE;

    //Data가 삭제된 Data인지 확인 추가
    while(tbl[h].key[0] is not null and tbl[h].valid is true and cnt--){
        if(strcmp(tbl[h].key, key) == 0)
            return = 0; // 중복된 Key가 들어 왔으므로 return

        //Open Addressing Linear Probing
        h = (h + 1) % MAX_TABLE;
    }
    
    strcpy(tbl[h].key, key); // key  복사
    strcpy(tbl[h].data, data); // data  복사
    tbl[h].valid = true; // Data valid true

    return 1;
}

int Search(const char *key, char *data) {
    unsigned long h = hash_function(key);// Key에 대한 hash값을 구한다.
    int cnt = MAX_TABLE;

    while(tbl[h].key[0] is not 0 and cnt --) {
        if(strcmp(tbl[h].key, key) == 0 && tbl[h].valid == true) {
            strcpy(tbl[h].data, data);
            return = h; // Key를 찾은 table index값을 리턴
        }

        //Open Addressing Linear Probing
        h = (h + 1) % MAX_TABLE;
    }
    
    // MAX_TABLE 수만큼 Linear하게 Probing 했음에도 Key를 못찾았기 때문에
    return -1;
}

int del(const char* key) {
    usigned long h = hash(key);
    char data[MAX_DATA+1];

    int index = search(key, data);
    
    if(index != -1) {
        tbl[index].valid = false;
        return 1;
    }
    else {
        return 0;
    }
}

Problem

• ACMICPC:
• LEETCODE: Hash