[データ構造]テーブルとハッシュ-5

チェニン

私たちが前に学んだ方法を指します.
オープン・アドレス・メソッド
これは、競合が発生した場合、代わりに別の場所に格納されることを意味します.
逆に、今回は「クローズドアドレッシングメソッド(closed addressing method)」と呼ばれています.
そして、どんなことがあっても、自分の位置で保存することを意味します.
「じゃあ…衝突しても自分の席に入るのか?どうしよう…?」
どうしてそんなことができるの?
数席しか用意できませんが、他に方法はありません!!
配列と接続リストを使用して作成する方法があります.
まずは配列で作りましょう

整列

2 Dアレイを構成し、ハッシュ値で複数のスロットを設定できます.
でも!!!これはよく言及される方法ではない.
これは、競合が発生していない場合、大量のメモリが浪費され、競合の最大回数を決定する必要があるためです.
したがって、接続リストのフィルタリング方法を使用します.

接続リスト

見えますか.これはリストを接続するモードです.
この方法では、1つのハッシュ値に複数のスロットを配置できます.
したがって、同じハッシュ値でバンドルされた接続済みスロットをすべて表示する必要があります.これは不便ですが.
ハッシュ関数を定義した場合、スロットの長さはあまり長くありません.

競合を解決するためのフィルタの実装

そのために
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));

#endif

Table2.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;
}

競合が発生せず、出力に成功しました.
これで、テーブルとハッシュについての話は終わりました.
パチパチ
ふろく

私たちが実施した表について、反省すべき点

TBSDelete、TBL Search関数では、ターゲットが見つからない場合にNULLを返す必要があります.
このNULLは次のように返されます.
メモリのアドレス値が返された場合は問題ありません.
int型の場合、NULLは整数0として認識される.
これらのエラーを避けるために、

int TBLDelete(Table *pt, Key k, Value * pv)
{
	return FALSE; 
}

に示すように、より一般的な関数を記述するために、Valueがポインタ型でなければならないという制約を解消することができる.
戻り値呼び出し関数が成功したかどうかを定義し、パラメータを使用して削除または参照ターゲットの値を取得します.
ここから
バリューがアドレス値でなければならないという制約も解消された.