해시 시계 (지퍼 법)

> 산열 법 을 체인 주소 법 (체인 법) 이 라 고도 부른다.
산열 법: 먼저 관건 적 인 코드 집합 에 대해 산열 함수 로 산열 주 소 를 계산 하고 같은 주 소 를 가 진 관건 적 인 코드 는 같은 서브 집합 에 귀착 한다. 모든 서브 집합 을 하나의 통 이 라 고 하고 각 통 의 요 소 는 하나의 단일 체인 표를 통 해 연결 되 며 각 링크 의 머리 결점 은 하 쉬 표 에 저장 된다.요소 의 키 코드 는 37, 25, 14, 36, 49, 68, 57, 11 이 고 해시 표 는 HT [12] 이 며 표 의 크기 는 12 이 며 해시 함 수 는 Hash (x) = x% 11 Hash (37) = 4 Hash (25) = 3 Hash (36) = 3 Hash (49) = 5 Hash (68) = 2 Hash (11) = 0 해시 함 수 를 사용 하여 각 요소 가 있 는 통 번 호 를 계산 하고 같은 통 의 링크 에 해시 충돌 요 소 를 저장 합 니 다.일반적으로 모든 통 에 대응 하 는 링크 의 결산 점 이 매우 적 고 n 개의 관건 적 인 코드 를 특정한 해시 함 수 를 통 해 산 목록 에 있 는 m 개의 통 에 저장 하면 모든 통 에 있 는 링크 의 평균 길 이 는?검색 길이 가 n 인 순서 표를 검색 평균 길이 로 대체 하여 검색 효율 이 훨씬 빠르다.체인 주소 법 처리 가 넘 쳐 서 링크 지침 을 증설 해 야 합 니 다. 저장 비용 이 증가 한 것 같 습 니 다.사실: 주소 법 을 열 려 면 검색 효율 을 확보 하기 위해 대량의 빈 공간 을 유지 해 야 합 니 다. 예 를 들 어 2 차 탐사 법 은 인자 a < = 0.7 을 불 러 오 라 고 요구 하고 표 항목 이 차지 하 는 공간 은 포인터 보다 많 기 때문에 체인 주소 법 을 사용 하 는 것 이 주소 법 을 여 는 것 보다 저장 공간 을 절약 합 니 다.
산열 의 실현 (지퍼 법) HashNode. h

#pragma once
#include 
#include
#include
typedef int KeyType;
typedef int valueType;
typedef struct HashNode
{
    KeyType _key;
    valueType _value;
    struct HashNode*_next;
}HashNode;
typedef struct HashTable
{
    HashNode** table;
    size_t _size;
    size_t _N;
}HashTable;
HashNode*BuyHashNode(KeyType key, valueType value);
size_t GetHashTablePrime(size_t N);
void HashTableInit(HashTable*ht,int size);//   
void HashTablePrint(HashTable*ht);
int HashTableInsert(HashTable*ht, KeyType key, valueTypevalue);//
HashNode* HashTableFind(HashTable*ht, KeyType key);//  
size_t HashTableErase(HashTable*ht, KeyType key);//  
void HashTableDesTroy(HashTable*ht);//  

HashNode.c

#include"HashNode.h"
HashNode* BuyHashNode(KeyType key, valueType value)
{
    HashNode*Node = (HashNode*)malloc(sizeof(HashNode));
    assert(Node);
    Node->_key = key;
    Node->_value = value;
    Node->_next = NULL;
    return Node;
}
void HashTableInit(HashTable*ht,int size)//   
{
    assert(ht);
    ht->_size = 0;
    ht->_N = size;
    //               
    ht->table = (HashTable**)malloc(sizeof(HashTable*)*ht->_N);
    assert(ht->table);
    memset(ht->table, 0, sizeof(HashTable*)*ht->_N);
}
size_t GetHashTablePrime(size_t N)
{
    static const unsigned long _PrimeList[28] =
        {
            53ul, 97ul, 193ul, 389ul, 769ul,
            1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
            49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
            1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
            50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
            1610612741ul, 3221225473ul, 4294967291ul
        };
        for (int i = 0; i < 28; i++)
        {
            if (N < _PrimeList[i])
            {
                N = _PrimeList[i];
                return N;
            }

        }
        return _PrimeList[27];


}
size_t HashFunc(KeyType key, size_t N)
{
    return key%N;
}

