10-1 장 해시법 (2)

1. 오픈 주소법 이해하기 

 

오픈 주소법(open addresing)

 

- 충돌이 발생했을 때 재해시(rehashing)를 수행하여 비어 있는 버킷을 찾아내는 방법

- 닫힌 해시법(closed hashing)

- 연결 탐사법(linear probing)

 : 빈 버킷을 만날 때 까지 재해시 

 

//요소의 상태 
typedef enum {
    Occupied, Empty, Deleted
}Status;

//요소 
typedef struct {
    Member data; //데이터
    Status stat; // 요소의 상태 
}Bucket;

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

 

1.1 요소 삽입

 

ex) 새로운 값 18을 삽입하고자 할때 충돌 발생

 

- 재해시 함수 

 -> 키값에 1을 더한 값을 13으로 나눔 

//재해시 함수 
static int rehash(int key, int size) 
{
	return (key+1) % size;
}

 

- 빈 버킷을 만날 때까지 재해시(rehashing)을 여러 번 반복

//데이터 추가 
int Add(CloseHahs *h, const Member *x)
{
	int key = hash(x->no, h->size); // 추가할 데이터의 해시값
	Bucket *p = &h-> table[key] ; // 현재 선택한 노드 
	if(Search(h,x)) //이 키는 이미 등록됨
		return 1; 
	for(int i =0 ; i<h->size; i++) {
		if(p->stat == Empty || p->stat == Deleted) {
			SetBucket(p,x,Occupied);
			return 0;
		}
		key = rehash(key, h->size);
		p = &h -> table[key];   
    }
    return 2; //해시 테이블이 가득참 
}

 

 

1.2 요소 삭제 

 

ex) 인덱스가 5인 값을 삭제하는 과정 

 

- 각 버킷에 대해 

1) 데이터 저장 속성값

2) 비어 있음 속성값(-)

3) 삭제 마침 속성값 (★)

 

//데이터 삭제 
int Remove (ClosedHash *h, const Member *x) 
{
	Bucket *p = Search(h,x);
	if(p == NULL)
		return 1; //이 키의 값은 존재하지 않음  
	p->stat = Deleted; 
	return 0;
}

 

 

1.3 요소 검색 

 

ex) 18을 검색 

 

- 원하는 값을 찾을 때까지 재해시 반복

 

//검색
Bucket *Search(const ClosedHash *h, const Member *x) 
{
	int key = hahs(x->no, h->size); //검색할 데이터의 해시값
	Bucket *p = &h->table[key]; //현재 선택한 노드 
	for(int i = 0; p->stat != Empty && i <h->size; i++)  {
		if(p->stat == Occupied && p->data.no == x->no)
			return p;
		key = rehash(key, h->size); //재해시
	 	p = &h->table[key]; 
	}
	return NULL;
}