哈希表-数据结构
一、哈希表基本概念
哈希表（也称为散列表）是根据键而直接访问在内存存储位置的数据结构，也就是说实际上是经过哈希函数进行映射，映射道表中一个位置来访问记录，这个存放记录的数组称为散列表。
哈希函数：就是将要存储的数据经过运算，映射到我们要存储的位置
二、哈希的本质
本质是一给数组，将通过哈希函数映射，将一定的数据放在指定的位置，再通过映射能够很快找到数据。
三、哈希冲突（哈希矛盾）
就是经过运算，不同的数据，但是，对应相同的位置，而前面这个地方已经将数据存储，要尽可能避免冲突
四、解决哈希冲突的办法
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;
}vv3、哈希表的遍历
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);}}
}