Leetcode学习：哈希表

哈希表学习过程 三、哈希冲突 四、哈希表题目 五、学习地址参考资料剩余练习题目

一、哈希表定义

哈希表（Hash Table）：也叫做散列表。是根据关键码值（Key Value）直接进行访问的数据结构。

哈希表通过「键 key 」和「映射函数 Hash(key) 」计算出对应的「值 value」，把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做「哈希函数（散列函数）」，存放记录的数组叫做「哈希表（散列表）」。

在上图例子中，我们使用 Hash(key) = key // 1000 作为哈希函数。// 符号代表整除。我们以这个例子来说明一下哈希表的插入和查找策略。

二、哈希函数

哈希函数（Hash ）：将哈希表中元素的关键键值映射为元素存储位置的函数。

2.1 哈希函数满足条件

在哈希表的实际应用中，关键字的类型除了数字类，还有可能是字符串类型、浮点数类型、大整数类型，甚至还有可能是几种类型的组合。一般我们会将各种类型的关键字先转换为整数类型，再通过哈希函数，将其映射到哈希表中。

2.2 哈希函数运用方法 2.2.1 直接定址法

2.2.2 除留余数法

2.2.3 平方取中法

2.2.4 基数转换法

三、哈希冲突

哈希冲突（Hash ）：不同的关键字通过同一个哈希函数可能得到同一哈希地址，即 key1 ≠ key2，而

Hash(key1) = Hash(key2)，这种现象称为哈希冲突。

3.1 哈希冲突是怎么发生的？

理想状态下，我们的哈希函数是完美的一对一映射，即一个关键字（key）对应一个值（value），不需要处理冲突。但是一般情况下，不同的关键字 key 可能对应了同一个值 value，这就发生了哈希冲突。

3.2 解决哈希冲突的办法【哈希表核心】

设计再好的哈希函数也无法完全避免哈希冲突。所以就需要通过一定的方法来解决哈希冲突问题。常用的哈希冲突解决方法主要是两类：「开放地址法（Open ）」 和 「链地址法（）」。

3.2.1 开放地址法

**开放地址法（Open ）：**指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时，处理冲突时需要尝试另外的单元，直到找到空的单元为止。

当发生冲突时，开放地址法按照下面的方法求得后继哈希地址：H(i) = (Hash(key) + F(i)) % m，i = 1, 2, 3, …, n (n ≤ m - 1)。

举个例子说说明一下如何用以上三种冲突解决方法处理冲突，并得到新地址 H(i)：

例如，在长度为 11 的哈希表中已经填有关键字分别为 28、49、18 的记录（哈希函数为 Hash(key) = key %

11）。现在将插入关键字为 38 的新纪录。根据哈希函数得到的哈希地址为 5，产生冲突。接下来分别使用这三种冲突解决方法处理冲突。

3.2.2 链地址法

链地址法（）：将具有相同哈希地址的元素（或记录）存储在同一个线性链表中。

我们假设哈希函数产生的哈希地址区间为 [0, m - 1]，哈希表的表长为 m。则可以将哈希表定义为一个有 m 个头节点组成的链表指针数组 T。

与开放地址法相比的优势：

采用链地址法处理冲突要多占用一些存储空间（主要是链节点占用空间）。但它可以减少在进行插入和查找具有相同哈希地址的关键字的操作过程中的平均查找长度。这是因为在链地址法中，待比较的关键字都是具有相同哈希地址的元素，而在开放地址法中，待比较的关键字不仅包含具有相同哈希地址的元素，而且还包含哈希地址不相同的元素。

四、哈希表题目 1.0217. 存在重复元素

存在重复元素力扣链接

这里我就不复制题目了；

因为这里我的学习内容是哈希表，那代码逻辑自然而生

struct hashTable {//定义了一个结构体 hashTableint key;      //整数类型的键 keyUT_hash_handle hh;//UT_hash_handle 结构体
};bool containsDuplicate(int* nums, int numsSize) {struct hashTable* set = NULL;//初始化定义了一个名为 set 的指针，指向哈希表for (int i = 0; i < numsSize; i++) {//遍历整数数组 numsstruct hashTable* tmp;HASH_FIND_INT(set, nums + i, tmp);//使用 HASH_FIND_INT 宏在哈希表中查找是否存在相同的键（即当前数组元素的值）/**如果 tmp 为 NULL，表示当前元素是第一次出现，动态分配内存创建一个新的哈希表节点，并将当前数组元素的值作为键存储到哈希表中*/if (tmp == NULL) {    //tmp 用于存储查找结果tmp = malloc(sizeof(struct hashTable));tmp->key = nums[i];HASH_ADD_INT(set, key, tmp);} else {//如果 tmp 不为 NULL，表示当前元素已经在哈希表中存在，说明存在重复元素，函数返回 truereturn true;}}return false;//如果整个数组都遍历完毕，都没有找到重复元素，则函数返回 false
}

在哈希表中查找元素的时间复杂度是 O(1)，整体算法的平均时间复杂度是 O(n)

这是我看见的有趣大佬干了个手写哈希表

