Java面试向：脑图啥是哈希
来同学，你给我讲一下什么是嘻哈，哦不对，哈希。
一般碰到这种随便聊一聊风格的面试官，考验你运气的时刻到了，你要是回答不到正确答案上面，呵呵。
这个时候，你只好系统地全面地解答，最后还要举例说明，啥是哈希。
先放脑图：百度脑图
脑图截图
首先，与Java语言无关的，数据结构层面上的哈希表是什么？
哈希表是通过定义一个哈希函数和一个冲突解决方法，将关键字（key）映射到一个有限区间的地址上的一种数据结构。并将关键字关联的值（value）存储在这个地址上，就构成了一个使用key来查找value的哈希表。
- 有限地址区间：通常用数组实现，由于数组的内存是连续的，因此可以快速地通过偏移量，也就是数组中的下标来快速地访问到元素。
- 哈希函数：是设计一个哈希表的关键，它输入一个关键字，输出一个数组的下标，也就是连续地址中的地址。并没有对所有类型的关键字都通用的一个哈希函数，每种类型的关键字，甚至同一种关键字在不同的场景下都需要独立设计哈希函数。
- Java中内置的类型都提供了哈希函数的默认实现，其中最常用的可能就是String了，它的哈希函数一般情况下可以直接使用。
- 合适的哈希函数是哈希表高效查找的关键，主要的影响因素是映射方法，好的映射方法有以下几个特点：映射到的地址分布均匀，也就是说不会产生大量的连续空地址导致空间浪费；产生的冲突少，也就是不同的key映射到相同地址的概率小，因为解决冲突也会影响效率；计算速度快，哈希函数本身的计算速度不能太慢。
- 冲突解决方法：冲突发生在插入新的键值时。由于key的取值范围一般情况下都比映射地址空间要大，因此理论上无法阻止不同的key映射到相同的地址上。反过来讲，如果一段连续的地址空间可以存储所有的关键字，那就没必要用哈希表了。一旦映射到了同样的地址上，就需要解决冲突，否则就会覆盖掉之前的映射关系，产生错误。
- 冲突解决方法是通用的，可以选择某种方法来解决冲突。冲突解决方法可以分为两类，一类是在数组中再找一个位置保存，另一类是在额外的空间中保存。Java中的HashMap是使用额外的空间来保存的。
然后，在Java中如何使用HashMap，如何定义自己的哈希
Java中的HashMap使用泛型来定义，有两个类型参数，一个是键，一个是值。public class HashMap<K,V> HashMap只是一个容器，提供了哈希函数调用的框架以及冲突解决方法，并没有定义哈希函数本身。因此需要定义哈希函数才能有效使用HashMap。
在Java语言中，除基本类型外，所有类都继承自Object，Object类提供了很多通用方法，其中就包括哈希函数 public int hashCode()。也就是说，在Java中每个对象都会有一个哈希函数，如果没有重写，那么就使用Object类提供的默认实现。很明显，这个哈希函数的输入是这个对象自身。但哈希函数的输出是一个任意整数，并不是一个有限区间，那么HashMap是怎么做到将其映射到有限区间的呢？
在HashMap内部会维护一个表，也就是一个数组（有限连续地址区间），HashMap并不需要由外部定义这个数组的大小，而是使用内部的规则自动扩展。这样外部并不知道这个数组的大小，因此也无法根据这个大小，也不应该根据这个大小来计算哈希值。所以外部提供的 hashCode() 方法返回的任意整数就有了意义，可以适应任意大小的表大小（当然不能超过int取值范围），只需要计算一下 hashCode() % N 其中 N 是表大小，就可以得到数组的索引。
有趣的是，HashMap规定这个数组的大小始终都是2的幂，这个设置使模除运算变成了位运算，也就是当X是2的幂时， (X % N) == (X & (N - 1)) 。
Object类提供的 hashCode() 方法默认是返回对象的内存地址转换成的整数，显然这个哈希函数不怎么样。所以一个类如果有做关键字的需求，就要重写这个方法。以下是重写这个方法的原则：
- 一致性：无论什么时候对同一个对象多次调用
hashCode()，都必须返回同样的值。 - 相等性：如果两个对象通过
equals()方法判断为相等，那么hashCode()方法必须返回相同的值。 - 可等性：如果两个对象通过
equals()方法判断为不相等，并不要求hashCode()返回不相等的值，也就是允许冲突。当然，冲突越少越好。
上述性质中多次提到了 equals() 方法，也是 Object 类提供的通用方法之一：boolean equals(Object obj)，如果想要 hasCode() 正常工作，那么同时 equals() 方法也要满足以上提到的性质。
最常用做关键字的类型非 String 莫属，它的 hashCode() 和 equals() 方法是重写的，源代码如下：
public int hashCode() {
int h = hash; // 这个hash变量是一个缓存字段，为了不重复计算。
final int len = length();
if (h == 0 && len > 0) {
for (int i = 0; i < len; i++) {
h = 31 * h + charAt(i);
}
hash = h; // 计算后存入缓存。
}
return h;
}
public boolean equals(Object anObject) {
if (this == anObject) { // 快速判断自己和自己比较
return true;
}
if (anObject instanceof String) { // 不是String类型直接判断为不等
String anotherString = (String)anObject;
int n = length();
if (n == anotherString.length()) { // 再判断长度
int i = 0;
while (n-- != 0) {
if (charAt(i) != anotherString.charAt(i)) // 判断每个字符
return false;
i++;
}
return true;
}
}
return false;
}
可以看出 hashCode() 的计算跟每一个字符都有关系，而且跟字符的位置也有关系，并且只与所有字符有关；而 equals() 的计算同样也是只判断字符，判断所有字符，且与位置相关。因此 String 类满足上面所述的前两个性质。至于第三个性质好不好，取决于神秘数字31，具体原因可以参考这篇文章：传送门=>走你
拜拜，煮面时顺溜
参考文章：
https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode--
https://blog.csdn.net/bingyu880101/article/details/49866131
https://blog.csdn.net/reggergdsg/article/details/53819293
https://segmentfault.com/a/1190000010799123
https://blog.csdn.net/zhengchao1991/article/details/78916471
https://blog.csdn.net/u012104435/article/details/47951357
https://www.cnblogs.com/chinajava/p/5808416.html
