海南网站建设推荐,seo自学网app,信息公开网站建设,为了做宣传网站而注册公司前言 C中的unordered容器#xff08;例如std::unordered_set、std::unordered_map等#xff09;底层是基于**哈希表#xff08;Hash Table#xff09;**实现的。哈希表是一种通过哈希函数将元素映射到特定“桶#xff08;bucket#xff09;”的容器#xff0c;提供快速的…前言 C中的unordered容器例如std::unordered_set、std::unordered_map等底层是基于**哈希表Hash Table**实现的。哈希表是一种通过哈希函数将元素映射到特定“桶bucket”的容器提供快速的查找、插入和删除操作。 unordered系列的实现基哈希桶
哈希表的基本结构
哈希表的核心思想是**将元素的值或键通过哈希函数Hash Function映射到哈希表中的某个桶bucket。每个桶通常是一个链表或其他数据结构用来处理冲突。当不同的元素通过哈希函数得到相同的哈希值时会出现哈希冲突Hash Collision**冲突的元素会被存储在同一个桶内。
哈希表的关键组成部分有
哈希表Hash Table unordered_map 和 unordered_set 底层使用哈希表来存储元素。 哈希表的核心是一个数组这个数组的每个位置被称为一个“桶”bucket。 每个桶可以存储一个或多个元素这些元素的键通过哈希函数映射到该桶中。哈希函数Hash Function 哈希函数负责将键值映射到哈希表中的某个桶。 C 标准库允许用户提供自定义的哈希函数默认情况下使用 std::hash 提供的哈希函数。 哈希函数的好坏直接影响到哈希表的性能一个好的哈希函数应当均匀分布键值减少冲突。冲突处理Collision Handling 哈希冲突发生在不同的键被映射到同一个桶时。 C 的 unordered_map 和 unordered_set 使用 开链法Chaining 处理冲突。 在开链法中每个桶内部实际上是一个链表或类似的结构用于存储多个哈希冲突的元素。 这意味着即使有冲突发生元素也不会丢失而是通过链表来管理这些冲突的元素。负载因子和扩展Load Factor and Rehashing 负载因子Load Factor定义为元素数量与桶数量的比值。当负载因子超过一个预设的阈值时哈希表会进行扩展即再散列 rehashing。 扩展通常意味着分配一个更大的桶数组并重新计算每个元素的哈希值然后将它们放入新的桶中。 再散列的过程可以确保在负载因子较高时哈希表的操作仍然是高效的。迭代顺序 因为哈希表的存储结构无序unordered_map 和 unordered_set 的迭代顺序是未定义的。 迭代顺序依赖于哈希函数和元素的插入顺序以及哈希表的大小和当前负载因子。时间复杂度 在理想情况下即哈希冲突少unordered_map 和 unordered_set 的插入、查找、删除操作的时间复杂度是 O(1)。 但在最坏情况下大量冲突这些操作的时间复杂度可能退化为 O(n)。
存储结构
类似于链表在顺序表中存储一个一个节点。
templateclass T
struct HashNode
{T _data;HashNodeT* _next;HashNode(const T data):_data(data),_next(nullptr){}
};table使用 std::vector 存储多个链表每个链表代表一个桶链表中的元素是映射到这个桶的所有元素。记录_n进行负载因子的储存class KeyofT是作为仿函数是为了配合K型和KV结构适应的
templateclass K,class T,class KeyofT,class HashFunc defaultHashfuncK
class HashTable
{public:...private:vectorNode* _table;size_t _n 0;
};哈希函数
在函数的内容的不确定的时候进行返回。针对string字符串的直接进行特模板化。针对26字母有不同的组合要进行字符串的哈希化处理目的是针对哈希冲突 本次采用 BKDR算法参考字符串哈希算法
templateclass T
struct defaultHashfunc
{size_t operator()(const T data){return (size_t)data;}
};
//模板特化
template
struct defaultHashfuncstring
{size_t operator()(const string str){size_t hash 0;for (auto ch : str){hash * 131;hash ch;}return hash;}
};unordered插入操作 哈希计算 当你插入一个元素比如在unordered_map中插入一个键值对首先会调用哈希函数对键key进行哈希计算。这个哈希函数返回一个哈希值通常是一个无符号整数类型如std::size_t。 这个哈希值会被用来确定元素应该存储在哪个桶bucket中。桶的数量通常是哈希表当前容量的一个因子。 桶的选择 哈希表根据哈希值和桶的数量来确定目标桶的位置。通常这是通过取模运算来完成的即 hf(kot(data)) % _table.size() 在这个位置上哈希表要检查这个桶是否已经存在元素如果存在则进行冲突处理。 冲突处理 如果目标桶已经有其他元素即发生了哈希冲突unordered_map 和 unordered_set 通过 开链法chaining 进行处理。 开链法意味着每个桶实际上包含一个链表或链表的类似结构。新元素将被添加到这个链表中。 元素存储 如果目标桶为空则直接将新元素存储在该桶中。 如果目标桶不为空发生冲突则将元素追加到该桶的链表中。 在 unordered_map 中如果插入的键已经存在则插入操作不会改变哈希表而是更新该键对应的值。 负载因子与再散列Rehashing 每次插入操作都会检查哈希表的负载因子即元素数量与桶数量的比值。 如果负载因子超过了哈希表的最大负载因子max_load_factor()哈希表会自动扩展增加桶的数量并重新分配所有元素到新的桶中。这就是所谓的再散列rehashing。 再散列过程中所有元素都将被重新哈希和插入新的桶中这样可以保证哈希表的高效性
pairiterator,bool insert(const T data)
{KeyofT kot;HashFunc hf;iterator it Find(kot(data));if (it ! end()){return make_pair(it,false);}if (_n _table.size()){size_t newsize _table.size() * 2;vectorNode* 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(kot(cur-_data)) % newtable.size();cur-_next newtable[hashi];newtable[hashi] cur;cur next;}_table[i] nullptr;}_table.swap(newtable);}size_t hashi hf(kot(data)) % _table.size();Node* newnode new Node(data);newnode-_next _table[hashi];_table[hashi] newnode;_n;return make_pair(iterator(newnode,this),true);
}
unordered删除操作
删除操作的底层流程 哈希计算 对于基于键删除的操作如 erase(const key_type k)首先会对给定的键 k 进行哈希计算计算出哈希值。 根据哈希值确定该键可能存储在哪个桶中。 查找元素 哈希表在确定了桶的位置后会在对应的桶链表中查找目标元素。 如果找到匹配的元素哈希表会进行删除操作如果未找到erase 返回 0表示没有元素被删除。 删除元素 删除元素时需要从桶的链表中移除该元素并处理相应的链表指针调整以确保链表结构的完整性。 如果该桶中的链表只有一个元素删除该元素后该桶变为空。 如果链表中有多个元素删除操作只影响指定元素并将链表的前后元素连接起来。
bool Erase(const K key)
{HashFunc hf;KeyofT kot;size_t hashi hf(kot(key)) % _table.szie();Node* cur _table[hashi];Node* prev nullptr;while (cur){if (kot(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;
}unordered查找操作
桶的选择 根据哈希值确定桶的位置索引通常通过哈希值对桶的数量取模来实现即 bucket_index hash_value % bucket_count。 定位到桶之后开始在该桶的链表中查找目标元素。遍历桶的链表 如果目标桶不为空查找操作会遍历桶中的链表比较每个元素的键与目标键 k 是否相同。 如果找到匹配的键find() 方法返回指向该元素的迭代器。如果未找到返回 end()。
iterator Find(const K key)
{HashFunc hf;KeyofT kot;size_t hashi hf(key) % _table.size();Node* cur _table[hashi];while (cur){if (kot(cur-_data) key){return iterator(cur,this);}cur cur-_next;}return iterator(nullptr, this);
}unordered迭代器
迭代器的结构
迭代器的构建需要_node的节点和哈希表的指针。节点的指针是进行返回当前节点的值。
templateclass K,class T,class Ptr,class Ref,class KeyofT, class HashFunc
struct HashIterator
{typedef HashNodeT Node;typedef HashIteratorK, T, Ptr, Ref ,KeyofT, HashFunc Self;typedef HashIteratorK, T, T*, T, KeyofT, HashFunc iterator;Node* _node;const HashTableK, T, KeyofT, HashFunc* _pht;};迭代器的特点
在迭代器内需要写普通迭代器的拷贝构造const迭代器的构造函数在迭代器实例化不同的类型这个函数作用是不一样的。这个的目的是为了解决set的insert返回值的需求map返回pairiteratorbool由于利用同于一个适配器需要适应不同的容器。
HashIterator(const iterator it):_node(it._node),_pht(it._pht)
{迭代器自增
if判断当前桶的是否还存在剩余节点存在返回下一个不存在调整至下一个不为空的桶。
Self operator()
{if (_node-_next){_node _node-_next;}else{KeyofT kot;HashFunc hf;size_t hashi hf(kot(_node-_data)) % _pht-_table.size();hashi;while (hashi _pht-_table.size()){if (_pht-_table[hashi]){_node _pht-_table[hashi];return *this;}else{hashi;}}_node nullptr;}return *this;
}迭代器其余结构
重载 * 、重载 - 、重载 !
Ref operator*()
{return _node-_data;
}Ptr operator-()
{return _node-_data;
}
bool operator!(const Self s)
{return _node ! s._node;
}
bool operator(const Self s)
{return _node-_data s._node;
}迭代器的封装
begin返回第一个储存数据的节点end返回空指针
iterator begin()
{ for (int i 0; i _table.size(); i){Node* cur _table[i];while (cur){if (cur){return iterator(cur, this);}}}return iterator(nullptr, this);
}
iterator end()
{return iterator(nullptr, this);
}map和set的封装
map的set的仿函数
仿函数传过去是在实例化的时候为了取到不同的结构下的值
struct mapofT
{const K operator()(const pairK, T kv){return kv.first;}
};struct setofT
{const K operator()(const K key){return key;}
};map的set的插入
由于map储存键值对返回pairset为了适应结构返回也是pairset的返回进行再次接受哈希桶底层利用iterator在这里返回const需要进行构造
pairiterator,bool insert(const pairK, T kv)
{return _ht.insert(kv);
}pairconst_iterator,bool insert(const K data)
{pairtypename HashTableK, K, setofT::const_iterator, bool ret _ht.insert(data);return make_pair(ret.first, ret.second);
}map的operator[]
采用insert进行返回存在key返回当前迭代器不存在插入这个值。整体这个函数放回该值的pair的second。
T operator[](const K key)
{pairiterator, bool ret insert(make_pair(key, T()));return ret.first-second;
}
