체이닝
앞서 우리가 배운 방법들을 가리켜
"열린 어드레싱 방법(Open addressing Method)"라고 하는데
이는 충돌이 발생하면 다른 자리에 대신 저장한다는 의미가 담겨 있다.
반면, 이번에는 "닫힌 어드레싱 방법(closed addressing method)"이라 한다.
그리고 이는 무슨 일이 있어도 자신의 자리에 저장응ㄹ 한다는 의미가 담겨 있다.
"그러면.. 충돌이 발생해도 자신의 자리에 들어간다는 말인가요? 어떻게요..?"
이것이 어떻게 가능할까?
자리를 여러개를 마련하는 수밖에 별다른 방법이 없지만!!
이를 배열과 연결리스트를 이용하여 만드는 법이 있다.
우선 배열을 통해 만들어보자
배열
2차원 배열을 구성하여 해쉬 값 별로 다수의 슬롯을 마련할 수 있다.
하지만!!! 이는 흔히 거론되는 방법이 아니다.
그 이유는 충돌이 발생하지 않을 경우 메모리 낭비가 심하고, 충돌의 최대 횟수를 결정해야하는 부담이 있다.
따라서 연결리스트를 이용하는 "체이닝"이라는 방법을 이용한다.
연결리스트
보이는가! 연결리스트의 모델로 연결해나가는 방식이다.
이 방법을 사용하면 하나의 해쉬 값에 다수의 슬롯을 둘수있다.
따라서 동일한 해쉬 값으로 묶여있는 연결된 슬롯을 모두~ 조사해야지 탐색이 가능하다는 불편이 따르지만!
해쉬 함수를 잘 정의한다면 슬롯의 길이는 그다지 길지 않을것이다.
충돌 문제의 해결을 위한 체이닝의 구현
이를 위해서
Person.c,h
Slot.h
Table.c,h
DLinkedList.c,h(연결리스트 구현결과)
파일 들이 필요하다!
Slot 은 변형해줘야한다!
Slot2.h
//
// Slot.h
// HashTable
//
// Created by 서희찬 on 2021/04/22.
//
#ifndef Slot_h
#define Slot_h
#include "Person.h"
typedef int Key; // ssn
typedef Person * Value;
typedef struct _slot
{
Key key;
Value val;
}Slot;
#endif /* Slot_h */더 이상 상태여부는 필요없으므로 없애줬다.
Table2.h
//
// Table.h
// HashTable
//
// Created by 서희찬 on 2021/04/22.
//
#ifndef Table_h
#define Table_h
#include "DLinkedList.h"
#include "Slot.h"
#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);
#endif /* Table_h */
Slot형 배열을 List형 배열로 바꾸었다!
이를위해 연결리스트 헤더파일 선언문도 추가하였다.
이제 연결 리스트와 구조체 Slot 관계를 고민해봐야한다.
- 슬롯을 연결 리스트의 노드로 활용
이렇게 한다면 리스트 자료구조와 관련된 코드를 직접 새로 작성하는 경우에 생각해 볼 수 있다.
- 슬로과 노드를 구분 한다.
이는 노드에 슬롯의 주소값을 저장하는 형태이다.
추천 하는 방법은 당연히 구분1,2 이다
그 이유는 이 방법을 선택해야 앞서 구현한 연결 리스트를 활용할 수 있기 때문이다!!!
그럼 나머지 코드들을 작성해보자
DLinkedList.h
#ifndef __D_LINKED_LIST_H__
#define __D_LINKED_LIST_H__
#include "Slot2.h"
#define TRUE 1
#define FALSE 0
// typedef int LData;
typedef Slot LData;
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;
typedef LinkedList List;
void ListInit(List * plist);
void LInsert(List * plist, LData data);
int LFirst(List * plist, LData * pdata);
int LNext(List * plist, LData * pdata);
LData LRemove(List * plist);
int LCount(List * plist);
void SetSortRule(List * plist, int (*comp)(LData d1, LData d2));
#endifTable2.c
//
// Table.c
// HashTable
//
// Created by 서희찬 on 2021/04/22.
//
#include <stdio.h>
#include <stdlib.h>
#include "Table.h"
#include "DLinkedList.h"
void TBLInit(Table * pt, HashFunc * f)
{
int i;
// reset all slot
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;
}
마지막으로 main 함수를 보자
#include <stdio.h>
#include <stdlib.h>
#include "Person.h"
#include "Table.h"
int MyHashFunc(int k)
{
return k % 100;
}
int main(void)
{
Table myTbl;
Person * np;
Person * sp;
Person * rp;
TBLInit(&myTbl, MyHashFunc);
// 데이터 입력
np = MakePersonData(900254, "Lee", "SEOUL");
TBLInsert(&myTbl, GetSSN(np), np);
np = MakePersonData(900354, "Seo", "MASAN");
TBLInsert(&myTbl, GetSSN(np), np);
np = MakePersonData(900827, "Hwe", "SEOUL");
TBLInsert(&myTbl, GetSSN(np), np);
// 데이터 탐색
sp = TBLSearch(&myTbl, 900254);
if(sp != NULL)
ShowPerInfo(sp);
sp = TBLSearch(&myTbl, 900354);
if(sp != NULL)
ShowPerInfo(sp);
sp = TBLSearch(&myTbl, 900827);
if(sp != NULL)
ShowPerInfo(sp);
// 데이터 삭제
rp = TBLDelete(&myTbl, 900254);
if(rp != NULL)
free(rp);
rp = TBLDelete(&myTbl, 900354);
if(rp != NULL)
free(rp);
rp = TBLDelete(&myTbl, 900827);
if(rp != NULL)
free(rp);
return 0;
}
충돌을 일으키지 않고 성공적으로 출력이 된다.
이로서 테이블과 해쉬에 대한 이야기는 끝이 났다.
짝짝짝
부록
우리가 구현한 테이블과 관련해서 반성할 점
TBLDelete,TBLSearch 함수는 대상을 찾지 못하면 NULL을 반환하도록하는데
이 NULL의 반환은
반환되는 값이 메모리의 주소 값이라면 문제가 없지만!
int 형이라면 NULL 을 정수0 으로 인식할수 있다.
이러한 오류를 피하기 위해
int TBLDelete(Table *pt, Key k, Value * pv)
{
return FALSE;
}와 같이 Value가 포인터 형이어야 한다는 제약사항을 없애 좀 더 일반적인 함수를 짤줄수 있다.
반환 값을 통해 함수호출 성공여부를, 매개변수를 통해 삭제또는 탐색 대상의 값을 얻도록 정의 하였다!
이로써
Value는 주소 값이어야한다는 제약사항도 소멸되었다.
