[자료구조] 해쉬(Hash)와 테이블(Table)

고유값 key(made by 해쉬함수)을 이용해서 배열에 저장함 ≒ #include <map>

 

[테이블] 

 

<특징>

키와 값이 하나의 쌍을 이루어 저장되는 데이터의 유형

O(1)의 시간 복잡도

 

<가벼운 예시>

 

#include <stdio.h>

typedef struct _empInfo
{
	int empNum;  //이것이 고유번호가 될것이여
	int age;     //실제 저장할 대상
}EmpInfo;

int main(void)
{
	EmpInfo empInfoArr[1000];
	EmpInfo ei;
	int eNum;

	printf("사번과 나이 입력: ");
	scanf("%d %d", &(ei.empNum), &(ei.age));
	empInfoArr[ei.empNum] = ei;  

	printf("확인하고픈 직원의 사번 입력: ");
	scanf("%d", &eNum);

	ei = empInfoArr[eNum];   
	printf("사번 %d, 나이 %d \n", ei.empNum, ei.age);
	return 0;
}

 

 

 

---

 

 

[해쉬 함수] 

 

<기능>

넓은 범위의 고유값을 그대로 사용하면 배열이 너무 커지니까 고유값의 범위를 줄인다(by 함수)

ex) 여덟 자리의 수로 이뤄진 직원의 고유번호를 두 자리의 수로 변경한다

 

 

 

<주의점>

 

값들의 충돌이 일어날수 있으므로 해쉬함수를 값의 충돌이 일어나지 않게 잘 정의해야함

ex) 17 % 10 = 7  ,  27 % 10 = 7  -> 충돌!

 

---

[해쉬-테이블] 

 

 

▶ 구조

Table

1. Solt tbl[100] -> 1) int key, 2) Person * val(int ssn, char name, char addr), 3) enum slot_status(EMPTY, DELETED, INUSE)
2. Hashfunc *hf (해쉬함수)

slot_status 

• EMPTY :  이 슬롯엔 데이터가 저장된 적이 없다
• DELETED : 이 슬롯엔 데이터가 저장된 적이 있으나 현재는 비워진 상태이다
• INUSE : 이 슬롯에는 현재 유효한 데이터가 저장되어 있다

DELETED 의 상태를 두어야하는 이유 : 충돌이 발생하였을 때 옆으로 데이터를 옮기게 되는데 이때 지운 데이터의 상태를 EMPTY로 두게 되면 지운 데이터와 충돌되었던 데이터를 찾다가 옆에 내가 찾는 데이터가 있는지 모르고 EMPTY만 보고 데이터가 없다고 판단하게 된다

 

▶ 테이블의 핵심주제 = 충돌 문제

해결책 : 충돌이 발생하면, 충돌이 발생한 그 자리를 대신해서 빈 자리를 찾아야 한다

 

 

[열린 어드레싱 방법] -> 충돌이 발생하면 다른 자리에 대신 저장한다

 

1. 선형 조사법

충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것

 

 f(k)+1  →  f(k)+2  →  f(k)+3  →  f(k)+4 ...

 

문제점 : 충돌 횟수가 증가함에 따라 특정 영역에 데이터가 집중적으로 몰리는 현상이 발생한다 !

 

2. 이차 조사법

충돌이 발생했을 때 n2칸 옆의 슬롯이 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것

 

 f(k)+1  →  f(k)+2^2 →  f(k)+3^3  →  f(k)+4^4 ...

 

문제점 : 충돌 횟수가 증가함에 따라 특정 영역에 데이터가 집중적으로 몰리는 현상이 발생한다

 

 

3. 이중 해쉬

1차 해쉬 함수 : 키를 근거로 저장위치를 결정하기 위한 것
일반적인 ex) h1(k) = k % 15
2차 해쉬 함수 : 충돌 발생 시 몇 칸 뒤를 살필지 결정하기 위한 것
일반적인 ex) h2(k) = 1 + (k % c)  c<15, c는 소수
-> 1을 더하는 이유 = 2차 해쉬 값이 0이 되는것을 방지
-> c가 15 보다 작은 이유 = 2차 해쉬 함수 값이 가급적 1차 해쉬 값을 넘어서지 않게 하기 위함
-> c가 소수인 이유 = 소수를 선택 했을때 클러스터 현상(충돌)을 낮춘다는 통계가 있더라 ~

2차 해쉬 함수를 적용해도 충돌 일어나면 2차 해쉬 함수 값만큼 값을 곱한다 h2(k), h2(k)x2, h2(k)x3, h2(k)x4...

 

 

 

[닫힌 어드레싱 방법] -> 무슨 일이 있어도 자신의 자리에 들어감 (자리를 여러개 만듬 by 연결 리스트)

 

1. 체이닝

 

▶ 충돌 문제를 해결한 완벽한 구현 (by 연결 리스트)

 

 

 

 

[테이블의 실질적 구현]

(헤더파일)

#ifndef __TABLE2_H__
#define __TABLE2_H__

#include "Slot2.h"
#include "DLinkedList.h"

#define MAX_TBL     100

typedef int HashFunc(Key k);

typedef struct _table
{
//	Slot tbl[MAX_TBL];
	List tbl[MAX_TBL];
	HashFunc * hf;
} Table;

void TBLInit(Table * pt, HashFunc * f); 
void TBLInsert(Table * pt, Key k, Value v);
Value TBLDelete(Table * pt, Key k);
Value TBLSearch(Table * pt, Key k);

#endif

 

(소스파일)

#include <stdio.h>
#include <stdlib.h>
#include "Table2.h"
#include "DLinkedList.h"

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)) //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; //삭제할 정보 반환
				}
			}
		}
	}

	return NULL;
}

Value TBLSearch(Table * pt, Key k) //고유값을 이용하여 정보 찾음 
{
	int hv = pt->hf(k);
	Slot cSlot;

	if(LFirst(&(pt->tbl[hv]), &cSlot)) //cSlot이 테이블의 첫번째를 가리키게 함
	{
		if(cSlot.key == k)
		{
			return cSlot.val;
		}
		else
		{
			while(LNext(&(pt->tbl[hv]), &cSlot))
			{
				if(cSlot.key == k)
					return cSlot.val;
			}
		}
	}

	return NULL;
}

 

<특징>

TBLDelete와 TBLSearch의 차이점은 LRemove를 하냐 안하냐 밖에 없음 (데이터를 찾고 그것을 지우냐 안지우냐)