Hash（哈希）相关知识（哈希函数、哈希查找）

Hash（哈希）相关知识

• 前言
• 一. 哈希函数
• • 1. 函数特性
  • • 1.1 基本的哈希函数
    • 1.2 加密的哈希函数
  • 2. 常见的哈希函数构造法
  • • 2.1 直接寻址法
    • 2.2 数字分析法
    • 2.3 平方取中法
    • 2.4 折叠法
    • 2.5 随机数法
    • 2.6 除留余数法
    • 2.7 加密哈希函数
  • 3. 哈希函数总结
• 二. 哈希查找
• • 1. 操作步骤
  • 2.哈希表的查找
  • • 2.1 哈希冲突
    • • 2.1.1 开放寻址法
      • 2.1.2 链地址法
      • 2.1.3 再散列法
      • 2.1.4 建立公共溢出区
    • 2.2 装填因子
• 三. 总结

前言

• 因为本人是小白(小菜鸡)，所以有些地方说的可能不是很准确，大家可以参考一些很厉害的博主，在评论区指出我写的不对的地方。
• 本来是想要单独写一下Hash(哈希)查找算法，但后来想到Java和区块链的入门里面都涉及到Hash，所以就说一下自己对Hash的理解。
• 在写的过程中，有涉及到密码学的相关概念，我尽力用举例子的方式让读者明白，如果觉得我有哪里说的不准确，可以查找相关文献进行更深层次的理解，以免我误人子弟，顺便谢谢大家啦！

一. 哈希函数

1. 函数特性

1.1 基本的哈希函数

• 哈希函数是一个数学函数，特性有下面三点：
• 其输入可为任意大小的字符串。
• 它产生固定大小的输出。
• 它能进行有效的计算，就是说对于特定的输入字符串，在合理时间内，能够计算出哈希函数的输出，对n位的字符串，哈希值计算的复杂度是O(n)。

1.2 加密的哈希函数

• 主要有附加的三个特性(相关文字说明源于BITCOIN AND CRYPTOCURRENCY TECHNOLOGIES 区块链技术驱动金融-数字货币与智能合约技术)：
• 碰撞阻力：对于两个不同的输入，能够产生相同的输出，就像y=x2，key1≠key2，但是产生了H(key1)=H(key2)。实际上世界上根本不存在具有防碰撞特性的哈希函数，现在技术上所用的加密哈希函数只不过是还没有找到碰撞的函数，就像之前人们都用的MD5，在前几年找到了碰撞后就逐渐淡出市场。
• 隐秘性：如果我们无法通过输出y=H(x)来找到输入x，那么就保证了隐秘性。但要满足这样条件的x必须取自一个非常大的集合，否则x将很容易就被获取。例如，我们抛硬币，只需要知道结果就很容易穷举出x的确定值。
• 谜题友好：这个特性听起来是人畜无害的，其实用我的话来解释就是盲目的穷举一个巨大无比的数据集，而要求是要找到一个小区域内的值。用人话来说就是，给你一个地球这么大的区域，让你通过穷举来寻找你家小区或者一个超市或者一个城市的区域，这个所要寻找的区域往往越小，难度越高(正常人都能看出来)。而这个谜题取自哪里也非常重要，谜题往往取自高阶最小熵分布，这样就保证了没有捷径能走。

2. 常见的哈希函数构造法

• 相信大家都接触过数据结构，在那里面讲到过很多种构建哈希函数的方法和存储方式，咱也列举一下(有的是复制粘贴的，因为在数据结构中都有讲到)。
• 百度词条：哈希表和相应问题处理方法

2.1 直接寻址法

• 取关键字或关键字的某个线性函数值为散列地址。即hash(k) = k 或 hash(k) = a · k + b，其中a、b为常数(这种散列函数叫做自身函数)。

2.2 数字分析法

• 这种方法是对重复性比较高的位进行查找，然后多选几位组成哈希地址，避免冲突增加。

2.3 平方取中法

• 取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

2.4 折叠法

• 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。

2.5 随机数法

• 选择一个随机函数，取关键字的随机函数值作为它的哈希地址，即H(key)=random(key)，其中random为随机函数。通常用于关键字长度不等时的场合。

2.6 除留余数法

• 取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H(key)=key MOD p(p<=m)。
• 不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。

2.7 加密哈希函数

• 这里介绍安全哈希算法(SHA - 256),主要是被比特币采用的哈希函数。
• 与它相关的概念叫压缩函数(compression function)。在通用术语中，将接受固定长度的哈希函数转化为可接受任意长度输入的哈希函数，这种转换过程叫MD(Merkle-Damgard)变换。一般来说这种基础型，可用于固定长度，并且具备碰撞阻力的哈希函数就是压缩函数。
• SHA - 256就是利用了压缩函数将一个768位的输入压缩成256位的输出，每一个区块的大小是512位。
• 对于以上所说的知识，可以在百度上搜，或者看区块链的书。

3. 哈希函数总结

• 哈希函数并不是越复杂越好，而是根据需求进行设计和使用，因为哈希函数越复杂，时间消耗越长，对性能也有一定的影响。

二. 哈希查找

1. 操作步骤

• 用给定的哈希函数构造哈希表。
• 根据选择的冲突处理方法解决地址冲突。
• 在哈希表的基础上执行哈希查找。

2.哈希表的查找

• 哈希表的查找效率主要取决于哈希函数的构造方式、处理冲突的方式和装填因子。

2.1 哈希冲突

• 其实原理就是上面讲的碰撞，为了处理冲突，有这几种处理方法：
• 百度词条：哈希查找，这里面讲的还可以，有资源的可以在网上找具体操作，当然数据结构中的hash也讲过这几个方法，可以去找课件和书。

• 

2.1.1 开放寻址法

• 如果产生冲突，就找个空地址塞进去，当然要保证散列地址足够大。
• 这种方法细分为3种，分别是线性探测再散列、二次探测再散列、伪随机探测再散列，详细的设计方法和原理在上面的链接里也有。

2.1.2 链地址法

• 将所有同关键字的记录存储在一个单链表中，称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。
• 这种方法有点像用链表构成树。

2.1.3 再散列法

• 提前准备多个散列函数，如果其中一个找不到合适的位置，那就换一个散列函数。

2.1.4 建立公共溢出区

• 粗暴方式，只要发生冲突就填进公共溢出区。

2.2 装填因子

• 散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度
• α是散列表装满程度的标志因子。
• 由于表长是定值，α与填入表中的元素个数成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
• 实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

三. 总结

• HashMap就是由数组+链表组合成的，也就是链地址法，在这篇里主要讲的就是哈希相关的东西，HashMap改天再说。
• 哈希函数的构造不是越复杂越好，合适就行了，因为不同的应用由不同的需求，根据需求选择合适的结构就行了，性能方面也要考虑，例如HashMap只要尽量的减少它的链表就能提高它执行的性能。