哈希表：开放定址法和拉链法

柔情只为你懂 2022-05-29 21:18 197阅读 0赞

开放定址法

//哈希表开放定址法
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    
    typedef int KeyType;
    typedef int ValueType;
    
    enum Status
    {
        EMPTY,//空
        EXITS,//存在
        DELETE,//删除
    };
    
    typedef struct HashNode
    {
        KeyType _key;//主键
        ValueType _value;//数值
        enum Status _status;//状态
    }HashNode;
    
    typedef struct HashTable
    {
        HashNode* _tables;//数组指针
        size_t _size;//元素个数
        size_t _N;//容量
    }HashTable;
    
    size_t GetNextPrimeNum(size_t cur);
    void HashTableInit(HashTable* ht);
    size_t HashFunc(KeyType key, size_t N);
    void Expand(HashTable* ht);
    int HashTableInsert(HashTable* ht, KeyType key, ValueType value);
    HashNode* HashTableFind(HashTable* ht, KeyType key);
    int HashTableRemove(HashTable* ht, KeyType key);
    int HashTableDestory(HashTable* ht);
    void PrintHashTable(HashTable* ht);
    
    size_t GetNextPrimeNum(size_t cur)//质数表，给增容提供最佳选择容量大小
    {
        const int _PrimeSize = 28;
        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 (size_t i = 0; i < 28; ++i)
        {
            if (_PrimeList[i]>cur)
                return _PrimeList[i];
        }
    }
    
    void HashTableInit(HashTable* ht)//哈希表初始化
    {
        assert(ht);
        ht->_N = GetNextPrimeNum(0);//设置容量大小，最初为53
        ht->_size = 0;//数组内存在元素个数初设为0
        ht->_tables =(HashNode*)malloc(sizeof(HashNode)*ht->_N);//动态分配数组的空间大小
        if (NULL == ht) 
        {
            perror("HashTable init error\n");
            return;
        }
        size_t i = 0;
        for (i = 0; i < ht->_N; i++)//将数组每个位置的状态设置为空
        {
            ht->_tables[i]._status = EMPTY;
        }
    }
    
    size_t HashFunc(KeyType key,size_t N)//哈希函数
    {
        return key % N;
    }
    
    void Expand(HashTable* ht)//增容
    {
        assert(ht);
        int i = 0;
    
        size_t N = ht->_N;//增容前的容量
        ht->_N = GetNextPrimeNum(N);//获取下一个最佳增容大小的质数
        HashNode* newTable = (HashNode*)malloc(sizeof(HashNode)*ht->_N);//创建新数组并初始化
        for (i = 0; i < ht->_N; i++)
        {
            newTable[i]._status = EMPTY;
        }
    
        size_t index = 0;
        i = 0;
        while (i < ht->_size)
        {
            if (ht->_tables[i]._status == EXITS)
            {
                index = HashFunc(ht->_tables[i]._key,ht->_N);
                while (newTable[index]._status != EMPTY)
                {
                    index++;
                    if (index == ht->_N)
                    {
                        index = 0;
                    }
                }
                newTable[index]._key = ht->_tables[i]._key;
                newTable[index]._value = ht->_tables[i]._value;
                newTable[index]._status = EXITS;
            }
            i++;
        }
        free(ht->_tables);
        ht->_tables = newTable;
    }
    
    int HashTableInsert(HashTable* ht, KeyType key, ValueType value)//插入
    {
        assert(ht);
    
        int i = 0;
        size_t index = HashFunc(key,ht->_N);//确定key在数组中对应的下标
    
        //coding for 增容
        //负载因子：不能超过0.7
        if (ht->_size * 10 / ht->_N >= 7) //避免浮点数
        {
            //增容
            Expand(ht);
        }
    
        while (ht->_tables[index]._status == EXITS)
        {
            if (ht->_tables[index]._key == key) //如果插入的元素已经存在
            {
                return -1;
            }
            index++;
            if (index == ht->_N)//如果找到尾，从头开始再找一遍
            {
                index = 0;
            }
        }
        ht->_tables[index]._key = key;
        ht->_tables[index]._value = value;
        ht->_size++;
        ht->_tables[index]._status = EXITS;
        return 0;
    }
    HashNode* HashTableFind(HashTable* ht, KeyType key)//查找
    {
        assert(ht);
    
        size_t index = HashFunc(key,ht->_N);//确定key在数组中对应的下标
    
        while (ht->_tables[index]._status != EMPTY)//如果当前位置的状态不为空
        {
            if (ht->_tables[index]._key == key)//判断该位置的key是否与查找的key相同
            {
                if (ht->_tables[index]._status == EXITS)//再判断当前位置的状态是否存在
                    return &(ht->_tables[index]);
                else//当前位置状态为“删除”
                    return NULL;
            }
            index++;
            if (index == ht->_N)
            {
                index = 0;
            }
        }
        return NULL;
    }
    int HashTableRemove(HashTable* ht, KeyType key)//删除
    {
        assert(ht);
        HashNode* node = HashTableFind(ht, key);
        if (node != NULL)//只有当前位置状态为“存在”才删除
        {
            node->_status = DELETE;
            ht->_size--;
            return 0;
        }
        else
        {
            return -1;
        }
    }
    int HashTableDestory(HashTable* ht)//销毁
    {
        assert(ht);
        free(ht->_tables);
        ht->_tables = NULL;
        ht->_size = 0;
        ht->_N = 0;
        return 0;
    }
    void PrintHashTable(HashTable* ht)//打印哈希表
    {
        assert(ht->_tables);
        for (size_t i = 0; i < ht->_N; ++i)
        {
            if (ht->_tables[i]._status == EXITS)
            {
                printf("[%d]%d ", i, ht->_tables[i]._key);
            }
            else if (ht->_tables[i]._status == EMPTY)
            {
                printf("[%d]E ", i);
            }
            else
            {
                printf("[%d]D ", i);
            }
        }
    }
    void TestHash()
    {
        HashTable ht;
        HashTableInit(&ht);
        for (int i = 0; i < 53;i++)
        {
            HashTableInsert(&ht, i,1);
        }
    
        HashTableInsert(&ht, 53, 1);
        HashTableRemove(&ht, 52);
        PrintHashTable(&ht);
    
        HashTableDestory(&ht);
        PrintHashTable(&ht);
    
        printf("\n");
    }
    
    int main()
    {
        TestHash();
        //system("pause");
        return 0;
    }

