前言

哈希桶是哈希表中用于存储数据的基本单元，也称为哈希槽或存储桶。

哈希桶（Hash Bucket）** 是哈希表数据结构中的一个概念。、哈希表通过哈希函数将输入数据映射到一个存储位置，而哈希桶就是这些存储位置中的一个单元。哈希桶用于存放哈希表中的元素，当不同的元素经过哈希函数映射到同一个桶时，通常通过链表或其他结构来存储这些元素。这种情况称为 哈希冲突。

哈希桶的工作机制

哈希函数的作用：哈希函数根据输入元素计算出一个整数值，称为哈希值，然后根据哈希值来决定元素存储在哪个桶中。

假设哈希表的桶数为 num_buckets，元素 key 的哈希值为 hash(key)，则该元素将被存储在 hash(key) % num_buckets 这个桶中。

哈希冲突：由于哈希表的容量有限，而插入的元素可能很多，因此会有多个元素映射到同一个桶。这就是哈希冲突。

冲突解决方式：当发生哈希冲突时，哈希桶中的元素通常会存储在某种结构中。常见的冲突解决方式包括：

拉链法：在每个哈希桶中维护一个链表，当多个元素映射到同一个桶时，这些元素会依次插入链表中。开放寻址法：当某个桶已经有元素时，寻找下一个空的桶来存储冲突的元素。参考

哈希桶示例

例如，一个哈希表有 5 个桶（编号为 0-4），通过简单的哈希函数 hash(key) = key % 5 来决定桶的位置。

<code>//假设插入的元素为：12, 7, 5, 10, 15, 9

hash(12) = 12 % 5 = 2

hash(7) = 7 % 5 = 2

hash(5) = 5 % 5 = 0

hash(10) = 10 % 5 = 0

hash(15) = 15 % 5 = 0

hash(9) = 9 % 5 = 4

最终得到的哈希桶分布如下：

桶 0：5 -> 10 -> 15桶 1：（空）桶 2：12 -> 7桶 3：（空）桶 4：9

其中：

桶 0 通过拉链法存储了 5、10 和 15，使用链表处理冲突。桶 2 同样存储了 12 和 7。

哈希桶的实现

存储结构

类似于链表，在顺序表中存储一个一个节点。’

template<class T>

struct defaultHashfunc

{

size_t operator()(const T& data)

{

return (size_t)data;

}

};

table：使用 std::vector 存储多个链表，每个链表代表一个桶，链表中的元素是映射到这个桶的所有元素。记录_n进行负载因子的储存

template<class K,class T,class KeyofT,class HashFunc = defaultHashfunc<K>>

class HashTable

{

public:

...

private:

vector<Node*> _table;

size_t _n = 0;

};

哈希函数

在函数的内容的不确定的时候进行返回。针对string字符串的直接进行特模板化。针对26字母有不同的组合，要进行字符串的哈希化处理，目的是针对哈希冲突 （本次采用 BKDR算法）参考：字符串哈希算法

template<class T>

struct defaultHashfunc

{

size_t operator()(const T& data)

{

return (size_t)data;

}

};

//string特化

template<>

struct defaultHashfunc<string>

{

size_t operator()(const string& str)

{

size_t hash = 0;

for (auto& ch : str)

{

hash *= 131;

hash += ch;

}

return hash;

}

};

插入操作

哈希桶插入步骤：

计算哈希值： 使用哈希函数 hash(key) 将键值（key）映射为一个整数，称为 哈希值。这个哈希值决定了 key 应该被存储在哪个桶中。

定位桶：根据哈希值和哈希表的大小（桶的数量），确定目标桶的位置。常用的方式是：bucket = hash(key) % num_buckets，其中 num_buckets 是哈希表的桶数量。

检查冲突：定位到目标桶后，检查桶中是否已经存在与 key 相同的元素。如果已经存在，则插入操作可以直接结束（因为集合不允许重复元素），否则继续进行。

插入元素： 如果目标桶中不存在相同的元素，直接将元素插入到该桶中。对于拉链法，目标桶通常使用链表（或类似结构）存储多个元素，因此新元素会被插入到链表末尾。

