1.基本概念

1.1 散列表/哈希表（Hash table）& 散列函数

#概述
是根据键（Key）而直接访问在内存存储位置的数据结构。
它通过计算一个关于键值的映射函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。
这个映射函数称做散列函数，存放记录的数组称做散列表。

#抽象描述
若关键字为 k，则其值存放在f(k) 的存储位置上。由此，不需比较便可直接取得所查记录。
称这个对应关系 f(k) 为散列函数，按这个思想建立的表为散列表。

#Hash 冲突/ Hash 碰撞
对不同的关键字k可能得到同一散列地址，即 k1≠k2，而f(k1)=f(k2) ，这种现象称为冲突或碰撞(Collision)。
具有相同函数值的关键字对该散列函数来说称做同义词。
综上所述，根据散列函数f(k) 和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，
并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，
这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

#均匀散列函数（Uniform Hash function）
若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数，
这就使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

#关于散列表的一个例子
一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个
按照人名首字母顺序排列的表, 即建立人名 x 到首字母 f(x) 的一个函数关系，
在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。
这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则 f()，存放首字母的表对应散列表。
关键字和函数法则理论上可以任意确定。

1.2 概念澄清

#Hash表 的时间复杂度
Hash表基于数组等数据结构，通过把关键字映射到数组的某个下标来加快查找速度。
>> 数组、链表、树等数据结构中查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间级。
>> 对于哈希表来说，只是O(1)的时间级。

#哈希化 & 哈希函数
这里有个重要的问题就是如何把关键字转换为数组的下标，
这个转换的函数称为哈希函数（也称散列函数），转换的过程称为哈希化。

#哈希算法
>> 这类算法接受任意长度的二进制输入值，对输入值做换算，最终给出固定长度的二进制输出值；
>> 可应用与信息安全与数据存储领域。

#哈希表（Hash Table）
是一种数据结构。

#哈希函数
是支撑哈希表的一类函数。

#equals, hashCode方法
重写equals方法通常有必要也重写hashCode方法，要保证对象equals，hashCode必须相等！

1.3 构造散列函数的方法

散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。

>> 直接定址法：
取关键字或关键字的某个线性函数值为散列地址。
即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。

>> 数字分析法：
假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
假设某公司的员工登记表以员工的手机号作为关键字。
手机号一共11位。前3位是接入号，对应不同运营商的子品牌；中间4位表示归属地；最后4位是用户号。
不同手机号前7位相同的可能性很大，所以可以选择后4位作为散列地址，
或者对后4位反转（1234 -> 4321）、循环右移（1234 -> 4123）、循环左移等等之后作为散列地址。
数字分析法通常适合处理关键字位数比较大的情况，
如果事先知道关键字的分布且关键字的若干位分布比较均匀，就可以考虑这个方法。

>> 平方取中法：
取关键字平方后的中间几位为哈希地址。
假设关键字是1234、平方之后是1522756、再抽取中间3位227，用作散列地址。
平方取中法比较适合于不知道关键字的分布，而位数又不是很大的情况。

>> 折叠法：
将关键字从左到右分割成位数相等的几部分，最后一部分位数不够时可以短些，
然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如关键字是9876543210，散列表表长是3位，将其分为四组，然后叠加求和：
987 + 654 + 321 + 0 = 1962，取后3位962作为散列地址。
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

>> 除留余数法：
f(key) = key mod p (p≤m)，m为散列表长。
这种方法不仅可以对关键字直接取模，也可在折叠、平方取中后再取模。
根据经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数，可以更好的减小冲突。
此方法为最常用的构造散列函数方法。

>> 随机数法
f(key) = random(key)，这里random是随机函数。
当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

#散列函数选取策略
实际应用中，应该视不同的情况采用不同的散列函数。
如果关键字是英文字符、中文字符、各种各样的符号，都可以转换为某种数字来处理，比如其unicode编码。
下面这些因素可以作为选取散列函数的参考：
（1）计算散列地址所需的时间；
（2）关键字长度；
（3）散列表大小；
（4）关键字的分布情况；
（5）查找记录的频率。

