u8,u8国际,u8国际官方网站,u8国际网站,u8国际网址,u8国际链接,u8体育,u8体育官网,u8体育网址,u8注册,u8体育网址,u8官方网站,u8体育APP,u8体育登录,u8体育入口

　　2.每次相同的输入一定得到相同的输出。不同的输入也可能产生相同的输出。（哈希碰撞）

　　3.输出分布是绝对离散的，不会受输入的影响，即同样的面积在任何地方框点都是差不多的。（最重要，哈希函数主要利用这个性质）

　　4.任何值模上一个数，最后一定得到0-该数的一个范围值。比如任何数模（或者说取余）上100，最后得到的值一定在0-99范围内。并且是绝对均匀分布。

　　哈希函数的目的是用于哈希表的第一步数组查询，直接通过取模（哈希函数）就得到哈希表对应的位置。这一步的时间复杂度是O（1）。

　　当出现数组的每个链表过长的时候，需要扩容。扩容之后全部每一条数据都得重新计算。

　　哈希表每次增删改查的代价可以说是O（1），虽然每次扩容的代价是O（logn）。一个原因是现实使用的工程数据量都是非常低的，另一个原因是离线技术，不占用用户使用的时候的时间。

　　1.当更多的数插入时，哈希表冲突的可能性就更大。对于冲突，哈希表通常有两种解决方案：第一种是线性探索，相当于在冲突的地方后建立一个单链表，这种情况下，插入和查找以及删除操作消耗的时间会达到O(n)，且该哈希表需要更多的空间进行储存。第二种方法是开放寻址，他不需要更多的空间，但是在最坏的情况下（例如所有输入数据都被map到了一个index上）的时间复杂度也会达到O(n)。

　　2.在决定建立哈希表之前，最好可以估计输入的数据的size。否则，resize哈希表的过程将会是一个非常消耗时间的过程。例如，如果现在你的哈希表的长度是100，但是现在有第101个数要插入。这时，不仅哈希表的长度可能要扩展到150，且扩展之后所有的数都需要重新rehash。

　　3.哈希表中的元素是没有被排序的。然而，有些情况下，我们希望储存的数据是有序的。

　　哈希表适用于那种查找性能要求高，数据元素之间无逻辑关系要求的情况。例如做文件校验或数字签名。当然还有快速查询功能的实现。

　　主要目的：主要是用它来存储有序的数据，它增删改查的时间复杂度都是O(logn)。

　　红黑树首先是平衡二叉树（AVL）的一种，所以他一定满足根节点小于左子树大于右子树。再然后才是它特有的属性。

　　二分查找法不能处理大数据和非数字情况，有了二分查找树；二分查找树会出现单链表情况，所以有了AVL树通过旋转实现绝对平衡；但是AVL树为了维护绝对平衡，几乎每次插入删除都要进行旋转操作；删除节点的时候，需要要维护从被删除节点到根节点这几个节点的平衡，旋转的时间复杂度是O（logn）,所以有了红黑树，在牺牲一定的查找效率的情况下，提升了删除效率。

　　总结：实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。

　　map的底层是红黑树，unordered_map底层是哈希表，明明哈希表的查询效率更高，为什么还需要红黑树？

　　1.map始终保证遍历的时候是按key的大小顺序的，这是一个主要的功能上的差异。（有序无序）

　　2.时间复杂度上，红黑树的插入删除查找性能都是O(logN)而哈希表的插入删除查找性能理论上都是O(1)，他是相对于稳定的，最差情况下都是高效的。哈希表的插入删除操作的理论上时间复杂度是常数时间的，这有个前提就是哈希表不发生数据碰撞。在发生碰撞的最坏的情况下，哈希表的插入和删除时间复杂度最坏能达到O(n)。

　　5.因为3，所以对map的遍历可以和修改map在一定程度上并行（一定程度上的不一致通常可以接受），而对unordered_map的遍历必须防止修改map的iterator可以双向遍历，这样可以很容易查找到当前map中刚好大于这个key的值，或者刚好小于这个key的值这些都是map特有而unordered_map不具备的功能。（这个不太明白，先放一放）

　　红黑树的插入删除查找性能都是O(logN)而哈希表的插入删除查找性能理论上都是O(1)，在这个对比上来看，红黑树性能远没有哈希表优秀。但是值得一提的是红黑树从上面介绍的资料来看，**他是相对于稳定的，最差情况下都是高效的。**而相对于哈希表这个数据结构来讲，哈希表的插入删除操作的理论上时间复杂度是常数时间的，这有个前提就是哈希表不发生数据碰撞。**在发生碰撞的最坏的情况下，哈希表的插入和删除时间复杂度最坏能达到O(n)。**而在一般情况下，如果在实际应用中，当然一个相对稳定且快速的数据结构是比较理想的选择。

　　红黑树的基本特征就那5个，234这三个类似，记下第5个和第1个就好了：红黑树

　　因为avl树是高度平衡，而红黑树通过增加节点颜色从而实现部分平衡，即从根到叶子的最长的可能路径不多于最短的可能路径的两倍长，这就导致，插入节点两者都可以最多两次实现复衡，而删除节点，红黑树最多三次旋转即可实现复衡，旋转的量级是O（1），而avl树需要维护从被删除节点到根节点这几个节点的平衡，旋转的量级是O（logn）,所以红黑树效率更高，开销更小，但是因为红黑树是非严格平衡，所以它的查找效率比avl树低。

　　总结：实际应用中，若搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，应该选择RB。

　　1.左神算法课（牛客2020算法基础提升班（10.10-11.10）_牛客网）

　　2.boboo老师的算法课（这篇文章提到过）：有没有好的学C++的视频教程推荐嘞！？