哈希函数和哈希表

哈希函数和哈希表

• 哈希函数的特点在于其高效的键值存储与快速查找能力。
• 在计算机科学领域中广泛采用的一种数据存储结构被称为哈希表。
• 总结部分需要重点阐述各知识点间的联系及其实际应用价值。
• 哈希函数的主要缺点包括固定散列冲突的可能性以及较为复杂的实现过程。
• 在实际应用中，哈希表常用于实现高效的数据库查询系统及分布式缓存网络等场景。
• 红黑树作为一种平衡二叉搜索树，在数据结构领域具有重要地位。
• 对比分析红黑树与哈希表的技术特点及其适用场景时需特别关注两者的优劣势对比点。
• 在Java语言环境中，HashMap是否是有序的数据结构？
  在Java中为何HashMap被视为线程不安全的数据结构？

哈希函数特点：

哈希函数特点：

1. 其输入呈无限增长趋势。
2. 对于相同输入的一次又一次执行均会产出一致结果。
3. 尽管如此，在某些情况下不同的输入仍可能导致相同的结果（即出现所谓的哈希冲突或称作碰撞现象）。
4. 可以说该算法的设计理念在于确保其处理结果具有高度确定性：无论数据来源如何分散或集中（即同一处理区域在不同空间位置上的样本处理效果相当），从而最大限度地减少了不确定性带来的影响。

对于任一数值对某个整数取模运算后所得的结果必定处于从零到该整数减一的区间内。例如任意数值对一百进行取余运算后所得结果必然是位于零至九十九之间的某个整数值。这种结果呈现完全均匀的概率分布特性。

哈希函数不需要担心遇到多个重复数字的问题，因为它能够将这些数字映射到同一个哈希值中。

主要作用在于用于实现哈希表的第一步数组查询。通过取模操作使用（利用）哈希函数来确定对应的位置。这一步的时间复杂度为O(1), 其时间效率极高。

哈希表

主要作用：加快查找速度。可以近似看成O（1）.

时间复杂度：
在哈希表中进行增删改取等基本操作所需的时间复杂度为O(1)；尽管在扩容时所需要的时间复杂度达到O(\log n)。

一个原因是实际使用的工程数据量通常处于较低程度，另一个原因是离线技术避免了在用户使用时产生时间上的占用。

总结：

哈希函数特征：

    1.与输入规律无关；2.哈希函数生成16位的码每一位都是相互独立的（因此利用一个哈希函数可造出很多哈希函数）

    
    
        
    代码解释

Hash table的基本操作时间复杂度被视为O(1)，其中容量扩展的时间计算结果基于logₙN（此处n表示倍增因子）。这种情况下，默认将容量扩展视为不影响整体时间效率。

Hash table的基本操作时间复杂度被视为O(1)，其中容量扩展的时间计算结果基于logₙN（此处n表示倍增因子）。这种情况下，默认将容量扩展视为不影响整体时间效率。

利用哈希函数做分流，处理大数据问题

哈希函数的缺点：

随着数据量的增加，在哈希表中发生碰撞的风险也随之提升。针对碰撞问题，哈希表主要采用两种解决策略：第一种是线性探测法，在发生碰撞时将冲突单元组织为单链表结构；这种情况下这些操作的时间复杂度可能达到O(n)，可能导致额外的空间需求。另一种常见的解决策略是开放寻址法，在这种情况下其时间复杂度同样可能达到O(n)，尤其是在极端情况下。

建议在创建哈希表之前先估算输入数据的规模。如果不预先估算输入数据的数量，则会使得哈希表的 resize 过程变得耗时且低效。例如，在现有哈希表长度为100的情况下插入第101个元素时, 不仅需要扩大空间至至少150, 并且所有已存在的键都需要重新进行计算以适应新空间规模

3.哈希表中的元素未被排序。但是，在某些情况下，我们希望所存储的数据具有有序性。

哈希表的应用场景：

在C++语言中，unordered_map和unordered_set均采用红黑树作为基础数据结构。哈希表适用于对查找性能有较高需求且数据元素间无需考虑逻辑关系的情况。例如，在文件校验和数字签名等方面具有显著应用价值。此外，在快速查询功能方面也展现了其独特优势。

红黑树：

主要功能是用于存储有序序列。该数据结构在增删改查操作上的时间复杂度均为O(logn)。那么使用迭代器遍历一棵红黑树的时间复杂度是多少？ 红黑树本质上是一种平衡二叉搜索树（AVL），因此其根节点总是小于左子树而大于右子树。它的其他特性则基于这种自我平衡机制。

传统的二分查找法存在局限性：它无法有效处理大规模数据集以及非数值型数据。因此，在面对大规模数据以及非数字类型的数据时，人们开发出了二分查找树这一改进方案。然而，在这种结构中可能出现单链表情况而导致的不平衡问题促使我们引入AVL树技术。 AVL树通过旋转操作实现高度平衡。尽管这种结构在维护绝对平衡方面表现优异，但其频繁的操作（如插入和删除）都会对性能产生显著影响。因此，在追求更高效率的目标下进行了进一步优化：牺牲了一定的查找速度以换取更快的删除操作速度。

RB-Tree是多维度考量下的综合权衡。
总结可知：在实际应用中，如果搜索操作远超插入和删除操作，则建议选用AVL树；相反地，在搜索与插入/删除频率较为均衡的情况下，则更适合采用红黑树。

