什么网站可以请人做软件下载,阳光电子商务平台,广东省建设安全卡查询网站,深圳工业设计工资引子#xff1a;之前我们讲了红黑树的自实现#xff0c;与小小的接口实现#xff0c;那set与map的pair封装是如何实现的呢#xff1f;#xff0c;今天我们来一探究竟#xff0c;而且我们也要进入新章节--哈希 对于operator--()的封装#xff1a;
注意#xff1a;牢记思…
引子之前我们讲了红黑树的自实现与小小的接口实现那set与map的pair封装是如何实现的呢今天我们来一探究竟而且我们也要进入新章节--哈希 对于operator--()的封装
注意牢记思考的方向始终是中序
示意图 stl代码实现 void decrement(){if (node-color __rb_tree_red node-parent-parent node)node node-right;else if (node-left ! 0) {base_ptr y node-left;while (y-right ! 0)y y-right;node y;}else {base_ptr y node-parent;while (node y-left) {node y;y y-parent;}node y;}}
};
自实现我们在传的时候要传一下_root,因为我们不是通过以上stl中hearer的方式
迭代器部分更改
Node* _root;RBTreeIterator(Node*node,Node*root):_node(node),_root(root)
{}
self operator--()
{if (_node nullptr) {//找最右节点Node* rightMost _root;while (rightMost rightMost-_right){rightMost rightMost-_right;}_node rightMost;}else if (_node-_left){Node* rightMost _node-_left;while (rightMost-_right){rightMost rightMost-_right;}_node rightMost;}else{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur parent;parent cur-_parent;}_node parent;}return *this;
}
对于set的insert封装
//插入
pairiterator,boolinsert(const T data)
{//空树新增节点也是红黑树Node* root _root;if (root nullptr){root new Node(data);_root root;_root-_col BLACK;return make_pair(iterator(_root, _root), true);}//红黑树大逻辑K_of_T kot;Node* cur _root;Node* parent nullptr;//要先找到插入位置while (cur){if (kot(data) kot(cur-_Data)){parent cur;cur cur-_left;}else if (kot(data) kot(cur-_Data)){parent cur;cur cur-_right;}else{return make_pair(iterator(cur, _root), false);}}cur new Node(data);// 新增节点。颜色红色给红色cur-_col RED;Node* newNode cur;if (kot(parent-_Data) kot(data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//更改颜色//现在cur为新增节点while (parent parent-_colRED){Node* grandfather parent-_parent;//找出叔叔节点if (parent grandfather-_left){Node* uncle grandfather-_right;//情况一if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{//情况二// g// p u//cif (parent-_left cur){RotateR(grandfather);grandfather-_col RED;parent-_col BLACK;}else{//情况三// g// p u// c// //双旋RotateL(parent);RotateR(grandfather);//注意cur与parent调了一下位置cur-_col BLACK;grandfather-_col RED;}break;}}else{Node* uncle grandfather-_left;//情况一if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{ //情况二// g// u p// cif (cur parent-_right){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}//情况三// g// u p// c else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}//确保根节点为黑的_root-_col BLACK;return make_pair(iterator(newNode, _root), true);
}
对于map的话只要将k对应的vaule输出就行注意调用的时候也要改为pairiterator,bool
什么是哈希
一哈希是一种数学函数它接受一个输入或“消息”然后返回一个通常更小的固定大小的输出这个输出称为“哈希值”或“哈希码”。
二哈希也是一种思想映射哈希思想通过哈希函数将任意长度的数据映射到固定长度的哈希值。这个映射过程是单向的即从数据到哈希值是容易的但从哈希值回溯到原始数据几乎是不可能的。快速性哈希函数的设计旨在快速计算以便在大数据集中实现高效的数据访问。均匀分布理想情况下哈希函数应该能够将输入数据均匀地分布在哈希值空间中以减少冲突并提高查找效率。
哈希的应用
哈希思想在数据库索引、密码存储、信息检索、数据同步、数字签名、区块链技术等多个领域都有广泛的应用。通过哈希可以有效地管理和访问大量数据同时保证数据的安全性和完整性。 由哈希来的哈希表unordered
一背景
在C98中STL提供了底层为红黑树结构的一系列关联式容器在查询时效率可达到log_2N即最差情况下需要比较红黑树的高度次当树中的节点非常多时查询效率也不理想。最好 的查询是进行很少的比较次数就能够将元素找到因此在C11中STL又提供了4个 unordered系列的关联式容器这四个容器与红黑树结构的关联式容器使用方式基本类似只是其底层结构不同
以下是unordered_set与set的区别图我们可以更加看到底层结构为哈希表的优势 对于调试性能大家可以通过以下代码进行测试
#includeunordered_set
#includeiostream
#includesetusing namespace std;int test_set2()
{const size_t N 10000000;unordered_setint us;setint s;vectorint v;v.reserve(N);srand(time(0));for (size_t i 0; i N; i){//v.push_back(rand()); // N比较大时重复值比较多//v.push_back(rand()i); // 重复值相对少v.push_back(i); // 没有重复有序}size_t begin1 clock();for (auto e : v){s.insert(e);}size_t end1 clock();cout set insert: end1 - begin1 endl;size_t begin2 clock();for (auto e : v){us.insert(e);}size_t end2 clock();cout unordered_set insert: end2 - begin2 endl;int m1 0;size_t begin3 clock();for (auto e : v){auto ret s.find(e);if (ret ! s.end()){m1;}}size_t end3 clock();cout set find: end3 - begin3 - m1 endl;int m2 0;size_t begin4 clock();for (auto e : v){auto ret us.find(e);if (ret ! us.end()){m2;}}size_t end4 clock();cout unorered_set find: end4 - begin4 - m2 endl;cout 插入数据个数 s.size() endl;cout 插入数据个数 us.size() endl endl;size_t begin5 clock();for (auto e : v){s.erase(e);}size_t end5 clock();cout set erase: end5 - begin5 endl;size_t begin6 clock();for (auto e : v){us.erase(e);}size_t end6 clock();cout unordered_set erase: end6 - begin6 endl endl;return 0;
}int main()
{test_set2();return 0;
}
可以有以下的结果只展示一种 哈希函数
引起哈希冲突的一个原因可能是哈希函数设计不够合理。
哈希函数设计原则
哈希函数的定义域必须包括需要存储的全部关键码而如果散列表允许有m个地址时其值 域必须在0到m-1之间
哈希函数计算出来的地址能均匀分布在整个空间中
哈希函数应该比较简单
常见的哈希函数包括以下几种类型(最常用的用颜色标出了)
直接定址法使用关键字本身作为哈希地址例如年龄作为关键字时年龄值直接作为哈希地址
数字分析法选择数字的某些部分作为哈希地址避免使用重复可能性大的数字前几位
平方取中法取关键字平方后的中间几位作为哈希地址
折叠法将关键字分割成位数相同的几部分然后取这几部分的叠加和作为哈希地址
除留余数法使用关键字除以一个不大于哈希表大小的数后的余数作为哈希地址公式为 H(key) key%p (p ≤ m) ;
随机数法使用随机函数作为哈希地址适用于关键字长度不等的情况
加法哈希通过将字符串中每个字符的ASCII值累加得到哈希值
位运算Hash利用位运算如移位和异或混合输入元素例如旋转Hash
乘法Hash使用乘法的不相关性例如使用乘数31的String类的hashCode()方法
除法Hash虽然不常用但除法也具有不相关性可以用于哈希函数
查表Hash如CRC系列算法通过查找预设的表来实现快速哈希
混合哈希算法结合以上各种方式例如MD5、Tiger等它们通常用于需要高安全性的场合
哈希冲突解决 哈希冲突
哈希冲突也称为哈希碰撞是指两个不同的输入值通过哈希函数计算后得到相同的哈希值。由于哈希函数的输出长度是固定的而输入数据可以是无限的理论上讲任何哈希函数都可能发生冲突.
解决哈希冲突两种常见的方法是闭散列和开散列
一什么是闭散列 也叫开放定址法当发生哈希冲突时如果哈希表未被装满说明在哈希表中必然还有 空位置那么可以把key存放到冲突位置中的“下一个” 空位置中去。那如何寻找下一个空位置 呢
1.1线性探测需要枚举3种状态 计算哈希值首先使用哈希函数计算键key的哈希值确定它在哈希表中的理论位置。 检查冲突如果该位置已被占用即发生冲突则按照固定间隔通常是1移动到下一个位置。 探测序列继续线性地探测下一个位置直到找到一个空闲位置。 插入元素一旦找到空闲位置将元素插入到该位置。 处理表满如果探测到表的末尾仍未找到空闲位置则循环回到表的开头继续探测。 查找元素在查找元素时也需要从哈希值对应的位置开始按照相同的探测序列查找直到找到目标元素或遇到一个空闲位置表示元素不存在。 删除元素删除元素时不能简单地将位置置为空因为这会打断查找其他元素的探测序列。通常使用一个特殊的标记如“已删除”标记来代替真正的空位。
1.2二次探测需要枚举3种状态 计算哈希值首先使用哈希函数计算键的哈希值确定它在哈希表中的理论位置。 发生冲突如果该位置已被占用计算下一个探测位置公式为 探测位置(原始位置)i^2 其中 i 是探测的第几次尝试i1,2,3,… 探测序列探测位置是原始哈希值加上 i^2 的结果这样探测的间隔会随着 i 的增加而增加1, 4, 9, 16, ...。 插入元素当找到一个空闲位置时将元素插入到该位置。 循环探测如果探测到表尾继续从表头开始探测直到找到空闲位置。 查找元素查找时也需要按照相同的探测序列进行查找直到找到目标元素或确定元素不存在。 删除元素与线性探测类似不能简单地将位置置为空而是使用一个特殊的标记来表示该位置已被删除。
其他平衡因子
哈希的平衡因子也称为荷载因子Load Factor是衡量哈希表性能的一个重要参数。它定义为哈希表中已存储元素的数量与哈希表的总槽位数即哈希表的大小之比。荷载因子用以下公式表示
荷载因子已存储元素的数量/哈希表的大小
荷载因子反映了哈希表的填充程度对哈希表的性能有直接影响 二什么是开散列就是说
开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地 址的关键码归于同一子集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链 接起来各链表的头结点存储在哈希表中。 下节我将详细讲解哈希表已经自实现希望帮到大家
