网站下方一般放什么,口碑好的句容网站建设,做的网站被注销,网站名称需要用注册吗文章目录 引言一、哈希表与哈希函数1、哈希表的基本原理2、哈希函数的作用与特点3、哈希冲突的处理方法 二、哈希桶及其迭代器1、 哈希桶a.定义哈希桶结构b.哈希函数c.哈希桶的插入、查找、删除 2、 哈希桶的迭代器a.类型定义与成员变量b.构造函数c.解引用与比较操作d.递增操作… 文章目录 引言一、哈希表与哈希函数1、哈希表的基本原理2、哈希函数的作用与特点3、哈希冲突的处理方法 二、哈希桶及其迭代器1、 哈希桶a.定义哈希桶结构b.哈希函数c.哈希桶的插入、查找、删除 2、 哈希桶的迭代器a.类型定义与成员变量b.构造函数c.解引用与比较操作d.递增操作 三、总结 引言
哈希表Hash Table是一种非常重要的数据结构它基于哈希函数将键Key映射到值Value上从而实现对数据的快速存储、查找和删除。在哈希表中数据并不是按顺序存储的而是根据哈希函数计算出的键的哈希值确定数据在表中的位置。由于哈希函数的设计使得键与位置之间存在直接对应关系因此哈希表在查找、插入和删除操作上的平均时间复杂度可以达到O(1)即常数时间复杂度。这使得哈希表在处理大规模数据时具有极高的效率。
在C标准库中unordered_map和unordered_set是两种基于哈希表实现的关联容器。它们利用哈希表的优势提供了快速的数据访问能力。unordered_map存储的是键值对Key-Value Pair允许我们根据键快速查找、插入或删除对应的值。而unordered_set则只存储键用于快速判断某个元素是否存在于集合中。我们将在下一篇文章根据本文内容介绍unordered_map和unordered_set。
unordered系列的关联式容器之所以效率比较高是因为其底层使用了哈希结构。哈希是一种查找的方法不是数据结构。 一、哈希表与哈希函数
哈希表与哈希函数是计算机科学中非常重要的概念它们在数据结构的构建和算法优化中发挥着关键作用。以下是关于哈希表的基本原理、哈希函数的作用与特点以及哈希冲突处理方法的详细介绍。
1、哈希表的基本原理
哈希表又称为散列表是一种根据关键码值key-value直接进行访问的数据结构。它通过一个哈希函数将键映射到表中的位置以便快速查找、插入和删除元素。哈希表的主要优势在于其高效的查找性能理想情况下其查找时间复杂度可以达到O(1)即常数时间复杂度。
在哈希表中每个键都唯一对应一个哈希值这个哈希值就是该键在表中的位置。当需要插入一个新元素时通过哈希函数计算键的哈希值然后将元素存储在对应的位置。当需要查找一个元素时同样通过哈希函数计算键的哈希值然后直接定位到表中的位置进行查找。
2、哈希函数的作用与特点
哈希函数是哈希表的核心它负责将输入的键转换为哈希值。哈希函数的主要作用是将任意长度的数据映射为固定长度的哈希值这个哈希值在哈希表中用作元素的索引。
哈希函数具有以下特点
一致性相同的输入键总是产生相同的哈希值。高效性计算哈希值的过程应该是高效的以便快速定位元素。雪崩效应输入键的微小变化应该导致哈希值的显著变化这有助于减少哈希冲突的可能性。抗碰撞性极难找到两个不同的输入键产生相同的哈希值即哈希冲突的概率应该很低。
常见的哈希函数有 直接定址法 这种方法通过取关键字的线性函数作为散列地址计算简单且结果分布均匀。假设我们要为一组学生的学号分配哈希地址学生的学号范围是1到100。我们可以使用直接定址法哈希函数为 Hash(key) key。例如学生学号为23则哈希地址为23。但其缺点是需要事先知道关键字的分布情况且数据范围不能相差太大因此适用于数据范围较小且连续的情况。 除留余数法 这种方法通过取关键字除以一个质数p的余数作为哈希地址其中p不大于散列表中允许的地址数m。假设我们有一个长度为10的哈希表我们希望用除留余数法为0到99之间的数字分配哈希地址。选择一个小于等于10的质数比如7作为除数。哈希函数为 Hash(key) key % 7。例如数字23的哈希地址是 23 % 7 2。除留余数法可以管理范围相差较大的数据是实际应用中非常常用的哈希函数构造方法。 平方取中法 平方取中法适用于事先不知道关键字的分布且关键字的位数不是很大的情况。假设关键字为1234对它平方就是1522756抽取中间的3位227作为哈希地址假设我们要为一组四位数分配哈希地址我们可以使用平方取中法。哈希函数为取数字平方的中间三位。例如数字1234的平方是1522756中间三位是227所以1234的哈希地址是227。通过取关键字平方后的中间几位作为哈希地址可以使得分布更加均匀减少冲突。 折叠法 折叠法适用于关键字位数较多且事先不需要知道关键字分布的情况。假设我们要为一组六位数分配哈希地址哈希表长度为100。我们可以将六位数分割成两部分每部分三位然后将这两部分相加取后两位作为哈希地址。哈希函数为 Hash(key) (key的前三位 key的后三位) % 100。例如数字123456的哈希地址是 (123 456) % 100 579 % 100 79。通过将关键字分割成若干部分并将这些部分叠加求和可以得到一个哈希地址。这种方法在处理长关键字时特别有效。 随机数法 当关键字的长度不等时可以采用随机数法。通过选择一个随机函数将关键字的随机函数值作为哈希地址。这种方法可以使得哈希地址的分布更加随机减少冲突的可能性。 数学分析法 数学分析法是根据关键字的每一位上符号的分布情况来选择哈希地址。如果某些位上符号分布均匀那么这些位就可以被选为散列地址。这种方法需要对数据的分布情况有深入的了解。
总的来说这些哈希函数方法各有其特点和适用场景。在实际应用中需要根据具体的数据特点和需求来选择合适的哈希函数以达到最优的哈希效果。同时也需要注意哈希函数的冲突处理问题通过合理的冲突解决策略来减少冲突的发生提高哈希表的性能。
3、哈希冲突的处理方法
尽管哈希函数的设计旨在使哈希冲突的可能性尽可能低但在实际应用中哈希冲突仍然可能发生。 解决哈希冲突两种常见的方法是闭散列和开散列。 链地址法Chaining当两个或多个键的哈希值相同时将这些键对应的元素存储在一个链表中。链表的头节点存储在哈希表的对应位置。当查找元素时首先计算键的哈希值然后遍历对应位置上的链表以找到元素。在 SGI STL 源代码中称表格内的元素为桶子bucket意为表格内的每个单元涵盖的不只是个节点可能是一“桶”节点。即开散列。 开放地址法Open Addressing当哈希冲突发生时尝试在哈希表的其他位置查找一个空闲槽来存储元素。根据具体实现方式的不同开放地址法又可分为线性探测、二次探测和双重散列等。即闭散列。 线性探测当哈希冲突发生时顺序检查哈希表中的下一个槽直到找到一个空闲槽。如果到达尾端就绕道头部继续寻找。例如假设 x 是任意整数 tablesize 是数组大小则 x % tablesize 得到的整数范围在 [ 0, tablesize - 1] 。刚好可以作为数组的索引 置于元素的删除只能标记删除记号实际删除则待表格重新整理时再进行这是因为表中的每个元素不仅仅表述它自己也关系到其它元素的排列。 二次探测当哈希冲突发生时根据一个二次方程来计算新的槽位置以减少聚集现象。F(i) i2 。如果使用哈希函数计算得到的位置是 H 。而该位置已被使用那么我们一次尝试 H2 12 H2 22H2 32….H2 i2 。
这些方法都有各自的优缺点需要根据具体的应用场景和需求来选择合适的方法。在实际应用中链地址法因其实现简单和灵活性而得到广泛应用。然而在处理大量哈希冲突时链表的长度可能会变得很长从而影响查找性能。因此在设计哈希表时需要综合考虑哈希函数的选择、哈希表的大小以及冲突处理策略等因素以实现高效的数据存储和访问。
二、哈希桶及其迭代器
哈希桶Hash Bucket是哈希表的一个基本组成单位用于存储具有相同哈希值的键值对。哈希桶通常与链表或其他数据结构结合使用以解决哈希冲突。 此部分内容与后面unordered_xxx的实现有关
1、 哈希桶
a.定义哈希桶结构
确定哈希桶中存储的元素类型
templateclass T
struct HashNode {HashNodeT* _next;T _data;HashNode(const T data) :_next(nullptr), _data(data) {}
};设计哈希桶的基本结构
templateclass K, class T, class KeyOfT, class Hash
class HashTable {typedef HashNodeT Node;templateclass K, class T, class KeyOfT, class Hashfriend struct __HTIterator;
public:typedef __HTIteratorK, T, KeyOfT, Hash iterator;//...
private:vectorNode* _tables;size_t _n;KeyOfT kot; Hash hs;
};根据HashNode结构体的定义这个结构体表示哈希表中每个槽位上的链表中的一个节点。每个HashNode对象包含以下部分
_next一个指向下一个HashNode的指针。当多个键值对具有相同的哈希值时它们会被链接到这个链表上通过_next指针来遍历这些节点。_data存储实际的键值对信息。这里_data只存储了值T而没有直接存储键K。这意味着我们将通过KeyOfT函数对象从值中提取。
在HashTable类中_tables是一个向量vector它存储了指向HashNode的指针。每个槽位即_tables中的一个元素可以是一个空指针表示该槽位没有存储任何键值对或者是一个指向链表头节点的指针表示该槽位上有一个或多个具有相同哈希值的键值对。
当向哈希表中插入一个键值对时哈希函数hs以及提取键的kot会被用来计算键的哈希值这个哈希值随后被用来确定键值对应该放在_tables的哪个槽位上。如果那个槽位已经有一个链表新的键值对将被作为一个新的HashNode添加到链表的末尾如果槽位是空的则创建一个新的HashNode并放在那里。
查找操作也类似计算键的哈希值找到对应的槽位然后遍历链表来查找具有匹配键的节点。 请注意由于HashNode只存储了值T而没有直接存储键KHashTable类中的KeyOfT函数对象就变得非常重要了。它负责从值T中提取出键K以便在插入、查找和删除操作中能够正确地比较键。 b.哈希函数
哈希函数是用于将任意长度的数据映射为固定长度的数值的函数。在哈希表等数据结构中哈希函数对于性能至关重要因为它决定了数据如何在哈希表中分布
templateclass K
struct HashFunc {size_t operator()(const K key) { return (size_t)key; }
};
template
struct HashFuncstring {size_t operator()(const string s) {size_t hashi 0;for (auto e : s) {hashi e;hashi * 31;}return hashi;}
};两个HashFunc模板特化定义展示了如何为不同类型的键实现哈希函数。 第一个模板定义是一个通用版本它将键K直接转换为size_t类型并返回。这适用于那些其数值本身就可以作为哈希值的简单类型例如整数或浮点数。然而这种转换对于复杂的类型如自定义类或字符串可能并不适用因为这些类型的值可能不适合直接用作哈希值。 第二个模板特化是为string类型定义的。它使用了一个常见的字符串哈希算法即所谓的“Rabin-Karp”哈希算法的一个简化版本。这个算法通过遍历字符串中的每个字符并累加一个与字符值相关的值在这里是通过将字符值加到hashi变量中然后将结果乘以一个常数在这里是31。这个算法的目的是生成一个与字符串内容紧密相关的哈希值同时保持一定的随机性以减少哈希冲突。
这种哈希函数的一个缺点是它可能不是均匀分布的特别是在处理长字符串时哈希值可能会快速溢出导致分布不均匀。此外如果字符串中包含的字符很多累加和乘法的结果可能会受到整数溢出的影响从而导致不可预测的行为。
c.哈希桶的插入、查找、删除
Find 函数这个函数用于在哈希表中查找具有给定键的节点。
iterator Find(const K key) {size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur) {if (kot(cur-_data) key)return iterator(cur, this);cur cur-_next;}return iterator(nullptr, this);
}首先计算键的哈希值并找到该键应该在的槽位通过取模操作hs(key) % _tables.size()。然后遍历该槽位上的链表查找具有匹配键的节点。如果找到匹配的节点它返回一个指向该节点的迭代器。如果没有找到匹配的节点它返回一个指向nullptr的迭代器表示未找到。
Insert 函数这个函数用于在哈希表中插入一个新的键值对。
pairiterator,bool Insert(const T data) {iterator it Find(kot(data));if (it ! end())return { it,this };if (_n _tables.size()) {vectorNode* newTables(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur) {Node* next cur-_next;size_t hashi hs(kot(cur-_data)) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi hs(kot(data)) % _tables.size();Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return { iterator(newnode, this),true };
}首先调用Find函数来检查是否已存在具有相同键的节点。如果找到了匹配的节点说明键已存在函数返回一个包含该节点迭代器的pair并标记为未插入false。如果键不存在它首先检查是否需要扩展哈希表即如果当前存储的键值对数量_n等于哈希表的大小_tables.size()。 如果需要扩展它创建一个新的、大小是原来两倍的哈希表并将旧哈希表中的所有节点重新哈希并插入到新哈希表中。然后它交换新旧哈希表使得_tables指向新的、更大的哈希表。 接下来它计算新键值对的哈希值创建一个新的Node并将其插入到正确的槽位上。最后它更新已存储的键值对数量_n并返回一个包含新节点迭代器的pair并标记为已插入true。
Erase 函数这个函数用于从哈希表中删除具有给定键的节点。
bool Erase(const K key) {size_t hashi hs(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur) {if (kot(cur-_data) key) {// 删除if (prev)prev-_next cur-_next;else_tables[hashi] cur-_next;delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;
}首先计算键的哈希值找到正确的槽位。然后遍历该槽位上的链表查找具有匹配键的节点。如果找到匹配的节点更新链表以删除该节点通过调整前一个节点的_next指针释放该节点的内存并更新已存储的键值对数量_n。最后返回true表示删除成功。如果没有找到匹配的节点返回false表示删除失败。
上述内容不难理解不做赘述。 2、 哈希桶的迭代器
哈希桶迭代器用于遍历哈希表中的所有元素。hashtable的迭代器没有后退操作也没有定义所谓的逆向迭代器。且以哈希桶为底层的unordered_xxx都是单向迭代器。
单向迭代器在大多数情况下已经足够满足哈希桶的遍历需求。哈希桶主要用于存储和快速查找键值对而单向迭代器能够按顺序遍历桶中的元素满足基本的遍历需求。如果需要反向遍历或进行更复杂的操作通常可以在外部逻辑中处理而不必要求迭代器本身支持这些功能。
a.类型定义与成员变量
templateclass K, class T, class KeyOfT, class Hash
struct __HTIterator {typedef HashNodeT Node;typedef HashTableK, T, KeyOfT, Hash HT;typedef __HTIteratorK, T, KeyOfT, Hash Self;Node* _node;HT* _ht;
};类型定义: Node: 指向HashNodeT类型表示哈希表中的一个节点。HT: 指向HashTableK, T, KeyOfT, Hash类型表示整个哈希表。Self: 指向迭代器自身的类型方便在迭代器内部引用自身。 成员变量: _node: 指向当前哈希节点的指针。_ht: 指向哈希表的指针用于迭代器内部的操作比如寻找下一个非空桶。
b.构造函数
构造函数: __HTIterator(Node* node, HT* ht): 接收一个指向节点的指针和一个指向哈希表的指针用于初始化迭代器。
c.解引用与比较操作 解引用操作: T operator*() { return _node-_data; }
T* operator-() { return _node-_data; }T operator*(): 返回当前节点存储的数据的引用。T* operator-(): 返回当前节点存储数据的指针允许使用箭头操作符访问节点的数据成员。 比较操作: bool operator!(const Self s) { return _node ! s._node; }
bool operator(const Self s) { return _node s._node; }bool operator!(const Self s): 比较当前迭代器和另一个迭代器是否不等通过比较它们的节点指针实现。bool operator(const Self s): 比较当前迭代器和另一个迭代器是否相等不仅比较节点指针还比较它们所属的哈希表指针确保它们在同一个哈希表中。
d.递增操作 递增操作: Self operator() {if (_node-_next) {_node _node-_next;}else {KeyOfT kot;Hash hs;size_t hashi hs(kot(_node-_data)) % _ht-_tables.size();hashi;while (hashi _ht-_tables.size()) {if (_ht-_tables[hashi]) {_node _ht-_tables[hashi];break;}hashi;}if (hashi _ht-_tables.size()) {_node nullptr;}}return *this;
}Self operator(): 实现迭代器的递增功能即移动到下一个节点。 如果当前节点有下一个节点即_node-_next不为空则迭代器直接移动到下一个节点。如果没有下一个节点迭代器需要找到下一个非空桶。这里它首先计算当前节点数据的哈希值并尝试找到下一个哈希值对应的桶。然后它遍历哈希表直到找到一个非空桶或者遍历完整个哈希表。如果遍历完整个哈希表都没有找到非空桶则将_node设置为nullptr表示迭代器已经到达哈希表的末尾。
三、总结
这个迭代器设计适用于基于哈希表的关联容器能够按照桶的顺序遍历元素。当桶内部存在链表来处理哈希冲突时迭代器能够正确地在链表内部进行遍历。
哈希函数与键提取函数的局部声明在operator中通常KeyOfT和Hash这些函数作为模板参数传递给哈希表的并在哈希表内部使用。哈希值的计算KeyOfT提取了键哈希函数Hash通过提取出来的键来计算哈希值。迭代器访问哈希桶内私有变量我们通过将迭代器声明为哈希桶类的友元函数。
HashTable模板类中_tables是一个私有成员变量它存储了指向HashNodeT类型对象的指针。这个_tables通常表示哈希表的内部存储结构也就是所谓的“桶”buckets每个桶可能包含一个链表或其他结构来处理哈希冲突。
__HTIterator是一个模板结构体它作为HashTable的迭代器。由于迭代器需要访问HashTable的私有成员特别是_tables通常迭代器会被声明为HashTable的友元friend。这样__HTIterator就可以访问HashTable的私有成员变量包括_tables以便能够正确地遍历哈希表中的元素。
在HashTable模板类中通过以下方式声明了__HTIterator为友元
templateclass K, class T, class KeyOfT, class Hash
friend struct __HTIterator;这意味着对于任何HashTable的特定实例其对应的__HTIterator实例都可以访问该HashTable的私有成员。
iterator是__HTIteratorK, T, KeyOfT, Hash的一个类型别名定义在HashTable的公共部分。这样用户可以使用HashTable::iterator来引用迭代器类型而不需要写出完整的模板实例化。
现在关于迭代器如何访问哈希桶内的私有变量
通过友元关系由于__HTIterator是HashTable的友元它可以直接访问_tables等私有成员。遍历桶和节点迭代器内部可能有一个指向当前桶的指针和一个指向当前桶内链表中节点的指针。迭代器通过这些指针来遍历桶内的链表从而访问哈希表中的元素。不直接修改桶结构尽管迭代器可以访问桶但它通常不应该直接修改桶的结构如添加或删除桶。这些操作应该由HashTable类的成员函数来执行以确保哈希表的一致性和正确性。访问节点数据迭代器通过访问桶内的节点来访问存储的元素。每个节点通常包含一个指向实际数据的指针或引用迭代器通过节点的公有接口如getter方法来获取这些数据。
下面我给出哈希桶及其迭代器的完整实现
namespace hash_bucket
{templateclass Tstruct HashNode {HashNodeT* _next;T _data;HashNode(const T data) :_next(nullptr), _data(data) {}};templateclass K, class T, class KeyOfT, class Hash class HashTable;templateclass K, class T, class KeyOfT, class Hashstruct __HTIterator {typedef HashNodeT Node;typedef HashTableK, T, KeyOfT, Hash HT;typedef __HTIteratorK, T, KeyOfT, Hash Self;Node* _node;HT* _ht;__HTIterator(Node* node, HT* ht) :_node(node), _ht(ht) {}T operator*() { return _node-_data; }T* operator-() { return _node-_data; }bool operator!(const Self s)const { return _node ! s._node; }bool operator(const Self s) const { return _node s._node; }Self operator() {if (_node-_next) {_node _node-_next;}else {KeyOfT kot;Hash hs;size_t hashi hs(kot(_node-_data)) % _ht-_tables.size();hashi;while (hashi _ht-_tables.size()) {if (_ht-_tables[hashi]) {_node _ht-_tables[hashi];break;}hashi;}if (hashi _ht-_tables.size()) {_node nullptr;}}return *this;}};templateclass K, class T, class KeyOfT, class Hash class HashTable {typedef HashNodeT Node;templateclass K, class T, class KeyOfT, class Hashfriend struct __HTIterator;public:typedef __HTIteratorK, T, KeyOfT, Hash iterator;iterator begin(){for (size_t i 0; i _tables.size(); i)if (_tables[i])return iterator(_tables[i], this);return end();}iterator end() { return iterator(nullptr, this); }HashTable()//:kot(KeyOfT()),hs(Hash()){_tables.resize(10, nullptr);_n 0;kot KeyOfT();hs Hash();} ~HashTable() {for (size_t i 0; i _tables.size(); i) {Node* cur _tables[i];while (cur) {Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}pairiterator,bool Insert(const T data) {iterator it Find(kot(data));if (it ! end())return { it,this };if (_n _tables.size()) {vectorNode* newTables(_tables.size() * 2, nullptr);for (size_t i 0; i _tables.size(); i){Node* cur _tables[i];while (cur) {Node* next cur-_next;size_t hashi hs(kot(cur-_data)) % newTables.size();cur-_next newTables[hashi];newTables[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTables);}size_t hashi hs(kot(data)) % _tables.size();Node* newnode new Node(data);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return { iterator(newnode, this),true };}bool Erase(const K key) {size_t hashi hs(key) % _tables.size();Node* prev nullptr;Node* cur _tables[hashi];while (cur) {if (kot(cur-_data) key) {// 删除if (prev)prev-_next cur-_next;else_tables[hashi] cur-_next;delete cur;--_n;return true;}prev cur;cur cur-_next;}return false;}iterator Find(const K key) {size_t hashi hs(key) % _tables.size();Node* cur _tables[hashi];while (cur) {if (kot(cur-_data) key)return iterator(cur, this);cur cur-_next;}return iterator(nullptr, this);}private:vectorNode* _tables;size_t _n;KeyOfT kot; Hash hs;};
}
