13-1. 빠른 탐색을 보이는 해쉬 테이블
테이블(Table) 자료구조의 이해
AVL트리는 ’단번에’ 찾아내는 방식이라고 말하기는 어렵다
시간 복잡도
- AVL 트리의 탐색 연산 : O(logn)
- 테이블의 탐색 연산 : O(1)
키(key)와 값(value)이 하나의 쌍을 이룬다.
키(key)가 존재하지 않는 ‘값’은 저장할 수 없다.
모든 키는 중복되지 않는다.
- 테이블 : 사전의 구조. 맵(map)이라고 부른다.
배열을 기반으로 하는 테이블
- 키와 값을 하나의 쌍으로 묶기 위해서 정의한 구조체
typedef struct _empInfo
{
int empNum; //직원의 고유변호 : key
int age; //직원의 나이 : value
}키를 결정하였다면, 이를 기반으로 데이터를 단번에 찾을 수 있어야 한다
테이블에 의미를 부여하는 해쉬 함수와 충돌문제
그 결과가 동일한 것을 가리켜 ’충돌(Collision)’이라고 한다
-
슬롯의 상태
1) Empty : 이 슬롯에는 데이터가 저장된바 없다.
2) Deleted : 이 슬롯에는 데이터가 저장된바 있으나 현재는 지워진 상태이다.
3) Inuse : 이 슬롯에는 현재 유효한 데이터가 저장되어 있다. -
테이블 구조
#define MAX_TBL 100
typedef int HashFunc(key, k);
typedef struct _table
{
Slot tbl[MAX_TBL];
HashFunc *hf;
}
// 테이블의 초기화
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);- 테이블 구현
#include <stdio.h>
#include <stdlib.h>
#include "Table.h"
void TBLInit(Table * pt, HashFunc * f)
{
int i;
// 모든 슬롯 초기화
for(i = 0 ; i < MAX_TBL; i++)
(pt->tbl[i]).status = EMPTY;
pt->hf = f; //해쉬 함수 등록
}
void TBLInsert(Table * pt, Key k, Value v)
{
int hv = pt->hf(k);
pt->tbl[hv].val = v;
pt->tbl[hv].key = k;
pt->tbl[hv].status = INUSE;
}
Value TBLDelete(Table * pt, Key k)
{
int hv = pt->hf(k);
if((pt->tbl[hv]).status != INUSE)
{
return NULL;
}
else
{
(pt->tbl[hv]).status = DELETED;
return (pt->tbl[hv]).val; //소멸 대상의 값 반환
}
}
Value TBLSearch(Table *pt, Key k)
{
int hv = pt->hf(k);
if((pt->tbl[hv]).status != INUSE)
return NULL;
else
return (pt->tbl[hv]).val; //탐색 대상의 값 반환
}좋은 해쉬 함수의 조건
- 좋은 해쉬 함수를 사용한 결과
전체 영역에 고루 분포
‘충돌’이 발생할 확률이 낮다
좋은 해쉬 함수는 ’충돌’을 덜 일으키는 함수이다
좋은 해쉬 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만들어 낸다
자릿수 선택(Digit Selection) 방법과 자릿수 폴딩(Digit Folding) 방법
- 비트 추출 방법 : 탐색 키의 비트 열에서 일부 추출 및 조합하는 방법
- 자릿수 폴딩
종이를 접듯이 숫자를 겹치게 하여 더한 결과를 해쉬 값으로 결정하는 방법
13-2. 충돌(Collision) 문제의 해결책
선형 조사법(Linear Probing)과 이차 조사법(Quadratic Probing)
- 해시 함수 : key % 7
1) 키가 9인 데이터의 해쉬 값 : 2
2) 키가 2인 데이터의 해쉬 값 : 2 -> 충돌 발생 -> 옆자리 탐색
3) 키가 9인 데이터의 삭제
선형 조사법의 순서
’클러스터(Cluster) 현상’ 즉, 특정 영역에 데이터가 몰리는 현상이 발생할 수 있다
이차 조사법의 순서
이중 해쉬(Double Hash)
이차 조사법의 문제
: 해쉬 값이 같으면, 충돌 발생시 빈 슬롯을 찾기 위해서 접근하는 위치가 항상 동일하다
- 1차 해쉬 함수 : 키를 근거로 저장위치를 결정하기 위한 것
- 2차 해쉬 함수 : 충돌 발생 시 몇 칸 뒤를 살필지 결정하기 위한 것
Ex)
- 1차 해쉬 함수 : h1(k) = k % 15
- 2차 해쉬 함수 : h2(k) = 1 + (k % c)
체이닝(Chaining)
- 열린 어드레싱 방법(open addressing method) : 충돌이 발생하면 다른 자리에 대신 저장
- 닫힌 어드레싱 방법(closed addressing method) : 무슨 일이 있어도 자기 자리에 저장을 한다
1) 배열 기반 닫힌 어드레싱 방법
2) 연결리스트 기반 닫힌 어드레싱 방법
하나의 해쉬 값에 다수의 슬롯을 둘 수 있다
- 닫힌 어드레싱 방법 구조체
typedef int key;
typedef Person *value;
typedef struct _slot
{
Key key;
Value val;
} Slot;슬롯의 상태 정보를 표시할 필요가 없다.
- 리스트형으로 변환한 헤더파일
#define MAX_TBL 100
typedef int HashFunc(Key k);
typedef struct _table
{
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);1. 구조체 Slot을 연결 리스트의 노드로 활용
typedef struct _slot // 구조체 Slot이 연결 리스트의 노드 역할을 겸하는 구조
{
Key key;
Value val;
struct _slot * next; //다음 노드를 가리키는 포인터 변수
} Slot;2. 슬롯과 노드를 구분하는 구조 1
typedef Slot * Data; //노드에 저장할 데이터는 Slot형 변수의 주소 값이다!
typedef struct _node
{
Data data;
struct _node *next;
} Node;3. 슬롯과 노드를 구분하는 구조 2
- 구조체
typedef Slot Data; //노드에 저장할 데이터는 Slot형 변수이다!
typedef struct _node
{
Data data;
struct _node *next;
} Node;- 헤더파일
#include "Slot2.h"
// 중간 생략 //
typdef Slot LData; //변경된 typedef 선언문
typedef struct _node
{
LData data;
struct _node * next;
} Node;
typedef struct _LinkedList
{
Node * head;
Node * cur;
Node * before;
int numOfData;
int (*comp)(LData d1, LData d2);
} _LinkedList;
// 이하 생략 //- 테이블 함수
#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))
{
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))
{
if(cSlot.key == k)
{
return cSlot.val;
}
else
{
while(LNext(&(pt->tbl[hv]), &cSlot))
{
if(cSlot.key == k)
{
return cSLot.val;
}
}
}
}
return NULL;
}우리가 구현한 테이블과 관련해서 반성할 점
- 테이블 삭제, 탐색 관련 함수
Value TBLDelete(Table *pt, Key k)
{
….
return NULL; // 삭제할 대상이 존재하지 않는 경우
}
Value TBLSearch(Table *pt, Key k)
{
….
return NULL; // 찾는 대상이 존재하지 않을 경우
}반환되는 값, 테이블에 저장되는 값은 메모리의 주소 값이라고 가정합니다. 달리 말해서 Value는 포인터 형으로 선언된다고 가정합니다.
NULL은 그 자체로 정수 0이기 때문에 다른 용도로 사용할 경우, 0이라는 의미를 지니는 데이터로 오해할 수 있다
- 변경된 테이블 삭제, 탐색 관련 함수
Value TBLDelete(Table *pt, Key k)
{
….
return FALSE; // 삭제할 대상이 존재하지 않는 경우
}
Value TBLSearch(Table *pt, Key k)
{
….
return FALSE; // 찾는 대상이 존재하지 않을 경우
}
Back-end Developer