什么是哈希表？
哈希表（Hash Table）是一种数据结构，它使用哈希函数将键（key）映射到桶（bucket）或槽（slot）中，可以直接通过相应的键值直接对数据进行访问，高效的插入，删除，查找
哈希表的组成部分和特性
-
哈希函数：哈希函数接受一个键作为输入，并返回一个索引值（通常是一个整数），该索引值用于确定键在哈希表中的位置。一个好的哈希函数应该能够将键均匀地分布到哈希表的各个桶中，以减少冲突（collision）的可能性。
-
桶或槽：哈希表的存储空间被划分为若干个桶或槽，每个桶可以存储一个或多个键值对。桶的数量通常小于哈希表中可能存在的键的数量，因此多个键可能会映射到同一个桶中，这称为冲突。
-
冲突解决：当两个或多个键映射到同一个桶时（哈希冲突），需要使用冲突解决策略。常见的冲突解决策略包括：
- 链地址法（链表法）：在发生冲突的桶中维护一个链表，将具有相同哈希值的键值对链接在一起。
- 开放地址法：当发生冲突时，通过某种探测方法（如线性探测、二次探测、双散列等）在哈希表中查找下一个可用的空槽。
- 再哈希法：当发生冲突时，使用另一个哈希函数重新计算键的哈希值，直到找到一个空槽为止。
4. 动态调整：为了保持哈希表的性能，当哈希表中的元素数量过多或过少时，可能需要动态地调整哈希表的大小。这通常涉及重新计算所有键的哈希值，并将它们重新分配到新的桶中。
5. 性能：哈希表通常具有接近O(1)的平均时间复杂度，用于插入、删除和查找操作。然而，在最坏情况下（例如，当所有的键都映射到同一个桶中时），哈希表的时间复杂度可能会退化为O(n)。
声明：以下的都是我看侯捷的<<深度剖析stl>>总结的，可能最新的stl实现不是这样的，但是也是对的新的对旧的的一些完善，但是大体是正确的
下面讲解哈希表，哈希碰撞是由链表来解决
teplate<class value>
struct _hashtable_node //哈希表bukets的链表节点
{
_hashtable_node *next;
value val;
}
template<class value,class key,class hashfuc,class extractkey,class equalkey>
class hashtable
{
private:
//三个仿函数
hashfcn hash; //哈希分散的仿函数 插入元素时(刚创建并无key)根据数据类型(基类和对象等)返回key
equalkey equals; //比较key大小，以便实现对key的排序
extractkey get_key; //得到一个元素的key(这个元素已存在)
_hashtable_node<value> node; //哈希表bukets的链表节点
vector<node*,alloc> bukets; //哈希表bukets
size_t num_size; //哈希表所含的元素个数
}关于hashtable的学习我们可以从六个方面入手
容器，迭代器，算法，仿函数，适配器，分配器
我先对上述代码简要介绍，value可以是键值对或者就只是值,key则是键，hashfuc通过值返回一个key也就是编号，extractkey则是当你存储的是键值对时如何得到元素得key比如pair<key,value>返回first（标准库基本上没了）,equalkey比较两个key是否相同，buckets(篮子)存放链表的篮子，num_size元素个数
容器：
从上面我们不难看出真正存储数据的是node（链表节点）可以看到有一个vetor<node*,alloc>,其中存储的就是链表，为什么用vector因为能扩充，元素过多时，或者单个链表过长影响性能我们能通过添加链表来添加元素
仿函数：
从上图可以看到每个bucket都有一个编号每个编号对应着一条链表
如何获得key(键)的呢?
template<class key> struct hash(){}
//偏特化
template<> struct hash(int) //基础类型直接返回 int,unsigned int,char,const int
{
size_t operater(int x){return x};
}
template<> struct hash(char*) //字符串类型 通过一个公式计算每个字符尽可能得到不相同的数据
{
size_t operator(char* s)
{
unsiged long h;
/*****begin******/ 遍历字符串得到一个不同字符串能得到不同值
/******end******/
return (size_t)h;
}
}
//当值是一个复杂类型，对象或者结构体你就得自己提供获取键的仿函数
当我们拿到折射值还不行因为折射值可能很大,我们的编号有限所以我们还要将上面的到的折射值%buckets.size()
hash()%bucket.size() //得到真正的键值 将这些元素散落在这个vector的链表，即使折射值不同仍然会出现相同的key我们则用链表连起来
为什么要判断键是否相同
对于具有相同哈希值但不相等的键，哈希表需要在插入、查找或删除操作时进行额外的等价检查（equality check）。这是因为在哈希表中，仅仅依赖哈希值来定位键是不够的，因为可能存在多个键具有相同的哈希值。因此，当哈希表在桶中找到了具有相同哈希值的键时，还需要通过等价检查来确定这些键是否真的相等。如果不相等，则需要继续搜索或采取其他策略来处理这个冲突
其余仿函数大家可以自己去深入了解
迭代器
因为内容太多我就不讲述太多
我们知道迭代器需要能够遍历到整个哈希表
我们已经知道它的容器是vector<node*>存放的链表的节点所以有以下东西
template<class value,class key,class hashfuc,class extractkey,class equalkey>
class _hashtable_iterator
{
node * p; //当前链表节点
hash_table *ht //当前篮子的指针
_hashtable_iterator& operater*(){return this->p->val;} 对*,->等运算符重载
}需要注意的是我们++或者--都要边界判定，为什么需要篮子指针，是因为每次++链表到尾了需要到下一个篮子， 每次--到头了需要到前一个篮子，以及+5，6,等等，
进行迭代器的减法时我们需要判断中间有几个元素也要有相应的算法逻辑
算法
插入算法，删除算法，查找算法，都是基于迭代器和容器上实现，算法是桥梁，这里我们给出插入的简单介绍
void HashTable::insert(KeyType key, ValueType value) {
// 计算哈希值
int hashIndex = hash(key) % capacity; // 使用取模运算来确定桶的编号
// 遍历链表以查找是否存在具有相同键的节点
node* currentNode = buckets[hashIndex];
while (currentNode != nullptr) {
if (currentNode->key == key) {
// 如果键已经存在，可以选择更新值或执行其他操作（如抛出异常）
currentNode->value = value;
return; // 退出函数，因为键已经存在
}
currentNode = currentNode->next; // 移动到链表中的下一个节点
}
// 如果键不存在于链表中，则创建一个新节点并将其添加到链表的开头
node* newNode = new node(key, value); // 创建新节点
newNode->next = buckets[hashIndex]; // 将新节点设置为当前桶的头节点
buckets[hashIndex] = newNode; // 更新桶的头节点指针
// 增加哈希表中元素的数量
size++;
// 如果哈希表变得过满，考虑重新哈希（重新分配和重新组织元素）
if (size > capacity * LOAD_FACTOR) { // LOAD_FACTOR是一个预定义的阈值，如0.75
rehash(); // 重新哈希函数，会重新分配buckets数组并重新组织元素
}
}分配器：
分配内存控制整个hashtable内存等资源的分配
适配器:
hash_map,hash_set 以及c++11的unordered_set,unordered_map
标签：map,set,hash,哈希,链表,key,节点,size From： https://blog.csdn.net/weixin_72492465/article/details/139638171