CH 13-2 충돌(Collision)문제의 해결책(3)
지금까지 다룬 충돌 해결방법을 열린 어드레싱 방법(open addressing method)라고 한다. 이는 충돌이 발생하면 다른 자리에 대신 저장한다는 의미이다.
이번에 알아볼 충돌해결책은 이와 반대로 닫힌 어드레싱 방법(close addressing method)라고 한다. 충돌이 생겨도 다른 자리를 찾아보는게 아니라, 어떻게든 자기 자리에 저장한다는 의미이다.
그 중 체이닝에 대해 배워보겠다…
어떻게든 자리 자기에 저장한다는 건… 결국엔 자리를 많이 만든다는 것이다… 따라서 슬롯의 배열이 2차원 배열이 되어야 한다.
위의 그림을 연결리스트 기반으로 만들면, 아래의 그림이 된다.
위의 그림을 보면… 배열의 특정 인덱스에 연결리스트들을 연결했다. 이 모습이 chain같다고 해서 체이닝이라고 부른다.
앞으로 이를 구현할 것이다. 앞서 구현한 연결리스트를 활용하면… 위의 모델을 매우 쉽게 구현할 수 있다.
CH13-2 충돌문제의 해결책(4)
직접 구현해보자…
#include <stdio.h>
#include <stdlib.h>
#include "Slot_2.h"
#include "DLinkedList_2.h"
#include "Table_2.h"
void TBLInit(Table * pt, HashFunc * f)
{
int i;
for (i = 0; i < MAX_TBL; i++) //Table의 전체 slot형배열을 돌며
ListInit(&(pt->tbl[i])); // 모든 index의 list를 초기화한다.
pt->hf = f; //해시 함수를 등록한다.
}
void TBLInsert(Table * pt, Key k, Value v)
{
int hv = pt->hf(k); //키를 해시함수에 입력해 인덱스를 얻는다.
Slot nSlot = { .key = k, .val = v };
LInsert(&(pt->tbl[hv]), &nSlot);
}
Value TBLDelete(Table * pt, Key k)
{
int hv = pt->hf(k); //키를 해시함수에 입력해 인덱스를 얻는다.
LData newData;
Value rValue;
LFirst(&(pt->tbl[hv]), &newData);
if (newData->key == k)
rValue = LRemove(&(pt->tbl[hv]))->val;
else
{
while (newData->key != k)
LNext(&(pt->tbl[hv]), &newData);
rValue = LRemove(&(pt->tbl[hv]))->val;
}
return rValue;
}
Value TBLSearch(Table * pt, Key k)
{
int hv = pt->hf(k);
LData newData;
Value rValue;
LFirst(&(pt->tbl[hv]), &newData);
if (newData->key == k)
rValue = newData->val;
else
{
while (newData->key != k)
LNext(&(pt->tbl[hv]), &newData);
rValue = newData->val;
}
return rValue;
}
생각만큼 간단한건 아니었다… 내가 너무 양심없는건가?
그리고 물론 한번에 빌드되지 않았다.. 문제는 한두개가 아니었지만, 핵심적인 부분을 이야기하자면