10 -1 해시법 (1)

1. 해시법 정의하기 

 

해시법(hashing)

- 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하는 것 

 

해시값(hash value)

- ex) 배열의 키 값(각 요솟값)을 배열의 요소 개수 13으로 나눈 나머지 

- 데이터에 접근할 때 사용 

해시 테이블 (hash table)

- 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열 

 

해시 함수(hash function)

- 키값을 가지고 해시값을 만드는 과정 

- 나머지를 구하는 연산 또는 나머지 연산을 다시 응용한 연산을 사용

 

버킷(bucket)

- 해시 테이블의 각 요소 

 

2. 충돌 살펴보기 

 

충돌(collision)

- 저장할 버킷이 중복되는 현상

 

ex) 새로운 값 18 추가 (해시값 5 -> 버킷 a[5])

but a[5]에는 다른 값 저장되어 있음

 

 

충돌에 대한 대처 

 

1) 체인법

 - 같은 해시값을 갖는 요소를 연결 리스트로 관리 

 

2) 오픈 주소법

 - 빈 버킷을 찾을 때까지 해시를 반복 

 

 

2. 체인법 살펴보기 

 

체인법(chaning)

- 같은 해시값을 갖는 데이터를 쇠사슬(chain) 모양으로 연결 리스트에서 연결하는 방법 

- 오픈 해시법

 

2.1 같은 해시값을 갖는 데이터 저장

 

- 배열의 각 버킷(해시 테이블)에 저장하는 값

 -> 그 인덱스를 해시값으로 하는 연결 리스트의 첫 번째 노드(node)에 대한 포인터 

 

2.2 버킷용 구조체 Node

 

- 개별 버킷의 자료형을 나타냄

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

 

2.3 해시 테이블을 관리하는 구조체 ChainHash

 

- 해시 테이블을 관리하기 위한 구조체 

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

 

2.4 해시값을 구하는 hash 함수 

 

- 매개변수 key로 받은 회원번호값을 해시 테이블의 크기 size로 나눈 나머지를 반환

//해시 함수 (key의 해시값을 반환)
static int hash(int key, int size) 
{
	return key % size;
}

 

2.5 노드의 값을 설정하는 SetNode 함수 

 

- 버킷의 노드에 값을 설정

//노드의 각 멤버에 값을 설정
static void SetNode(Node *n, const Member *x, const Node *next)
{
	n->data = *x; //데이터 
	n->next = (Node*) next; //다음 노드에 대한 포인터  
 }

 

2.6 해시 테이블을 초기화 하는 Initialize 함수 

 

- 공백인 해시 테이블을 만듬

- 요소의 개수가 size인 배열 table의 본체를 생성하고 

 매개변수 size로 받은 값을 멤버 size에 복사 

 

//해시 테이블 초기화 
int Initialize(ChainHash *h, int size) 
{
	if((h->table = (Node**)calloc(size, sizeof(Node *))) == NULL)
	{
		h->size = 0;
		return 0;
	}
	h->size = size;
	for(int i = 0; i <size; i++) //모든 버킷을 공백 상태로 만듬
		h->table[i] = NULL;
	return 1;
}

 

2.7 키값으로 요소를 검색하는 Search 함수 

 

- 키 값이 x->no인 요소를 검색하는 함수 

 

<검색 알고리즘>

 

1) 해시 함수가 키값을 해시값으로 변환

 

2)  해시값을 인덱스로 하는 버킷 선택

 

3) 선택한 버킷의 연결리스트를 처음부터 순서대로 검사 

 키값과 같은 값을 찾으면 검색성공

 

ex) 33을 검색 

- 33의 해시값은 7 

- table[7]이 가리키는 연결 리스트를 하나씩 끌어당기며 찾음 

 

ex) 26을 검색 

- 26의 해시값은 0

- table[0]이 NULL이므로 검색 실패 

//검색
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; //검색 실패  
 }

 

2.8 요소를 추가하는 Add 함수 

 

- 포인터 x가 가리키는 데이터를 추가하는 함수 

 

<추가 알고리즘>

 

1) 해시 함수가 키값을 해시값으로 변환

 

2) 해시값을 인덱스로 하는 버킷 선택 

 

3) 버킷에 저장된 포인터가 가리키는 연결 리스트를 처음부터 순서대로 검색

 키값과 같은 값을 찾으면 키 값이 이미 등록된 상태이므로 추가 실패 

 끝까지 스캔하여 찾지 못하면 리스트의 맨 앞 위치에 노드 삽입

 

 

ex) 13 추가 

 - 13의 해시값은 0

 - table[0]은 NULL 

 - 그 노드에 대한 포인터를 table[0]에 대입

 

ex) 46 추가 

 - 46의 해시값은 7

 - table[7]의 버킷에는 20과 33을 연결하는 리스트의 포인터가 저장 

 - 리스트의 맨앞에 46 추가 

 - 추가할 값 46을 저장하는 노드를 새로 만들고  그 노드에 대한 포인터를 table[7]에 대입

 

// 데이터 추가 
 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 =(Node*) calloc(1,sizeof(Node))) == NULL)
		return 2;
	SetNode(temp,x,h->table[key]); //추가하는 노드에 값을 설정
	//현재 해시값을 인덱스로 하는 연결리스트의 head로 지정해서 연결리스트의 맨 앞에 추가  
	h->table[key] = temp; //추가 성공 table[key] => 연결리스트의 head 역할  
	return 0; 
 }

 

2.9 요소를 삭제하는 Remove 함수 

 

- 키 값이 x->no인 요소를 삭제하는 함수 

 

<삭제 알고리즘>

 

1) 해시 함수가 키값을 해시값으로 변환

 

2) 해시값을 인덱스로 하는 버킷을 선택

 

3) 선택한 버킷의 포인터가 가리키는 연결 리스트를 처음부터 순서대로 검색

 키값과 같은 값을 찾으면 그 노드를 리스트에서 삭제 

 

ex) 69를 삭제 

- 69의 해시값은 4

- table[4]의 버킷에 저장된 포인터의 리스트를 연결 검색 

- 69를 저장한 노드의 다음 노드는 17을 저장한 노드

- 17을 저장한 노드에 대한 포인터를 table[4]의 버킷에 대입 

- 69를 저장하는 노드의 메모리 해제 

 

//데이터 삭제 
 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; //삭제 실패 (존재하지 않음) 
 }

 

2.10 해시 테이블의 내용을 출력하는 Dump 함수 

 

- 해시 테이블의 내용을 통째로 출력

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

 

2.11 모든 데이터를 삭제하는 Clear 함수 

 

- 해시 테이블에 등록된 모든 데이터를 삭제 

 

<데이터 삭제 알고리즘>

 

1) 배열 표의 요소가 NULL이 아니면 그 해시값을 갖는 데이터가 연결 리스트로 존재하므로, 

연결 리스트를 맨 앞부터 순서대로 검사하면서 리스트의 모든 노드에 대한 메모리 해제 

 

2) 검사 중인 배열 요소에 NULL을 대입

 

3) 배열에 대한 모든 검사가 끝나면 모든 버킷이 "공백"상태가 됨

 

//모든 데이터 삭제 
 void Clear(ChainHash *h) 
 {
 	for(int 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;
	 }
 }

 

2.12 해시 테이블을 종료하는 Terminate 함수 

 

- 해시 테이블의 사용을 마칠때 사용

//해시 테이블 종료 
 void Terminate(ChainHash *h) 
 {
 	Clear(h); //모든 데이터 삭제 
	free(h->table); //해시 테이블 배열의 메모리 해제 
	h->size = 0; //해시 테이블 크기를 0으로 초기화  
 }