算法知识学习-----哈希（哈希函数与哈希表）
哈希函数与哈希表
一般来说，在哈希函数中（hashfunction），用户会提供一个数据源（data），它可以是一个字符串或者其他类型的变量（variable）。随后将该数据作为输入传递给哈希函数（hashfunction(input)），它将通过一系列计算步骤生成其输出结果（outputresult）。这些输出结果通常是一个固定长度的字符串序列（stringsequence），每个字符占据一个字节的空间（byteofspace）。每一个字符的位置都遵循十六进制编码规则（hexadecimalencodingrules），具体来说是可以存储数字0到9以及字母A到F之间的字符（characters）。因此能够生成的总共有 16^{16} 种不同的值（values），这是一个极其庞大的数值范围（numericalrange）。而MD5加密算法正是基于这一原理设计而来，在实际应用中它会生成一个固定长度为32位十六进制字符串序列（stringsequence）。
他有几个性质：
无界域的概念在数学分析中非常重要。当我的输入是一个字符串时，理论上其规模可以无限制地扩大。因此，在实际处理中需要考虑这一特性。
② 输出是有限的 他已经设定好了范围就是在0-16^16的范围
③多次输入同一个参数，返回的输出也是同一个返回值
④ 赋予不同的参数值时可能会得到相同的返回结果 当输入的数据量远远超过输出的数据容量时 则必然会导致存在不同输入却产生相同输出的情况 这在密码学中被称为哈希碰撞
当输入数据量达到一定规模时，输出呈现均匀分布特征，在该范围内每个数值出现的概率大致相同（离散型）。
基于这个性质，他会有很多的应用，我们也可以概括出几个特征。
他的输出与其所依据的数据特性并无直接关联。例如，在分析以下三个特定的数值样本时：liming, liming1, liming2（经分析发现它们具有较高的相关性），但在执行哈希运算时可能会导致较大的差异，并且这些结果完全不相关。
一道例题：快速设计出100个哈希函数
首先, 哈希函数必须满足上述五个关键属性。 对于我们而言, 从零开始构建这样一个功能模块仍然面临较大的技术挑战。 然而, 如果我们转变思维, 可以采取以下策略: 我们可以从现有的成熟技术中汲取灵感, 比如市面上已经存在一系列经过优化的成品车, 我们可以考虑将其他车辆的部分配件整合到现有底盘上, 从而快速生成所需的功能模块。当然前提是确保所有参与构建的车辆均采用相同的底盘架构。
设置哈希算法遵循类似的思路，并已存在现成的实现方案。其中一种方案是使该算法生成的结果取自MD5算法生成字符串的前8个字符；另一种方案则是获取后8个字符作为独立的结果集合。此外还可以通过将两个结果进行组合运算来生成最终的哈希值
也可以通过以下方式来生成最终的混合哈希值：首先取输入数据的MD5编码值的前8位字符，并与另一个选定的哈希算法计算后的最后8位字符进行组合；随后将这些组合后的字符经过再次加密处理以获得最终的整体哈希结果；这种方法不仅能够提高计算效率还能确保数据完整性验证的安全性；即使是一百万次这样的计算也完全不在话下
哈希表
哈希表本质上是通过计算将输入数据映射到特定位置存储起来的一种数据结构。 HashMap正是利用了这一特性进行高效的数据存储和检索。 当使用一个较短的哈希表处理大量输入时, 多个数据会被映射到同一个位置, 导致查找操作的时间复杂度接近O(N)。
这里有两种解决办法：
采用红黑树结构进行替换后，则其查询效率将显著优于原来的链表。
对当前哈希表进行扩容相当于将哈希表的范围增大随后重新计算每个元素的哈希值并按照新的顺序进行排列。可能会有疑问是否进行了扩容之后再重新排列哈希表是否造成了较高的开销我们来做一个简单的估算假设每次扩展至原来的两倍最终扩展至N规模那么所需的总操作次数为log₂N这在性能上是非常高效的。
一道例题：
系统中存在一个容量为100T的大文件，并且该文件仅存储所有内容均为字符串。根据规定我们需要从数据中提取并记录所有重复出现的字符串。
假设一百台电脑可以用于处理当前应用
解决办法即是逐行读取字符串内容，并对每个数值应用哈希算法计算出结果并对结果取模100；他的数值必定落在0至99之间，请根据其所属编号将数据分配至相应服务器进行处理。
这仅解决了数据分发的问题，并未处理数据本身。将数据分配至各个电脑后，请问是如何完成后续处理工作的？具体来说是采用了哈希原理进行计算吗？我们需要明确的是，在此过程中我们采用了另一种哈希函数来重新计算每个 incoming 值，并将其存储于 HashMap 中。字符串被用作键值对的存储单位，并记录其出现频率。在 HashMap 中若某键的哈希值与当前一致，则记录该键出现的次数。若不同，则在该 hash 值对应的数组索引处将该字符串附加到对应链表尾部。