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

开放定址法

//哈希表开放定址法
#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;
}