拉链法

//哈希表拉链法
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    
    typedef int KeyType;
    typedef int ValueType;
    
    typedef struct HashNode//结点
    {
        KeyType _key;//主键
        ValueType _value;//值
        struct HashNode* _next;//指针，指向下一个同义词结点
    }HashNode;
    
    typedef struct HashTable
    {
        HashNode** _tables;
        size_t _size;//元素个数
        size_t _N;//容量
    }HashTable;
    
    
    size_t GetNextPrimeNum(size_t cur);
    void HashTableInit(HashTable* ht);
    size_t HashFunc(KeyType key, size_t N);
    HashNode* BuyNode(KeyType key, ValueType value);
    int HashTableInsert(HashTable* ht, KeyType key, ValueType value);
    HashNode* HashTableFind(HashTable* ht, KeyType key);
    int HashTableRemove(HashTable* ht, KeyType key);
    void HashTableDestory(HashTable* ht);
    void PrintHashTable(HashTable* ht);
    
    size_t GetNextPrimeNum(size_t cur)//质数表，给增容提供最佳选择容量大小
    {
        const int _PrimeSize = 28;
        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 (size_t i = 0; i < 28; ++i)
        {
            if (_PrimeList[i]>cur)
                return _PrimeList[i];
        }
    }
    
    void HashTableInit(HashTable* ht)//初始化哈希表
    {
        assert(ht);
        ht->_size = 0;
        ht->_N = GetNextPrimeNum(0);
        ht->_tables = (HashNode**)malloc(sizeof(HashNode*)*ht->_N);
        size_t i = 0;
        for (; i < ht->_N; i++)
        {
            ht->_tables[i] = NULL;
        }
    }
    
    size_t HashFunc(KeyType key, size_t N)//哈希函数
    {
        return key % N;
    }
    
    HashNode* BuyNode(KeyType key, ValueType value)//创建结点
    {
        HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
        assert(newNode);
        newNode->_key = key;
        newNode->_value = value;
        newNode->_next = NULL;
        return newNode;
    }
    
    int HashTableInsert(HashTable* ht, KeyType key, ValueType value)//插入
    {
        assert(ht);
    
        //负载因子为1，增容
        if (ht->_size == ht->_N)
        {
            size_t newN = GetNextPrimeNum(ht->_N);
            HashNode** newTable = (HashNode**)malloc(sizeof(HashNode*)*newN);
            memset(newTable, NULL, sizeof(HashNode*)*newN);
            for (size_t i = 0; i < ht->_N; ++i)
            {
                HashNode* cur = ht->_tables[i];
                while (cur)
                {
                    HashNode* next = cur->_next;
                    size_t newIndex = HashFunc(cur->_key, newN);
                    //头插
                    cur->_next = newTable[newIndex];
                    newTable[newIndex] = cur;
                    cur = next;
                }
            }
            free(ht->_tables);
            ht->_tables = newTable;
            ht->_N = newN;
        }
    
    
        size_t index = HashFunc(key, ht->_N);
        HashNode* cur = ht->_tables[index];
        while (cur)
        {
            if (cur->_key == key)
            {
                return -1;
                cur = cur->_next;
            }
        }
        //头插
        HashNode* node = BuyNode(key, value);
        node->_next = ht->_tables[index];
        ht->_tables[index] = node;
        ht->_size++;
        return 0;
    }
    HashNode* HashTableFind(HashTable* ht, KeyType key)//查找
    {
        assert(ht);
        size_t index = HashFunc(key, ht->_N);
        HashNode* cur = ht->_tables[index];
        while (cur != NULL)
        {
            if (cur->_key == key)
            {
                return cur;
            }
            else
            {
                cur = cur->_next;
            }
        }
        return NULL;
    }
    int HashTableRemove(HashTable* ht, KeyType key)//删除
    {
        assert(ht);
        size_t index = HashFunc(key, ht->_N);
        HashNode* cur = ht->_tables[index];
        HashNode* prev = cur;
        while (cur != NULL)
        {
            if (cur->_key == key)
            {
                if (prev == cur)
                {
                    cur = cur->_next;
                    ht->_tables[index] = cur;
                    free(prev);
                }
                else
                {
                    prev->_next = cur->_next;
                    free(cur);
                }
                return 0;
            }
            else
            {
                prev = cur;
                cur = cur->_next;
            }
        }
        return -1;
    }
    void HashTableDestory(HashTable* ht)//销毁
    {
        assert(ht);
        HashNode* cur = NULL;
        HashNode* prev = NULL;
        for (int i = 0; i < ht->_N; i++)
        {
            cur = ht->_tables[i];
            if (cur != NULL)
            {
                while (cur != NULL)
                {
                    prev = cur;
                    cur = cur->_next;
                    free(prev);
                }
            }
        }
        free(ht->_tables);
        ht->_tables = NULL;
        ht->_size = 0;
        ht->_N = 0;
    }
    
    void PrintHashTable(HashTable* ht)//打印哈希表
    {
        assert(ht);
        HashNode* cur = NULL;
        for (int i = 0; i < ht->_N; i++)
        {
            if (ht->_tables[i] != NULL)
            {
                cur = ht->_tables[i];
                printf("[%d] are:", i);
                while (cur != NULL)
                {
                    printf("%d ", cur->_key);
                    cur = cur->_next;
                }
                printf("\n");
            }
            else
            {
                printf("[%d] is NULL\n", i);
            }
        }
    }
    
    void TestHash()
    {
        HashTable ht;
        HashTableInit(&ht);
        for (int i = 0; i < 53; i++)
        {
            HashTableInsert(&ht, i, 1);
        }
        PrintHashTable(&ht);
    
        HashTableInsert(&ht, 53, 1);
        PrintHashTable(&ht);
    
        HashTableRemove(&ht, 52);
        PrintHashTable(&ht);
    
        HashTableDestory(&ht);
        PrintHashTable(&ht);
    }
    
    int main()
    {
        TestHash();
        return 0;
    }