열혈 자료구조 - 13.2 충돌 문제의 해결책

선형 조사법

- 해쉬 함수를 통해 슬롯에 저장할 때 이미 저장되어 있으면 다음 칸에 저장하는 방법

- 충돌이 발생하면 다음칸을 탐색하여 비어있다면 저장

- 단순하지만 충돌 횟수가 증가함에 따라 클러스터 현상이 발생한다는 단점이 있음

    -> 클러스터 현상 : 특정 영역에 데이터가 몰리는 현상

 

이차 조사법

- 선형 조사법을 약간 개선한 방법

- 선형 조사법은 한칸 씩 이동하면서 찾았지만 이차 조사법은 제곱의 수만큼 이동하면서 찾음

- 이차 조사법과는 별개로 만약 슬롯에 9를 삭제했을 때 슬롯의 상태를 DELETED로 바꿔줘야 함

    -> 만약 value 2를 찾기 위해 해쉬 함수를 통해 슬롯 번호를 찾으면 2번이라고 알림

    -> 2번에는 9가 저장되어 있다가 삭제 되었고 실제 2는 그 옆인 3번에 저장되어 있음

    -> 2번 자리에는 value 2가 아니라 다른 값이 저장되어 있다가 삭제되었다는 것을 알려주기 위해 DELETED 상태를 남겨야 함

    -> DELETED 상태를 만났다면 조사법에 따라 이동하면서 검사함

    -> 데이터를 넣고 삭제하면 모든 슬롯이 DELETED 상태가 된다는 문제가 있음

 

이중 해쉬

- 해쉬 함수를 2개를 만들어서 1차 해쉬는 해쉬(위치)를 찾을때 사용하고 충돌이 발생했을 때 사용

- 2차 해쉬 함수를 사용하면 건너뛰는 값의 크기가 다 다름

- 2차 해쉬에 1을 넣는 이유 : 2차 해쉬가 '0'인것을 방지하기 위해

- c는 배열의 크기(10)보다 작은 소수 중 하나를 설정

    -> 소수를 넣는 이유는 클러스터 현상을 낮춘다는 통계적 근거에 바탕

 

체이닝 방법

- 한 해쉬 값에 다수의 대이터를 저장할 수 있도록 2차원의 형태로 선언하는 모델

- 충돌이 발생하면 다른 해쉬에 저장하는 다른 방법과는 다르게 충돌이 발생해도 그 해쉬에 저장이 됨

- 연결 리스트 기반의 체이닝 방법 구현

void TBLInit(Table * pt, HashFunc * f)
{
	int i;

        for(i=0; i<MAX_TBL; i++) {
		ListInit(&(pt->tbl[i]));        // 해쉬 한칸씩 리스트로 초기화 시킴
        }

	pt->hf = f;
}

void TBLInsert(Table * pt, Key k, Value v)
{
	int hv = pt->hf(k);     // 키에 대한 해쉬를 얻음
	Slot ns = {k, v};
	
	if(TBLSearch(pt, k) != NULL) {
		printf("키 중복 오류 발생 \n");
		return;
	} // 키가 중복되었다면
	else {
		LInsert(&(pt->tbl[hv]), ns);        // 연결 리스트에 추가
	}
}

Value TBLDelete(Table * pt, Key k)
{
	int hv = pt->hf(k);     // 키에 대한 해쉬를 얻음
	Slot cSlot;

	if(LFirst(&(pt->tbl[hv]), &cSlot)) {
		if(cSlot.key == k) {
			LRemove(&(pt->tbl[hv]));
			return cSlot.val;
		}
		else {
			while(LNext(&(pt->tbl[hv]), &cSlot)) {
				if(cSlot.key == k) {
					LRemove(&(pt->tbl[hv]));
					return cSlot.val;
				}
			}
		}
	} // 연결 리스트 조회 : First 후 Next로 조회하면서 해당 키가 맞다면 노드 삭제

	return NULL;
}

Value TBLSearch(Table * pt, Key k)
{
	int hv = pt->hf(k);     // 키에 대한 해쉬를 얻음
	Slot cSlot;

	if(LFirst(&(pt->tbl[hv]), &cSlot)) {
		if(cSlot.key == k) {
			return cSlot.val;
		}
		else {
			while(LNext(&(pt->tbl[hv]), &cSlot)) {
				if(cSlot.key == k) {
					return cSlot.val;
                                }
			}
		}
	} // 연결 리스트 조회 : First 후 Next로 조회하면서 해당 키가 맞다면 노드값 반환

	return NULL;
}