1.4 Hash冲突/碰撞的解决思路

1.4.1 开放寻址法(open addressing)

开发地址法的做法是，当冲突发生时，使用某种探测算法在散列表中寻找下一个空的散列地址，
只要散列表足够大，空的散列地址总能找到。按照探测序列的方法，一般将开放地址法区分为
>> 线性探查法
>> 二次探查法
>> 伪随机探测再散列
这些方法都不能实现一致散列，因为它们能产生的不同探查序列数都不超过 m^2 个（一致散列要求有 m! 个探查序列）。
在这三种方法中，双重散列能产生的探查序列数最多，因而能给出最好的结果。

#Hash表的大小选择问题
表的大小选取至关重要，此处选取10作为大小，发生冲突的几率就比选择质数11作为大小的可能性大。
越是'质数'，mod取余就越可能均匀分布在表的各处。

#避免聚集
聚集（Cluster，也翻译做“堆积”）的意思是，在函数地址的表中，
散列函数的结果不均匀地占据表的单元，形成区块，
造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），
散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。
对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。

1.4.1.1 线性探测法

假设Hash表为values, 此时采用取 x % 10的方法插入values中. 
此时要插入一个数字是28. 如果发现 values[8] 已经被占用了，
就看看 values[9] 是否空着，如果 values[9] 也被占用了，就看看 values[0] 是不是还空着。

完整的描述是，先使用 F(x) 函数获取 k 的第一个地址，如果这个地址已被占用，
就探查下一个紧挨着的地址，如果还是不能用，就探查下一个紧挨着的地址，
如果到达了数组的末尾，就卷绕到数组的开头，如果探查了 m 次还是没有找到空槽，
就说明数组已经满了，此时扩容. 这就是线性探查（linear probing）

#缺点：
需要不断处理冲突，无论是存入还是査找效率都会大大降低。

线性探测法解决Hash冲突.png

1.4.1.2 二次探测再散列

这里只分析插入, 删除和查找, 可参考线性探测法自行分析即可

二次探查法解决Hash冲突.png

1.4.1.3 伪随机探测再散列

这里只分析插入, 删除和查找, 可参考线性探测法自行分析即可

伪随机探测再散列解决Hash冲突.png

1.4.2 再哈希法

这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。
这种方法不易产生聚集，但增加了计算时间。

1.4.3 链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，
并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。

链地址法适用于经常进行插入和删除的情况。
如果查找比较频繁, 可将其改为'红黑树'。

链地址法解决Hash冲突.png

Hash表的性能问题

哈希表的特性决定了其高效的性能，大多数情况下查找或者插入元素的时间复杂度可以达到O(1)， 时间主要花在计算hash值上。

然而也有一些极端的情况，最坏的就是hash值全都映射在同一个地址上，这样哈希表就会退化成链表, 如下图Figure2.
当hash表变成图2的情况时，时间复杂度会变为O(n)，效率瞬间低下，
所以，设计一个好的哈希表尤其重要，如HashMap在jdk1.8后引入的红黑树结构就很好的解决了这种情况。

Hash表性能.png

1.5 一致性Hash

一致性哈希算法是在哈希算法基础上提出的，在动态变化的分布式环境中，哈希算法应该满足的几个条件:
>> 平衡性
是指hash的结果应该平均分配到各个节点，这样从算法上解决了负载均衡问题。
>> 单调性
是指在新增或者删减节点时，不影响系统正常运行。
>> 分散性
是指数据应该分散地存放在分布式集群中的各个节点(节点自己可以有备份)，不必每个节点都存储所有的数据。

http://www.zsythink.net/archives/1182 (一致性Hash)

2.实际应用

2.1 常见应用