哈希桶的扩容： 如果大小不够，一个桶的元素过于多，就需要进行扩容，创建一个新表进行插入操作。

bool insert(const T& data)

{

HashFunc hf;

bool it = Find(kot(data));

if (it)

{

return false;

}

if (_n == _table.size())

{

size_t newsize = _table.size() * 2;

vector<Node*> newtable;

newtable.resize(newsize,nullptr);

for (int i = 0; i < _table.size() ;i++)

{

HashFunc hf;

size_t hashi = 0;

Node* cur = _table[i];

while (cur)

{

Node* next = cur->_next;

hashi = hf(cur->_data) % newtable.size();

cur->_next = newtable[hashi];

newtable[hashi] = cur;

cur = next;

}

_table[i] = nullptr;

}

_table.swap(newtable);

}

size_t hashi = hf(data) % _table.size();

Node* newnode = new Node(data);

newnode->_next = _table[hashi];

_table[hashi] = newnode;

++_n;

return true;

}

插入效率：

时间复杂度：哈希桶的插入操作通常情况下的时间复杂度为 O(1)，因为哈希函数能够在常数时间内定位到桶的位置。然而，最坏情况下（所有元素都被映射到同一个桶中），时间复杂度退化为 O(n)，其中 n 是桶中元素的数量。空间复杂度：哈希表的空间复杂度与桶的数量和元素数量成正比，通常为 O(n)。

删除操作

哈希桶删除步骤：

计算哈希值： 使用哈希函数 hash(key) 计算出元素的哈希值，找到元素应该所在的桶。

定位桶： 根据哈希值和哈希表的桶数量，确定目标桶的位置，通常通过：bucket = hash(key) % num_buckets 来找到对应的桶。

遍历桶中的元素： 在找到的桶中，遍历桶中存储的所有元素（通常是通过链表存储），寻找需要删除的元素。

删除元素： 一旦找到目标元素，将其从桶中删除（对于拉链法，通常是从链表中删除元素）。如果该元素不存在，则无需做任何操作。

bool Erase(const K& key)

{

HashFunc hf;

size_t hashi = hf(key) % _table.szie();

Node* cur = _table[hashi];

Node* prev = nullptr;

while (cur)

{

if (cur->_data == key)

{

if (prev == nullptr)

{

_table[hashi] = cur->_next;

}

else

{

prev->_next = cur->_next;

}

delete cur;

--_n;

return true;

}

prev = cur;

cur = cur->_next;

}

return false;

}

时间复杂度分析：

最佳情况：每个桶中只有一个元素或哈希函数将元素均匀分布到桶中，删除操作的时间复杂度为 O(1)，因为只需找到桶后直接删除即可。

最坏情况：所有元素都被映射到同一个桶中，导致链表长度等于元素数量。在这种情况下，删除操作的时间复杂度为 O(n)，其中 n 是链表中的元素数量。

平均情况：如果哈希函数分布较好，链表的长度较短，删除操作的平均时间复杂度为 O(1)

查找操作

哈希桶查找步骤：

计算哈希值：使用哈希函数 hash(key) 计算出需要查找的元素的哈希值，找到元素应该存储的桶。定位桶：根据哈希值，计算出目标桶的索引。常用的方式是：bucket = hash(key) % num_buckets，其中 num_buckets 是哈希表的桶数量。在桶内查找： 如果该桶为空，直接返回元素不存在。如果桶内有元素，遍历桶中的链表或数组，逐个检查每个元素是否与要查找的键值相等。返回结果：

如果找到与目标键相等的元素，则返回成功查找的结果。如果遍历完整个桶（链表或数组）后，未找到目标元素，则返回查找失败。

bool Find(const K& key)

{

HashFunc hf;

size_t hashi = hf(key) % _table.size();

Node* cur = _table[hashi];

while (cur)

{

if (kot(cur->_data) == key)

{

return true;

}

cur = cur->_next;

}

return false;

}