应用场景：C++中如map和set都是用红黑树实现的 。

红黑树和哈希表的比较

map和unordered_map的底层数据结构分别为红黑树和哈希表……尽管哈希表在查询效率上更具优势……为何还要采用红黑树？hashmap包含unordered_map吗？其实map本质上就是一种明确实现的红黑树。它的主要优势在于：除了上述核心功能特点外……它在数据访问顺序上提供了严格保证……这种有序性在很多应用场景中非常有用。

2.时间复杂度指标显示，红黑树在插入、删除和查找操作上的表现均为O(logN)级别。相比之下，在稳定性框架下运行的理想状态中，哈希表实现的插入、删除及查找操作均能达到理论上的最优效率（O(1)）。然而，在最差情况下仍具备高效性。值得注意的是，在无冲突的情况下（即理想状态），哈希表的操作效率得以维持在最佳水平；但一旦出现冲突，在极端情况下（如满载），其插入与删除操作的时间复杂度可能降至O(n)水平。

3. map支持定位操作 ，而unordered_map无法进行范围查找。
   4. 容量扩展因容量扩展而导致迭代器失效。\n\n如果一个 iterator 所指的位置没有被删除，则该(iterator)将永远有效。\n\nThe iterators of an unordered_map may become invalid when the underlying data structure is modified.

4. 基于上述分析可知，在3的情况下对map的操作不仅可以实现遍历还可以与修改操作在一定程度上并行进行（这种程度上的不一致性通常是可以接受的），而对于unordered_map则需要特别注意以防止修改操作影响其iterator的有效性；为了避免在unordered_map中的迭代操作因修改而产生不可预测的影响，在实际应用中应采取相应的措施以确保数据结构的一致性和功能完整性；从而使得可以在当前map中快速找到刚好大于或刚好小于某个特定key的值；这些功能仅存在于std::map中而不在std::unordered_map中

关于第二部分关于时间复杂度的讨论中提到了红黑树和哈希表的表现比较。其中红黑树在插入、删除和查找操作中的时间复杂度均为O(logN)，而哈希表在插入、删除和查找操作中的理论时间复杂度均为O(1)。在这一对比中可以看出红黑树性能远没有哈希表优秀。值得注意的是相对于稳定的红黑树而言无论是在最好情况还是最坏情况下都能维持较高的效率。而在哈希表这种数据结构中假设不发生碰撞的情况下插入和删除操作的时间复杂度是常数时间的然而一旦发生碰撞其表现可能会有所下降进而导致 worst-case 时间复杂度达到 O(n) 的情况出现。因此在一般应用中选择一个相对稳定且效率较高的数据结构更为理想

HashMap是有序的还是无序的？

 HashMap的数据结构：数组+单链表，当存在hashCode相同的不同对象时，会将value以单链表的形式，往后增加。数组加快访问速度，单链表解决hash值冲突。
 调用put方法时，发生了什么：根据key的hashCode,计算出将key放入数组的index下标，index=(数组长度-1)&hashCode
 HashMap循环遍历的顺序：根据数组顺序+单链表顺序进行输出。
虽然遍历时，用的EntrySet,但是可以简单理解为，两层循环输出数据，外层循环为遍历数组，内层循环为遍历单链表。
 HashMap在初始化时，默认初始变量为16，以及默认的扩容因子为0.75

结论

当两个Map实例的容量设置不同时，在同时插入相同的键值对时...

再结论

代码遵循统一规范具有重要意义，在实际应用中应当依据需求选择合适的存储结构以满足特定功能需求。建议采用LinkedHashMap实现基于键值有序性的功能需求。具体而言，Java中的HashMap依据哈希码值计算存储位置，并不具备自动维持数据输入顺序的能力；为了避免期望Hashmap中数据存储顺序与输入数据插入顺序一致的问题，则应选择LinkedHashMap对象进行实现。具体来说，在实际应用中应当依据需求选择合适的存储结构以满足特定功能需求。建议采用LinkedHashMap实现基于键值有序性的功能需求。具体而言，在实际应用中应当依据需求选择合适的存储结构以满足特定功能需求；在实际应用中应当依据需求选择合适的存储结构以满足特定功能需求；在实际应用中应当依据需求选择合适的存储结构以满足特定功能需求；在实际应用中应当依据需求选择合适的存储结构以满足特定功能需求；在实际应用中应当依据需求选择合适的存储结构以满足特定功能需求；在实际应用中应当依据需求选择合适的存储结构以满足特定功能需求

HashMap 为啥线程不安全？

（1）HashMap 不是一个线程安全的容器，不安全性体现在多线程并发对 HashMap 进行 put 操作 上。
如果有两个线程 A 和 B ，首先 A 希望插入一个键值对到 HashMap 中，在决定好插入的位置（桶）的位置进行 put 时，此时 A 的时间片正好用完了，
轮到 B 运行，B 运行后执行和 A 一样的操作，只不过 B 成功把键值对插入进去了。
如果 A 和 B 插入的位置(桶)是一样的，那么线程 A 继续执行后就会覆盖 B 的记录，造成了数据不一致 问题。
（2）还有一点在于 HashMap 在扩容 时，因 resize 方法会形成环，造成死循环，导致 CPU 飙高