网站建设案例好么,品牌网站如何做seo,做网站先得注册域名吗,制作快递网站什么是Hash Table
散列表用的是数组支持按照下标随机访问数据的特性#xff0c;所以散列表其实就是数组的一种扩展#xff0c;由数组演化而来。可以说#xff0c;如果没有数组#xff0c;就没有散列表。
散列函数
散列函数是将我们想插入的节点散列成一个数值的函数。它…什么是Hash Table
散列表用的是数组支持按照下标随机访问数据的特性所以散列表其实就是数组的一种扩展由数组演化而来。可以说如果没有数组就没有散列表。
散列函数
散列函数是将我们想插入的节点散列成一个数值的函数。它是一个函数。我们可以把它定义成 hash(key)要想找到一个不同的 key 对应的散列值都不一样的散列函数几乎是不可能的。即便像业界著名的MD5、SHA、CRC等哈希算法也无法完全避免这种散列冲突。而且因为数组的存储空间有限也会加大散列冲突的概率。
所以我们几乎无法找到一个完美的无冲突的散列函数即便能找到付出的时间成本、计算成本也是很大的所以针对散列冲突问题我们需要通过其他途径来解决。
散列冲突
开放寻址法
开放寻址法的核心思想是如果出现了散列冲突我们就重新探测一个空闲位置将其插入。那如何重新探测新的位置呢我先讲一个比较简单的探测方法线性探测Linear Probing。当我们往散列表中插入数据时如果某个数据经过散列函数散列之后存储位置已经被占用了我们就从当前位置开始依次往后查找看是否有空闲位置直到找到为止。
链表法
链表法是一种更加常用的散列冲突解决办法相比开放寻址法它要简单很多。我们来看这个图在散列表中每个“桶bucket”或者“槽slot”会对应一条链表所有散列值相同的元素我们都放到相同槽位对应的链表中。
HashMap 底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理也免不了会出现拉链过长的情况一旦出现拉链过长则会严重影响 HashMap 的性能。
于是在 JDK1.8 版本中为了对 HashMap 做进一步优化我们引入了红黑树。而当链表长度太长默认超过 8时链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候又会将红黑树转化为链表。因为在数据量较小的情况下红黑树要维护平衡比起链表来性能上的优势并不明显。
装载因子
装载因子越大说明散列表中的元素越多空闲位置越少散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链查找的过程也会因此变得很慢。
最大装载因子默认是 0.75当 HashMap 中元素个数超过 0.75*capacitycapacity 表示散列表的容量的时候就会启动扩容每次扩容都会扩容为原来的两倍大小。
代码
这里我们给出C语言的HashTable代码我们使用的是链表法而且也没有在链表过长的时候将其转化为红黑树只是单纯的链表。
#include stdlib.h
#include stdio.h
#include stdbool.htypedef struct Node {int key;int val;struct Node *next;
} Node;typedef struct HashMap {int size;int count;struct Node **hashmap;
} HashMap;// 定义哈希函数
unsigned int hash(int n) {return (unsigned int) n;
}// 创建一个节点
Node *creatNode(int key, int val) {Node *node (Node *) malloc(sizeof(Node));node-key key;node-val val;node-next NULL;return node;
}// 创建一个hash表
HashMap *createHashMap() {HashMap *H (HashMap *) malloc(sizeof(HashMap));H-size 8;H-count 0;H-hashmap (Node **) calloc(H-size, sizeof(Node *));return H;
}// 扩容以2倍的形式扩容
static void extend(HashMap *map) {int newsize map-size * 2;Node **newhashmap (Node **) calloc(newsize, sizeof(Node *));for (int i 0; i map-size; i) {Node *node map-hashmap[i];Node *head1 (Node *) malloc(sizeof(Node));Node *head2 (Node *) malloc(sizeof(Node));Node *temp1 head1;Node *temp2 head2;while (node) {if (hash(node-key) % newsize ! i) {temp2-next node;temp2 temp2-next;} else {temp1-next node;temp1 temp1-next;}node node-next;}temp1-next NULL;temp2-next NULL;newhashmap[i] head1-next;newhashmap[i map-size] head2-next;free(head1);free(head2);}map-size newsize;free(map-hashmap);map-hashmap newhashmap;
}// 插入某个结点
bool insert(HashMap *map, int key, int val) {int hash_key hash(key) % map-size;// 要插入的哈希值未产生碰撞if (map-hashmap[hash_key] NULL) {map-count;map-hashmap[hash_key] creatNode(key, val);} else {Node *head map-hashmap[hash_key];if (head-key key) return false;while (head-next head-next-key ! key) head head-next;if (head-next NULL) {map-count;head-next creatNode(key, val);} else if (head-next-key key) return false;}// 装载因子过高就开始扩容if (map-count / map-size 0.75) extend(map);return true;
}// 寻找某个结点
bool find(HashMap *map, int key, int *v) {int hash_key hash(key) % map-size;if (map-hashmap[hash_key] NULL) {return false;} else {Node *head map-hashmap[hash_key];if (head-key key) {*v head-val;return true;}while (head-next head-next-key ! key) head head-next;if (head-next NULL) return false;if (head-next-key key) {*v head-next-val;return true;}}return false;
}// 删除某个结点
void delete(HashMap *map, int key) {int hash_key hash(key) % map-size;if (map-hashmap[hash_key] NULL) return;Node *head map-hashmap[hash_key];if (head-key key) {map-hashmap[hash_key] head-next;map-count--;free(head);return;}while (head-next head-next-key ! key) head head-next;if (head-next NULL) return;if (head-next-key key) {Node *temp head-next;head-next head-next-next;map-count--;free(temp);}return;
}int main() {HashMap *H createHashMap();for (int i 0; i 1024; i) {insert(H, i, i);}printf(H size is %d\n,H-size);printf(H count is %d\n,H-count);delete(H, 0);int v 0;if (find(H, 0, v)) printf(%d\n, v);else printf(not find \n);if (find(H, 4, v)) printf(%d\n, v);else printf(not find \n);return 0;
}