#1.数据校验 (MD系列, SHA系列)
#2.唯一标识
比如说, 现在有十万个文件, 给你一个文件, 要你在这十万个文件中查找是否存在. 
可以用哈希算法对文件进行计算, 然后比较哈希值是否相同. 
因为存在哈希冲突的情况, 你可以在相同哈希值的文件再进行二进制串比较.
#3.哈希表
#4.负载均衡
比如说, 现在有多台服务器, 来了一个请求, 如何确定这个请求应该路由到哪个路由器呢?
当然, 必须确保相同的请求经过路由到达同一个服务器. 
一种办法就是保存一张路由关系的表, 比如客户端IP和服务器编号的映射, 但是如果客户端很多, 势必查找的时间会很长. 
这时, 可以将客户端的唯一标识信息(如:IP、username等)进行哈希计算, 然后与服务器个数取模, 得到的就是服务器的编号.
#5.分布式存储
当我们有大量数据时, 一般会选择将数据存储到多个服务器, 为了提高读取与写入的速度. 
决定将文件存储到哪台服务器, 就可以通过哈希算法取模的操作来得到.

2.2 JDK 的 HashMap 等集合类容器

3.一些问题

3.1 为什么重写Equals方法时一定要重写hashCode方法

// hashCode():
HashCode是object类的一个方法，用来生成该对象的hashCode值，
是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值, 
public int hashCode()返回该对象的哈希码值。
主要为了提高set,map, (注意这里没有list)这些集合的查询效率。
当我们将一个新对象放到set,map,hashTable集合中时，会先获取这个对象的hashCode值，
如果集合中已经存在该值，再获取该值对应的链表，
如果链表中有该元素则更新，没有则创建一个新值在链表中。
所以hashCode在上面扮演的角色为寻域（寻找某个对象在集合中区域位置）。

// equals():
Equals 是object类的一个方法，用来判读二个对象是否相同（是否指向相同的引用）。
如果需要通知指定的值来判断二个对象是否相等，需要我们自己手动去覆盖这个方法。
如String类的Equals方法就是重写了的。

// 重写Equals与HashCode的原则
这二个方法本来是Object中相对独立的二个函数，并没有什么相互的依赖。
但是在HashTable,HashMap的集合中，HashCode和Equals就有了依赖性。
向HashTable,HashMap中添加新元素时，会先获取该元素的Hash值，
HashCode()的作用就是保证对象返回唯一hash值，但当两个对象计算值一样时，这就发生了碰撞冲突。
如果Hash值冲突了，那就获取该域（集合中发生冲突的位置）上的对象链，
再通过Equals来判断是否该链表上已经存在该元素，
若不存在则使用头插法插入新结点，若存在则把value值覆盖。
>> hashCode值相同，equals并不一定相同
>> Equals相同，则hashCode一定相同
>> 所以，我们在重写Equals方法时一定要重写hashCode方法

    @Test
    public void fn04() {
        Map<Person, Integer> people = new HashMap<>();
        Person tom1 = new Person(1, "tom");
        Person tom2 = new Person(1, "tom");
        people.put(tom1, 1);
        people.put(tom2, 1);
        System.out.println(people); // {Demo.Person(id=1, name=tom)=1, Demo.Person(id=1, name=tom)=1}

        Map<Stu, Integer> stus = new HashMap<>();
        Stu jerry1 = new Stu(2, "jerry");
        Stu jerry2 = new Stu(2, "jerry");
        stus.put(jerry1, 1);
        stus.put(jerry2, 2);
        System.out.println(stus); // {Demo.Stu(id=2, name=jerry)=2}
    }
    @Getter
    @Setter
    @ToString
    @AllArgsConstructor
    private class Person { // Person类未重写 hashCode 与 equals 方法
        private Integer id;
        private String name;
    }
    @Data
    @AllArgsConstructor
    private class Stu { // Stu类重写了 hashCode 与 equals 方法
        private Integer id;
        private String name;
    }

参考资料