哈希表总结-C语言版_c语言自带的hash函数

目录

1、哈希表的原理

2、自己实现的hash表--C语言版

3、C语言开源项目uthash.h 中的hash接口 使用指南

3.1 uthash.h头文件说明

3.2 常见的uthash.h接口以及使用方法

4、实践应用

参考资料：

1、哈希表的原理

哈希表的关键思想是使用哈希函数将键映射到存储桶。更确切地说，

当我们插入一个新的键时，哈希函数将决定该键应该分配到哪个桶中，并将该键存储在相应的桶中；
当我们想要搜索一个键时，哈希表将使用相同的哈希函数来查找对应的桶，并只在特定的桶中进行搜索。

哈希表常用来搜索查找需要的元素， 哈希表的查找时间复杂度通常很低， 这里没有深入研究他的复杂度如何计算。

2、自己实现的hash表--C语言版

实现hash这种数据结构， 主要考虑两点：

（1）哈希函数：能够将集合中任意可能的元素映射到一个固定范围的整数值，并将该元素存储到整数值对应的地址上。
（2）冲突处理：由于不同元素可能映射到相同的整数值，因此需要在整数值出现「冲突」时，需要进行冲突处理。总的来说，有以下几种策略解决冲突：

本文使用链表的方式存储相同hash哈希值的元素， 因此代码中有链表的常见操作， 如链表创建、插入、删除、查找。

基于链表的操作， 完成了hash表的 创建、查找、插入、删除等操作。

代码如下：

 
typedef struct _ListNode_{
    int val;
    struct _ListNode_ *next;
} stListNode;
 
typedef struct {
    stListNode *data;
} MyHashSet;
 
/** Initialize your data structure here. */
//参考官方题解-- 用链表存储每一个key对应的不同的value，也就是解决冲突
 
 
/* 先完成链表的基本操作 */
// 在头结点之后插入一个新的节点
void ListPush(stListNode *head, int key)
{
    stListNode *tmp = (stListNode *)malloc(sizeof(stListNode));
 
    tmp->val = key;
    tmp->next = head->next;
    head->next = tmp;
}
 
 
void ListDelete(stListNode *head, int key)
{
    stListNode *it = head;
    stListNode *tmp = NULL;
 
    while(it->next)
    {
        if(key == it->next->val)
        {
            tmp = it->next;
            it->next = tmp->next;
            free(tmp);
            break;
        }  
 
        it = it->next; 
    }
}
 
//查找链表中是否存在key, 存在返回1, 不存在返回0
int ListContains(stListNode *head, int x)
{
    stListNode *it = head;
 
    //这里必须是it->next开头, 不然的话就会在头一次调用时判断失误, 具体原因不清楚？？？
    while(it->next)     
    {
        if(it->next->val == x)
        {
            return 1;
        }
 
        it = it->next;
    }
 
    return 0;
}
 
//删除链表的所有节点
void listFree(stListNode *head)
{
    while(head->next)
    {
        stListNode *tmp = head->next;
        head->next = tmp->next;
        free(tmp);
    }
}
 
const int base = 769;
 
int hash(int key) 
{
    return key % base;
}
 
 
//创建一个hash表, 里面可以存储base个key键值桶
MyHashSet* myHashSetCreate(void) 
{
    MyHashSet *rethash = (MyHashSet *)malloc(sizeof(MyHashSet));
    rethash->data = (stListNode *)malloc(sizeof(stListNode) * base);
 
    for(int i=0; i<base; i++)
    {
        rethash->data[i].val = 0;
        rethash->data[i].next = NULL;
    }
 
    return rethash;  
}
 
//插入时先判断是否存在, 不存在时再插入
void myHashSetAdd(MyHashSet* obj, int key) 
{
    int h = hash(key);
 
    if( !ListContains(&(obj->data[h]), key) )
    {
        ListPush(&(obj->data[h]), key);
    }
}
 
void myHashSetRemove(MyHashSet* obj, int key) 
{
    int h = hash(key);
    ListDelete(&(obj->data[h]), key);
}
 
/** Returns true if this set contains the specified element */
bool myHashSetContains(MyHashSet* obj, int key) 
{
    //找到键值桶, 在链表中查找是否存在
    int h = hash(key);
    return ListContains (&(obj->data[h]), key );
}
 
//删除base所有桶的list链表
void myHashSetFree(MyHashSet* obj) 
{
    for(int i=0; i<base; i++)
    {
        listFree(&(obj->data[i]));
    }
    
    free(obj->data);
}
 
