网站建设厦门,wordpress打造论坛,龙岗微信网站制作,微信引流推广怎么找平台一、哈希表基本概念 哈希表#xff08;也称为散列表#xff09;是根据键而直接访问在内存存储位置的数据结构#xff0c;也就是说实际上是经过哈希函数进行映射#xff0c;映射道表中一个位置来访问记录#xff0c;这个存放记录的数组称为散列表。
哈希函数#xff1a;就…一、哈希表基本概念 哈希表也称为散列表是根据键而直接访问在内存存储位置的数据结构也就是说实际上是经过哈希函数进行映射映射道表中一个位置来访问记录这个存放记录的数组称为散列表。
哈希函数就是将要存储的数据经过运算映射到我们要存储的位置
二、哈希的本质
本质是一给数组将通过哈希函数映射将一定的数据放在指定的位置再通过映射能够很快找到数据。
三、哈希冲突哈希矛盾 就是经过运算不同的数据但是对应相同的位置而前面这个地方已经将数据存储要尽可能避免冲突
四、解决哈希冲突的办法
4.1、开放寻址法 简单点来说对于冲突元素找到空位置放进去即可
开放寻址法Open Addressing是一种解决哈希冲突的方法它在哈希表中直接解决冲突即当两个或多个键的哈希值相同时它们会尝试在哈希表中找到下一个空闲位置来存储数据。开放寻址法的主要思想是所有的元素都存储在哈希表中而不是像链地址法那样在表外链接。
4.2、链地址法
链地址法Separate Chaining是另一种解决哈希冲突的方法。在这种方法中哈希表的每个槽slot或桶bucket都关联一个链表我们把具有相同属性的元素进行连接最后只需要我们进行查找的时候只需要进行哈希映射找到数组的地址之后去遍历里面的链表找到对应的元素。用于存储具有相同哈希值的所有元素。
工作原理 1. **哈希函数**首先使用哈希函数将键映射到哈希表的一个位置。 2. **冲突处理**如果两个键映射到同一个位置即发生冲突它们会被存储在同一个链表中。 3. **插入操作**插入新元素时首先计算其哈希值然后在对应的链表中添加新元素。 4. **查找操作**查找元素时首先计算其哈希值然后在对应的链表中遍历查找。 5. **删除操作**删除元素时首先找到对应的链表然后在链表中找到并删除元素。
### 优点 - **简单易实现**链地址法的实现相对简单容易理解。 - **动态扩容**可以通过调整链表的大小来动态地处理负载因子的变化从而保持操作的效率。
### 缺点 - **额外空间**每个槽需要额外的空间来存储链表的指针这可能会增加内存的使用。 - **性能依赖于负载因子**当哈希表的负载因子即表中元素数量与槽数量的比率较高时链表可能会变得较长导致查找效率下降。
### 性能优化 - **动态扩容**随着元素的增加可以动态地增加哈希表的大小以保持负载因子在一个合理的范围内。 - **负载因子控制**通过控制负载因子可以平衡内存使用和查找效率。
链地址法是哈希表中常用的冲突解决策略之一适用于键值对的存储和快速查找。
五、哈希操作
1、哈希表的创建
int hash_function(char key)
{if (key a key z){return key-a;}else if (key A key Z){return key-A;}else{return HASH_SIZE-1;}
}
2、哈希表的插入
int insert_hashtable(HSDataTYpe data)
{int addr hash_function(data.name[0]);HSNode_t *pnode malloc(sizeof(HSNode_t));if(NULL pnode){perror(fail malloc);return -1;}pnode-data data;pnode-pnext NULL;pnode-pnext hashtable[addr];hashtable[addr] pnode;return 0;
}vv
3、哈希表的遍历
void each_for_hsnode()
{for(int i 0;i HASH_SIZE;i){HSNode_t *pnode hashtable[i];while(pnode ! NULL){printf(name %s\n,pnode-data.name);printf(telephone %s\n,pnode-data.tel);pnode pnode-pnext;}}printf(\n);
}
4、哈希表的查找
void find_hsnode(HSDataTYpe data)
{int addr hash_function(data.name[0]);HSNode_t *pnode hashtable[addr];while(pnode ! NULL){if(strcmp(pnode-data.name,data.name) 0){printf(name %s\n,pnode-data.name);printf(telephone %s\n,pnode-data.tel);break;}pnode pnode-pnext;}printf(\n);
}
5、哈希表的销毁
void destory_hsnode()
{for(int i 0;i HASH_SIZE;i){HSNode_t *p NULL;while(hashtable[i]! NULL){p hashtable[i];hashtable[i] p-pnext;free(p);}}
}
