哈希表：初始化、插入、删除、查找、查找

首先看一个面试题：
找到一个字符串中第一次出现一次的字符？
思路是：如果是a-z26个字符，可以设置大小为26的数组，将每个字符出现的次数依次存放在数组里。如果是所有字符，将所有字符按照各自的ASSCII码作为下标将出现的次数存放在数组里。
代码如下：

char FindFirstChar( const char *str)
{
    int hashtable[256] = { 0 };//所有字符
    //int hashtable[26] = { 0 };//记录每次字符出现的次数,初始设置出现0次
    char *s1 = ( char*)str;
    //char *s1 =(unsigned char*)str;
    while (*s1)
    {
        hashtable[*s1 ]++;
        //hashtable[*s1 - 'a']++;
        s1++;
    }
    s1 = (char *)str;
    //s1 = (unsigned char *)str;
    while (*s1)
    {
        if (hashtable[*s1] == 1)
            return *s1;
        /*if (hashtable[*s1 - 'a'] == 1)
            return *s1;*/
        s1++;
    }
    return -1;
}

对于这个题用的就是哈希的思想，找到每个字符对应的位置。
哈希表是通过哈希函数使元素的存储位置与它 的关键码之间能够建立一一映射的关系，在查找时可以很快找到该元素。
哈希函数Hash(key)=key%m(m为内存单元的个数）。

哈希冲突：
1.闭散列：当表中还有被装满，可以把key存放在表中的“下一个“”空位置。即从发生冲突的位置开始，依次向后探测，直到找到空位置为止。
当散列表的载荷因子：填入表中的元素个数/散列表的长度结果在0.8以上时冲突的可能性越大。所以当载荷因子大于 0.8时就应该扩容。
2.二次探测:Hi=(Ho+i^2)%m,Hi=(Ho-i^2)%m,i=1,2,3…(m是表的大小）
插入：
使用哈希函数找到待插入元素在哈希表的位置，如果该位置没有元素则直接插入新元素，如果该位置中有元素和待插入元素相同，则不用插入，如果该位置有元素但不是待插入元素即发生哈希冲突，则可以使用线性探测和二次探测找到下一个空位置。
代码如下：
Hash.h

#pragma once
typedef int HTDatatype;
enum STATUS
{
    EXIST,//该位置有数据
    DELETE,//该位置数据被删除
    EMPTY,//该位置没有数据
};
typedef struct HashNode
{
    HTDatatype _key;//数据
    enum STATUS _status;//状态
}HashNode;
typedef struct HashTable阿
{
    HashNode *hash;
    size_t _size;//哈希表里有效数据个数
    size_t _capacity;//哈希表大小
}HashTable;

void HTInit(HashTable *ht, size_t capacity);//哈希表初始化
//成功：0，失败-1
int HTInsert(HashTable *ht, HTDatatype key);//插入数据
HTDatatype HTFind(HashTable *ht, HTDatatype key);//查找
int HTRemove(HashTable *ht, HTDatatype key);//删除
void HTPrint(HashTable ht);//打印哈希表
void HTDestroy(HashTable *ht);//销毁哈希表

Hash.c

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
#include"Hash.h"
void TestHashTable()
{
    HashTable ht;
    HTInit(&ht, 0);//哈希表初始化
    HTInsert(&ht, 37);//插入数据
    HTInsert(&ht, 25);//插入数据
    HTInsert(&ht, 14);//插入数据
    HTInsert(&ht, 36);//插入数据
    HTInsert(&ht, 49);//插入数据
    HTInsert(&ht, 68);//插入数据
    HTInsert(&ht, 57);//插入数据
    HTInsert(&ht, 11);//插入数据
    HTPrint(ht);//打印哈希表;
    printf("****************************\n");
    srand((unsigned)time(0));//设置时间戳种子
    for (int i = 0; i < 53; i++)
    {
        HTInsert(&ht, rand());
    }
    HTPrint(ht);//打印哈希表;
    HTDestroy(&ht);
}
int main()
{
    TestHashTable();
    system("pause");
    return 0;
}
int  GetPrime(HashTable *ht)
{
    const int _PrimeSize = 28;
    //该数据都是经过许多人测试的素数，能够满足需求，冲突较小
    static const unsigned long _PrimeList[_PrimeSize] = {

        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

    };
    int index = 0;
    while (index < _PrimeSize)
    {
        if (ht->_capacity < _PrimeList[index])
        {
            return _PrimeList[index];
        }
        index++;
    }
    return _PrimeList[_PrimeSize - 1];
}
void HTInit(HashTable *ht, size_t capacity)//哈希表初始化
{
    assert(ht);
    ht->_size = 0;
    ht->_capacity = capacity;
    ht->_capacity = GetPrime(ht);//哈希表是素数大小，减少冲突
    ht->hash = (HashNode *)malloc(sizeof(HashNode)*ht->_capacity);
    assert(ht->hash);
    for (int i = 0; i < ht->_capacity; i++)
    {
        ht->hash[i]._status= EMPTY;//必须初始化状态
    }
}
int  HashFunc(HashTable * ht, HTDatatype key)
{
    return key%(ht->_capacity);
}
void CheckCapacity(HashTable *ht)
{
    //对于哈希表，并不是size=capacity时才扩容，如果size=capacity,那么当哈希表全部存满时，
    //无法用EMPTY判断查找数据,将会陷入死循环
    //而是当a=填入表中的数据/哈希表长度>=0.7时就要扩容，a越大，冲突可能性越大
    if (ht->_size * 10 / ht->_capacity >= 7)//负载因子大于0.7，需要扩容
    {
        //扩容：重新定义一个哈希表，将ht里的数据重新插入到newht,不能直接拷贝数据，
        //因为newht的表长发生变化，数据存放的位置也将发生变化
        HashTable newht;
        HTInit(&newht,ht->_capacity *2);
        for (int i = 0; i < ht->_capacity; i++)
        {
            if(ht->hash[i]._status==EXIST)//必须加上
            HTInsert(&newht,ht->hash[i]._key );//插入数据
        }
        free(ht->hash);
        ht->hash = newht.hash;
        ht->_size = newht._size;
        ht->_capacity = newht._capacity;
    }
}
int HTInsert(HashTable *ht, HTDatatype key)//插入数据
{
    assert(ht);
    CheckCapacity(ht);//判断容量
    int index = HashFunc(ht, key);
    int i = 1;
    while (ht->hash[index]._status == EXIST)//冲突，
    {
        int tmp = index;
        if (ht->hash[index]._key == key)
            return -1;
        /*index++;
        if (index == ht->_capacity)
            index = 0;*/ //线性探测
        //二次探测
        index = tmp + i*i;
        i++;
        index = index%ht->_capacity;

    }
    ht->hash[index]._key = key;
    ht->_size++;
    ht->hash[index]._status = EXIST;
    return 0;
}
void HTPrint(HashTable ht)//打印哈希表
{
    for (int i = 0; i < ht._capacity; i++)
    {
        if (ht.hash[i]._status == EXIST)
            printf("EXIST:%d  ", ht.hash[i]._key);
        else if (ht.hash[i]._status == DELETE)
            printf("DELETE:%d  ", ht.hash[i]._key);
        else
            printf("EMPTY:NULL ");       
    }
    printf("\n");
}
HTDatatype  HTFind(HashTable *ht, HTDatatype key)//查找
{
    assert(ht);
    int index = HashFunc(ht, key);
    while (ht->hash[index]._status !=EMPTY)
    {
        if (ht->hash[index]._key == key)
        {
            if (ht->hash[index]._status == EXIST)
                return ht->hash[index]._key;
            else//状态是删除且值相等，index后不会再存在该数据，直接返回
                return -1;
        }   
        index++;
        if (index == ht->_capacity)
            index = 0;
    }
    return -1;
}
int HTRemove(HashTable *ht, HTDatatype key)//删除
{
    assert(ht);
    int index = HashFunc(ht,key);
    while (ht->hash[index]._status != EMPTY)
    {
        if (ht->hash[index]._key == key)
        {
            if (ht->hash[index]._status == EXIST)
            {
                ht->hash[index]._status = DELETE;
                ht->_size--;
            }
            else
                return - 1;//该数据已经被删除，无法再删除
        }
        index++;
        if (index == ht->_capacity)
            index = 0;
    }
    return -1;//没有找到该数据，删除失败
}
void HTDestroy(HashTable *ht)//销毁哈希表
{
    assert(ht);
    free(ht->hash);
    ht->hash = NULL;
    ht->_capacity = 0;
    ht->_size = 0;
}

测试用例：