int HashTableInsert(HashTable*ht, KeyType key, valueType value)//  
{

    assert(ht);
    HashNode* node = BuyHashNode(key, value);
    if (ht->_size * 10 / ht->_N > 7)
    {
        //  
        size_t newN = GetHashTablePrime(ht->_N);
        HashTable newht;
        HashTableInit(&newht, newN);

        for (size_t i = 0; i < ht->_N; i++)
        {
            HashNode* cur = ht->table[i];//           
            if (ht->table[i])
            {
                size_t index = HashFunc(cur->_key, newht._N);//                
                while (cur)
                {
                    cur->_next = newht.table[index];//                 
                    newht.table[index] = cur;//                       
                    cur = cur->_next;
                }

            }
        }
        free(ht->table);
        ht->_N = newN;//          
        ht->table = newht.table;//      
    }

    size_t index = HashFunc(key, ht->_N);
    if (ht->table[index])
    {
        HashNode*cur = ht->table[index];
        while (cur)
        {
            if (cur->_key == key)
            {
                return -1;
            }
            cur = cur->_next;
        }

    }
    node->_next = ht->table[index];
    ht->table[index] = node;
    ht->_size++;
    return 0;
}
void HashTablePrint(HashTable*ht)
{
    for (size_t i = 0; i < ht->_N; i++)
    {
        if (ht->table[i])
        {
            HashNode*cur = ht->table[i];
            while (cur)
            {
                printf("[%d]->%d
 ",i, cur->_key);
                cur = cur->_next;
            }

        }
    }
}
HashNode *HashTableFind(HashTable*ht, KeyType key)
{
    assert(ht);
    size_t index = HashFunc(key, ht->_N);
    if (ht->table[index])
    {
        if (ht->table[index]->_key=key)
        {
            return ht->table[index];
        }
        else
        {
            HashNode*cur = ht->table[index];
                while (cur)
                {
                    if (cur->_key==key)
                    {
                        return cur;
                    }
                    cur = cur->_next;
                }
                return NULL;
        }
    }
}
size_t HashTableErase(HashTable*ht, KeyType key)
{
    assert(ht);
    size_t index = HashFunc(key, ht->_N);
    if (ht->table[index])
    {
        HashNode* cur = ht->table[index];
        HashNode* prev = ht->table[index];
        while (cur)
        {
            if (cur == prev&&cur->_key == key)//      
            {
                ht->table[index] = cur->_next;
                free(cur);
                cur = NULL;
                ht->_size--;
                return 0;
            }
            else if (cur->_key == key)//    
            {
                prev = cur->_next;
                free(cur);
                cur = NULL;
                ht->_size--;
                return 0;
            }
            prev = cur;
            cur = cur->_next;
        }
        return -1;
    }

    else
    {
        return -1;
    }
}
void HashTableDesTroy(HashTable*ht)
{
    assert(ht);
    for (size_t i = 0; i < ht->_N; i++)
    {
        if (ht->table[i])
        {
            HashNode*cur = ht->table[i];
            while (cur)
            {
                HashNode*tmp = cur;
                cur = cur->_next;
                free(tmp);
                tmp = NULL;

            }
        }
    }
    free(ht->table);
    ht->table = NULL;
    ht->_N = 0;
    ht->_size = 0;
}

test.c

#include"HashNode.h"
void test()
{
    HashTable ht;
    HashTableInit(&ht,5);
    HashTableInsert(&ht, 8,0);
    HashTableInsert(&ht, 11, 0);
    HashTableInsert(&ht, 10, 0);
    HashTableInsert(&ht, 12, 0);
    HashTableInsert(&ht, 2, 0);
    HashTableInsert(&ht, 5, 0);
    HashTableInsert(&ht, 20, 0);
    HashTablePrint(&ht);
    printf("
");

    printf("%d
 ", HashTableFind(&ht, 10)->_key);
    printf("%d
 ", HashTableFind(&ht, 12)->_key);
    printf("%d
 ",HashTableFind(&ht, 20)->_key);
    printf("%d
", HashTableFind(&ht, 8)->_key);
    printf("%p
 ", HashTableFind(&ht, 1)->_key);
    printf("
");
    HashTableErase(&ht, 8);
    HashTableErase(&ht, 2);
    HashTableErase(&ht, 5);
    HashTableErase(&ht, 20);
    HashTablePrint(&ht);
    printf("
");
    HashTableDesTroy(&ht);
    HashTablePrint(&ht);


}
int main()
{
    test();
    system("pause");
    return 0;
}