/**
 * Your MyHashSet struct will be instantiated and called as such:
 * MyHashSet* obj = myHashSetCreate();
 * myHashSetAdd(obj, key);
 
 * myHashSetRemove(obj, key);
 
 * bool param_3 = myHashSetContains(obj, key);
 
 * myHashSetFree(obj);
*/

有关hash集合和hash表的设计， 详见

LC706-设计哈希映射

LC705-设计哈希集合

3、C语言开源项目uthash.h 中的hash接口 使用指南

3.1 uthash.h头文件说明

       uthash.h 是C语言的开源项目，它实现了常见的hash操作函数，例如查找、插入、删除等。该套开源代码采用宏的方式实现hash函数的相关功能，支持C语言的任意数据结构最为key值，甚至可以采用多个值作为key，无论是自定义的struct还是基本数据类型，需要注意的是不同类型的key其操作接口方式略有不通。     

       使用uthash代码时只需要包含头文件"uthash.h"即可。由于该代码采用宏的方式实现，所有的实现代码都在uthash.h文件中，因此只需要在自己的代码中包含该头文件即可。可以通过下面两种方式获取源代码：

• 通过官方下载链接：      https://github.com/troydhanson/uthash

3.2 常见的uthash.h接口以及使用方法

能够实现哪些功能？

typedef struct my_struct 
{  
    int  key;          /* key */  
    int  val;  
    UT_hash_handle hh;               
}stHashTable; 

void find(int ikey)
{
    struct my_struct *s;  
    HASH_FIND_INT(g_users, &ikey, s );  
    return s;  
} 

void delete_user(int ikey) 
{  
    struct my_struct *s = NULL;  
    HASH_FIND_INT(g_users, &ikey, s);  
    if (s!=NULL) {  
      HASH_DEL(g_users, s);   
      free(s);              
    }  
}  

void delete_all() 
{  
    struct my_struct *current_user, *tmp;  
    HASH_ITER(hh, users, current_user, tmp) 
    {  
        HASH_DEL(g_users,current_user);    
        free(current_user);              
    }  
}  

typedef struct  _stHashTable_
{
    struct ListNode *key;
    UT_hash_handle hh;
}stHashTable;

typedef struct _HashSet_{
    char str[MAX_SIZE];
    ... ...
    UT_hash_handle hh;
}stHashSet;

unsigned int num_users;  
num_users = HASH_COUNT(g_users);

4、实践应用

看一道LeetCode上的典型题目， 求两个数组的交集。  链接  LC349. 两个数组的交集

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 
 //哈希集合法----这次写的封装接口， 把全局的hash表当做入参了
typedef struct _HashSet_{
    int key;
    UT_hash_handle hh;
}stHashSet;
 
 
stHashSet *find(stHashSet** hashtable, int ikey) {
    stHashSet* tmp;
    HASH_FIND_INT(*hashtable, &ikey, tmp);
    return tmp;
}
 
void insert(stHashSet** hashtable, int ikey) 
{
    stHashSet* tmp = find(hashtable, ikey);
    if (tmp != NULL) return;
    tmp = malloc(sizeof(stHashSet));
    tmp->key = ikey;
    HASH_ADD_INT(*hashtable, key, tmp);
}
 
int *func(stHashSet** hashSet1, stHashSet** hashSet2, int* returnSize)
{
    if(HASH_COUNT(*hashSet1) > HASH_COUNT(*hashSet2))
    {
        func(hashSet2, hashSet1, returnSize);
    }
 
    //储存结果的地方申请内存
    int *retArr = (int *)malloc(sizeof(int)*HASH_COUNT(*hashSet2));
    *returnSize = 0;
 
    //遍历元素少的那个hash表, 在元素多的表中查找是否存在相同的key
    stHashSet *tmp, *it;
    HASH_ITER(hh, *hashSet1, tmp, it)
    {
        if( find(hashSet2, tmp->key) )
        {
            retArr[*returnSize] = tmp->key;
            (*returnSize)++;
        }
    }
 
    return retArr;
}
 
 
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
    int i = 0;
    stHashSet *hSet1 = NULL;
    stHashSet *hSet2 = NULL;
 
    /*插入元素、构造两个数组的hash集合*/
    for(i=0; i<nums1Size; i++)
    {
        insert(&hSet1, nums1[i]);
    }
 
    for(i=0; i<nums2Size; i++)
    {
        insert(&hSet2, nums2[i]);
    }
 
    return func(&hSet1, &hSet2, returnSize);
 
}

参考资料：

LeetCode链接：LeetCode哈希表book
c开源hash项目 uthash的用法总结