#include 
#include #ifndef MY_TINY_STL_HASHMAP_C_H
#define MY_TINY_STL_HASHMAP_C_H
#define DEFAULT_CAPACITY 32 //初始的表长
#define DEFAULT_FACTOR 0.75f //初始的装载因子
/*类型定义 和 装载因子初始化*/
typedef int key_t;
typedef int val_t;
static const float factor = DEFAULT_FACTOR; //装载因子
typedef struct node {//每个哈希表的键值对key_t key;val_t val;struct node *next;
} Node;
typedef struct {size_t size;       //记录已经存下的键值对数目size_t capacity;   //记录表长Node **buckets; //桶子：用于记录的哈希桶，桶子中每个元素是Node*
} HashMap;/*函数的声明*/
HashMap *init();void Put(HashMap *, key_t, val_t);void insert(HashMap *, Node *);                           //直接把已经分配好的内存插入哈希表
static void putVal(HashMap*,key_t, val_t); //这个是put的委托函数,用于直接更新桶子，并更新HashMap的size
static inline size_t getHashcode(key_t);              //得到key对应的扰动函数
static inline size_t strHashcode(char *);               //得到字符串的哈希值，用的java的31为底的算法，这个哈希值再经过扰动函数
static inline size_t getIndex(key_t, size_t);           //通过桶的大小和key映射位置，算是包含了关键的哈希函数：由于C不支持泛型也就无法针对不同类型作出不同的哈希了，我这里默认key为int
static void resize(HashMap *);                          //如果插入的元素过多，*2进行重新哈希分配
static void rehash(HashMap *, Node **);                   //重新设置长度则需要重新哈希一些key的位置
val_t *Get(HashMap *, key_t);                            //得到key对应的val
static void del_nodes(Node *);                          //把单个链表销毁
void destroy(HashMap *);                                //把哈希表的内存销毁/*函数实现*/
HashMap *init() {    //初始化得到一个哈希表HashMap *ret = (HashMap *) malloc(sizeof(HashMap));if(ret==NULL)return NULL;ret->size = 0;ret->capacity = DEFAULT_CAPACITY;ret->buckets = (Node **) calloc(DEFAULT_CAPACITY, sizeof(Node *));if(ret->buckets==NULL)return NULL;return ret;
}void insert(HashMap *map, Node *node) {assert(map != NULL && node != NULL);size_t index = getIndex(node->key, map->capacity);node->next = map->buckets[index];map->buckets[index] = node;
}void Put(HashMap *map, key_t key, val_t val) {assert(map != NULL);//判断是否需要扩容if (map->size >=factor * map->capacity) resize(map);putVal(map, key,val);
}static inline size_t strHashcode(char *key) {size_t hash = 0;size_t index = 0;while (key[index] != '\0') {hash = hash * 31 + key[index++];}return hash;
}static inline size_t getHashcode(key_t key) {return key ^ (key >> 16);//这是32位数的扰动函数
}static inline size_t getIndex(key_t key, size_t bucket_size) {//由于bucketsize一定是2的次方，所以size-1和key相与得到的就是下标return getHashcode(key) & (bucket_size - 1);
}static void putVal(HashMap* map,key_t key,val_t val) {assert(map!=NULL);//获取位置size_t index = getIndex(key, map->capacity);Node *x = map->buckets[index];if (x == NULL) {//插入位置为空x = (Node *) malloc(sizeof(Node));x->val = val;x->key = key;x->next = NULL;map->buckets[index] = x;map->size++;    //哈希表内的元素增加return;}//插入位置不为空，说明发生冲突，使用链地址法，遍历链表while (x) {//如果key相同就覆盖if (x->key == key) {x->val = val;return;}x = x->next;}//当前的key不在链表中，则插入链表头部x = (Node *) malloc(sizeof(Node));x->key = key;x->val = val;x->next = map->buckets[index];map->buckets[index] = x;map->size++; //哈希表内元素增加
}static void resize(HashMap *map) {map->capacity <<= 1;            //扩大两倍容量，相当于左移一位Node **tmp = map->buckets;     //存下之前的内存地址map->buckets = (Node **) calloc(map->capacity, sizeof(Node *)); //重新分配rehash(map, tmp);//重新哈希处理free(tmp);                                          //释放之前的内存
}static void rehash(HashMap *map, Node **preTable) {//采取java1.7的方式进行rehash也就是最简单直接的直接重新哈希插入size_t preCap = map->capacity >>1,i; //改变前的有效区域Node* preNode,*curNode;for (i = 0; i < preCap; i++) {if (preTable[i] != NULL) {//判断对应的key是否需要重新换位置,如果对最新掩码多出来的1敏感则需要rehashcurNode = preTable[i];while (curNode) {preNode = curNode;curNode = curNode->next;insert(map, preNode);}}}
}val_t *Get(HashMap *map, key_t key) {//前面的写好后，那么get就很好写了int index = getIndex(key, map->capacity);Node *node = map->buckets[index];while (node != NULL) {if (node->key == key) {return &(node->val);}node = node->next;}return NULL;//没找到返回NULL指针
}static void del_nodes(Node *head) {//删除单条链表Node *pre;Node *cur = head;while (cur != NULL) {pre = cur;cur = cur->next;free(pre);}
}void destroy(HashMap *map) {//销毁整个哈希表size_t sz = map->capacity;Node **tmp = map->buckets;for (size_t i = 0; i < sz; i++) {if (tmp[i] != NULL)del_nodes(tmp[i]);}free(tmp);free(map);
}#endif //MY_TINY_STL_HASHMAP_C_Hbool containsDuplicate(int* nums, int numsSize) {HashMap* set = init();for (int i = 0; i < numsSize; i++) {if(Get(set,nums[i])!=NULL)return true;Put(set,nums[i],0);}return false;
}作者：加油！！！欧里给
链接：https://leetcode.cn/problems/contains-duplicate/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.0219. 存在重复元素 II

当我看到题目的时候，以为是给我一个数组，以及一个数字，让我判断数组中会不会有数字和我自己给的数字相同

随后仔细去读题，发现有个“存在两个不同的索引 i 和 j 满足 nums[i] == nums[j] 且 abs(i - j)