해시법

- 정렬된 배열에 새로운 값을 추가하려면?

        1. 삽입할 위치를 이진검색법으로 조사

        2. 삽입할 위치 이후의 모든 요소를 뒤로 하나씩 이동

        3. 새로운 값 대입

        => 복잡도: O(n)

 

• 해시법: 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것
  • 해시 함수(hash function): 키 값을 가지고 해시 값을 만드는 과정
  • 해시 값(hash value): 배열의 키 값을 배열의 요소 개수로 나눈 나머지 등 해시 함수를 거친 값
  • 해시 테이블(hash table): 해시 값을 정리한 표
  • 버킷(bucket): 해시 테이블의 각 요소

 

• 충돌(collision): 저장할 버킷이 중복되는 현상
  • 해시 함수는 가능하면 해시 값이 중복되지 않도록 고르게 분포된 값을 만들어야 함
  • 충돌에 대한 대처: 
    1. 체인법: 같은 해시 값을 갖는 요소를 연결 리스트로 관리
    2. 오픈 주소법: 빈 버킷을 찾을 때까지 해시를 반복(재해시할 때의 해시 함수는 자유롭게 결정 가능)
       
       • 검색: 버킷 상태가 '비어있음'이면 검색 실패, '삭제됨'이면 재해시 후 다시 검색
       • 삭제: 버킷의 데이터를 삭제 후 상태를 '삭제됨'으로 저장

---

• 체인법(Chaining) (= 오픈 해시법(Open hashing))

해시 테이블 각 버킷에 저장하는 값은 해당 인덱스를 해시 값으로 하는 연결 리스트의 첫 번째 노드에 대한 포인터

 

/* 버킷을 나타내는 노드 */
typedef struct __node {
    Member data;
    struct __node *next; //다음 노드에 대한 포인터
} Node;

/* 해시 테이블 */
typedef struct {
    int size; //해시 테이블 크기
    Node **table; //해시 테이블의 첫 번째 요소에 대한 포인터
} ChainHash;

 

• hash 함수: 해시 값을 구함

static int hash(int key, int size){
    return key % size;
}

 

• SetNode 함수: 노드 값 설정

static void SetNode(Node *n, Member x, const Node *next){
    n->data = x;
    n->next = next;
}

 

• Initialize 함수: 해시 테이블 초기화

int Initialize(ChainHash *h, int size){
    int i;
    if((h->table = calloc(size, sizeof(Node*))) == NULL){ //메모리 영역 확보 실패
        h->size = 0;
        return 0;
    }
    h->size = size;
    for(i=0; i<size; i++)
    	h->table[i] = NULL;
    return 1;
}

 

• Search 함수: 키 값으로 요소를 검색

Node *Search(const ChainHash *h, const Member *x){
	int key = hash(x->no, h->size); //검색하는 데이터의 해시 값
    Node *p = h->table[key];
    
    while(p != NULL){
        if(p->data.no == x->no) return p;
        p = p->next;
    }
    return NULL;
}

 

• Add 함수: 요소 추가

int Add(ChainHash *h, const Member *x){
    int key = hash(x->no, h->size);
    Node *p = h->table[key];
    Node *temp;
    while(p != NULL){
    	if(p->data.no == x->no) return 1; //이미 등록된 키
        p = p->next;
    }
    if((temp = calloc(1, sizeof(Node)) == NULL) 
    	return 2; //메모리 할당 실패
    SetNode(temp, x, h->table[key]); //리스트의 맨 앞에 삽입
    h->table[key] = temp;
    return 0;
}

 

• Remove 함수: 요소 삭제

int Remove(ChainHash *h, const Member *x){
    int key = hash(x->no, h->size);
    Node *p = h->table[key]; //현재 선택한 노드(리스트의 맨 처음 노드)
    Node **pp = &h->table[key]; //현재 선택한 노드에 대한 포인터
    
    while(p != NULL){
    	if(p->data.no == x.no) {
        	*pp = p->next;
            free(p);
            return 0;
        }
        pp = &p->next;
        p = p->next;
    }
    return 1;
}

 

• Dump 함수: 해시 테이블의 내용을 출력

void Dump(ChainHash *h){
    int i;
    for(i = 0; i < h->size; i++) {
    	Node *p = h->table[i];
        printf("%02d  ", i); //해시 값
        while(p != NULL){
        	printf("-> %d ", p->data.no);
            p = p->next;
        }
        putchar('\n');
    }
}

 

• Clear 함수: 모든 데이터 삭제

void Clear(ChainHash *h){
    int i;
    for(i=0; i < h->size; i++){
    	Node *p = h->table[i];
        while(p != NULL){
        	Node *next = p->next;
            free(p); //선택한 노드 메모리 해제
            p = next;
        }
        h->table[i] = NULL;
    }
}

 

• Terminate 함수: 해시 테이블 종료

void Terminate(ChainHash *h){
    Clear(h);
    free(h->table);
    h->size = 0;
}