扫盲，那些让人蛋疼的Hash概念

声明：本文首发微信公众号【菜鸟要飞】，如有转载，请标明出处！

今天分享的内容纯粹是概念和基本原理层次上的介绍，也是我在学习HashMap的源码时在一些专业术语上混淆，简单总结一下分享给大家。

Hash算法

概念

Hash算法是这样一类算法，这类算法接受任意长度的二进制输入值，对输入值做换算（切碎），最终给出固定长度的二进制输出值。哈希算法是用来解决数据和数据之间对应关系的一种算法。

应用

1、安全方面。加密算法，如MD5算法。

2、快速查找。例如运用一种哈希算法将每张图片映射出唯一的MD5值，实现快速以图搜图的功能。

3、数据结构。具体表现就是哈希算法在哈希表中的应用。说起哈希表这里又要提到另外一个概念——哈希函数，是支撑哈希表的一类函数。通过哈希函数，实现数据映射，使得哈希表实现对数据快速存取的功能。个人认为哈希函数和哈希算法是指的同一个概念。

哈希表

首先哈希表是一种数据结构。常见的数据结构还有数组，链表，树，图等。

概念

元素存储在线性表、树这种数据结构的存储地址是随机的，和元素之间不存在确定关系。因此，在这样的数据结构中查找某个元素时需要进行一系列和元素的比较。数组采用一段连续的存储地址来存储数据，元素和下标之间有对应关系，但如果不知道元素的具体下标，在查找元素时还是要经过一系列的比较。这一类查找方法建立在比较的基础上。最大的缺点就是慢！

哈希表则利用了在数组中根据下标就可以一次定位到某个元素的特性。哈希表在存储地址和元素的关键字之间建立一个确定的关系f

存储地址 = f(关键字)；

使的每个元素和数据结构中一个唯一的存储地址相对应。因而在查找时，首先利用元素的关键字和确定关系f找到元素的存储地址，进而一次定位到某个元素，不需要比较便可直接获取。

在此，我们称这个对应关系f为：哈希(Hash)函数，按这个思想建立的映射关系表为：哈希表。

哈希函数

哈希函数，是哈希表的支撑。是哈希表中存储地址和存储元素的关键字之间映射关系的具体实现。这里强调一下，它是一类算法，并不是某一个。

哈希函数常用的实现方法有直接寻址法，数字分析法，平方取中法、随机数法、除留取余法等待，有兴趣的自己查一查。

哈希冲突

哈希冲突是指，在哈希表中当我们对某个元素的关键字经过哈希函数运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，就是所谓的哈希冲突。我们需要清楚的是，哈希表的存储空间是一个数组，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。

冲突只能尽量地少，而不能完全避免。常见的解决哈希冲突的方法：链地址法，再哈希法、开放定址法、公共溢出区。

所以在实现哈希表这种数据结构时，要设定一个好的哈希函数，尽可能地保证计算简单和散列地址分布均匀，尽量减少冲突；还要必须设定一种处理哈希冲突的方法。

个人理解哈希表就是：哈希(Hash)函数+ 数组 + 哈希冲突的处理

HashMap

HashMap是Java JDK提供的一种数据类型，是基于数组来实现哈希表，进行数据的存储。

先看一张HashMap原理实现图

首先要重点说明一下，HashMap中的元素指的是Entry对象，并不是调用HashMap的put方法时传入的value。Entry对象它自身又是个链表，这个对象包含key（关键字）、value、next(链表)、hash（存储地址）四个成员，其中key和value是在调用HashMap的put方法时传入的。

这里要强调一下，HashMap中的哈希函数 ，并不是 key到value的映射。在使用习惯上，很容易让人误解HashMap中哈希表的实现就是 key到value的映射，其实是Entry（元素）、  key （关键字）和数组index(存储地址)之间的映射。

我们可以结合上面哈希表的定义类比一下：

HashMap中的数组相当于元素也就是Entry对象的存储空间，数组的index就像相当于元素的地址，而key相当于元素的关键字。

哈希函数 就可抽象为

index = f(key),这里的key 就是平常调用HashMap put方法时传入的参数key。

在HashMap中哈希函数的具体实现就是 

f(key) = key.hashCode() & (table.length - 1);

HashMap中的链表就是用来处理哈希冲突的，也就是上面提到的链地址法。具体实现大家可以查阅资料或源码，这里不做深入探讨。

最后

提到HashMap和hashCode()方法，一定就少不了equals方法。重写equals方法时为什么一定要重写hashCode()方法，真的一定要重写吗？ 这将是下次分享的内容。

欢迎关注我的公众号：【菜鸟要飞】 ，面试宝典、学习路线、源码分享等等你来学