[数据结构与算法]C语言 哈希表的简单实现

简介

?? 哈希表：也叫做散列表。是根据关键字和值（Key-Value）直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value，然后把键值对映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数（散列函数），用于存放记录的数组叫做 哈希表（散列表）。 哈希表的关键思想是使用哈希函数，将键 key 和值 value 映射到对应表的某个区块中。

哈希冲突

??根据上述内容不难发现会出现特殊情况，就是通过不同的 Key，可能访问到同一个地址，这种现象叫作碰撞（Collision）。而通过某个 Key 一定会得到唯一的 Value 地址。
冲突的处理方式也有很多，下面介绍几种。

• 开放地址法（也叫开放寻址法）：实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量。
• 再哈希法（rehash）：在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了。
• 链地址法：链地址法其实就是对Key通过哈希之后落在同一个地址上的值，后续通过一个链表将数据衔接在其后面。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的。
• 建立一个公共溢出区：这种方式是建立一个公共溢出区，当地址存在冲突时，把新的地址放在公共溢出区里。

链地址法示例【后续代码采用链地址法解决冲突】：

哈希函数的构建

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址，如 add = a(key) + b。
• 数字分析法：通过对数据的分析，发现数据中冲突较少的部分，并构造散列地址。
• 平方取中法：当无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为散列地址。这是因为：计算平方之后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的散列地址。
• 取随机数法：使用一个随机函数，取关键字的随机值作为散列地址，这种方式通常用于关键字长度不同的场合。
• 除留取余法：取关键字被某个不大于散列表的表长 n 的数 m 除后所得的余数 p 为散列地址。这种方式也可以在用过其他方法后再使用。该函数对 m 的选择很重要，一般取素数或者直接用 n。

散列表的特点

散列表有两种用法：一种是 Key 的值与 Value 的值一样，一般我们称这种情况的结构为 Set（集合）；而如果 Key 和 Value 所对应的内容不一样时，那么我们称这种情况为 Map，也就是人们俗称的键值对集合。

根据散列表的存储结构，我们可以得出散列表的以下特点。

1. 访问速度很快
   由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。

2. 需要额外的空间
   首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。

3. 无序
   散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。

4. 可能会产生碰撞
   没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样。

源代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_KEY_LEN 100
#define MAX_TABLE_SIZE 100				// 哈希表大小

typedef struct HashNode{
    char *key;
    int value;							// 哈希表元素 key + value 
    struct HashNode *nextNode;
}HashNode;


typedef struct HashTable{
    HashNode * hashNode[MAX_TABLE_SIZE];
    int currentIndex;
}HashTable;


unsigned long HashFun(const char *key)					// 哈希函数
{
    unsigned long hash = 0;
    int len = strlen(key);
    for (int i = 0; i < len; i++) {
        hash = hash * 33 + key[i];
    }
    return hash;
}
//初始化
void InitHashTable(HashTable *hashTable)
{
    memset(hashTable->hashNode, 0, sizeof(HashNode *) * MAX_TABLE_SIZE);
    hashTable->currentIndex = 0;
}

//插入key value
void Insert(HashTable *hashTable, char *key, int value)
{
    int pos = HashFun(key) % MAX_TABLE_SIZE;
    HashNode * newNode = (HashNode *)malloc(sizeof(HashNode));
    newNode->nextNode = NULL;
    newNode->key = (char *)malloc(sizeof(char) * (strlen(key) + 1));
    strcpy(newNode->key, key);
    newNode->key[strlen(key)] = '\0';
    newNode->value = value;
    HashNode *p = hashTable->hashNode[pos];
    if (p == NULL) {  //如果头结点为空，说明没有冲突
        hashTable->hashNode[pos] = newNode;
        hashTable->currentIndex++;
        return;
    }
    //头结点不为空，同时头结点的key和输入的key相同，覆盖value

    
    if (strcmp(p->key, key) == 0) {
        return;
    }

    else 
    {
        while(p->nextNode)
        {
            if (strcmp(p->nextNode->key, key) == 0) 
            {
                return;
            }
            p = p->nextNode;
        }
        
        p->nextNode = newNode;
        return ;
    }
}

int * Get(HashTable *hashTable, char *key)
{
    int pos = HashFun(key) % MAX_TABLE_SIZE;
    HashNode *p = hashTable->hashNode[pos];
    if (p == NULL) {  //如果头结点为空，说明不存在这样的key
        return NULL;
    } else {
        HashNode *q = p;
        while (q != NULL) {
            if(strcmp(q->key, key) == 0) {
                return &(q->value);
            }
            q = q->nextNode;
        }
        return NULL;
    }
}

int Drop(HashTable *hashTable, char *key)
{
    int pos = HashFun(key) % MAX_TABLE_SIZE;
    HashNode *p = hashTable->hashNode[pos];
    if (p == NULL) {  //如果头结点为空，说明不存在这样的key
        return 0;
    }
    else {
        if(strcmp(p->key, key) == 0) {  //删除的如果是头结点
            hashTable->hashNode[pos] = p->nextNode;
            free(p->key);
            free(p);
            return 1;
        }
        //删除的不是头结点的情况
        HashNode *q = p->nextNode;
        HashNode * last = p;
        while (q != NULL) {
            if(strcmp(q->key, key) == 0) {
                last->nextNode = q->nextNode;
                free(q->key);
                free(q);
                return 1;
            }
            last = q;
            q = q->nextNode;
        }
        return 0;
    }
}


void ClearHashTable(HashTable* hashTable)
{
    for(int i = 0; i < MAX_TABLE_SIZE; i++) {
        HashNode *head = hashTable->hashNode[i];
        while(head) {
            HashNode *temp = head->nextNode;
            free(head->key);
            free(head);
            head = temp;
        }
    }
}

void PrintHashTable(HashTable *hashTable)
{
    for(int i = 0; i < MAX_TABLE_SIZE; i++) {
        HashNode *head = hashTable->hashNode[i];
        if (head == NULL)
            continue;
        printf("\nindex:%d======>", i);
        printf("(%s:%d)", head->key, head->value);
        head = head->nextNode;
        while(head) {
            printf("-->(%s:%d)", head->key, head->value);
            head = head->nextNode;
        }
    }
}

int main(void)
{
    HashTable *hashTable = (HashTable *)malloc(sizeof(HashTable));
    InitHashTable(hashTable);
    Insert(hashTable,"1234", 1);
    int *data = Get(hashTable,"b");
    printf("\n====%d=====\n", *data);
    Drop(hashTable, "python");
    PrintHashTable(hashTable);
    Drop(hashTable, "b");
    Drop(hashTable, "c1");
    printf("\n");
    PrintHashTable(hashTable);
    Drop(hashTable, "world");
    printf("\n");
    PrintHashTable(hashTable);
    ClearHashTable(hashTable);

}

参考链接：http://data.biancheng.net/view/107.html