Java集合系列之哈希表【一】

在Java世界里，HashMap是相当相当的重要，而和HashMap有关的哈希表是个什么东西？

百科解释：

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

可以得知：

1. 哈希表其实也叫散列表，英文单词是Hash table
2. 哈希表是一个数据结构，可以根据一个key值来直接访问数据，因此查找速度快

在讨论哈希表之前，有必要先大概了解下其他数据结构在新增，查找等基础操作的执行性能

1. 数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
2. 线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
3. 二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

哈希表的本质

哈希表本质上是个数组，因为它的底层实现用到了数组。然后在数组的基础上加工加工，变得更加有特色了，然后就自立门户，叫哈希表。

一般实现哈希表可以采用两种方法：

1. 数组+链表
2. 数组+二叉树

无论哪个都必须有数组，比如第一种数组+链表的形式，其实是解决哈希冲突的一种方法，然后使用链表存放数据，所以综合起来就是使用数组+链表的方式来实现一个哈希表，另外数组中一般存放单一数据，而哈希表中存放的是一个键值对。

哈希函数

其实通俗的理解就是比如微信里的通讯录，里面有很多好友，而这些好友是有一个排列规则的，也就是根据名字的姓排序，然后根据名字进行排序，这样找某个好友的话可以快速定位。这个排序规则放到在哈希表中就是哈希函数。

键值对和Entry

对于哈希表，它经常存放的是一些键值对的数据，键值对就是我们经常说的key-value，简单点说就是一个值对应另外一个值，比如a对应b，那么a就是key，b是value，哈希表存放的就是这样的键值对，在哈希表中是通过哈希函数将一个值映射到另外一个值的，所以在哈希表中，a映射到b，a就叫做键值，而b呢？就叫做a的哈希值，也就是hash值。

比如上面的图中，好友的名字拼音和名字就是一个键值对，根据这个拼音就能找到名字。jdk中键值对就叫Entry。

哈希表如何存数据

以上面的图为例：数组长度是5，现在要把好友信息加到通讯录中，通过对key也就是名字拼音进行哈希函数计算后得到一个值1，这个1就是要存放到数组中的位置。而数组中的每个位置存放的是一个键值对。

哈希冲突

如图所示，现在有另外一个好友，经过哈希函数计算后，下标也是1，而1之前已经被张三占了，这种情况就是哈希冲突。

解决哈希冲突

哈希冲突的解决办法有好几种，其中两种方法，一个是开放寻址法，一个是拉链法。

1. 开放寻址法其实简单来说就是，既然位置被占了，那就另外再找个位置不就得了，怎么找其他的位置呢？这里其实也有很多的实现，我们说个最基本的就是既然当前位置被占用了，我们就看看该位置的后一个位置是否可用，也就是1的位置被占用了，我们就看看2的位置，如果没有被占用，那就放到这里呗，当然，也有可能2的位置也被占用了，那咱就继续往下找，看看3的位置，直到找到空位置。

   Java中的ThreadLocal就是利用了开放寻址法。

2. 拉链法也是比较常用的，HashMap就是使用了这种方法。和开放寻址法不同，还是在该位置，解决办法就是链表，这时候这个1的位置存放的不单单是之前的那个Entry了，此时的Entry还额外的保存了一个next指针，这个指针指向数组外的另外一个位置，将张尚安排在这里，然后张三那个Entry中的next指针就指向张尚的这个位置，也就是保存的这个位置的内存地址，如果还有冲突，那就把有冲突的那个Entry放在一个新位置上，然后张尚的Entry中的next指向它，这样就形成了一个链表。

拉链法会产生什么问题？

如果冲突过多的话，这块的链表会变得比较长，怎么处理呢？举个例子，拿java集合类中的HashMap来说，如果链表长度大于等于8的话，链表就会转换成树结构；如果长度小于等于6的话，就会还原链表。以此来解决链表过长导致的性能问题。

开放寻址法会产生什么问题？

有一定量的位置被占了的时候就会发生扩容

哈希表的扩容

其实不仅仅是因为有一定量的位置被占了的时候会发生扩容，还有一个很重要的原因就是当哈希表被占的位置比较多的时候，出现哈希冲突的概率也就变高了，所以很有必要进行扩容。

有一个负载因子的概念，简单点说就是已经被占的位置与总位置的一个百分比，比如一共十个位置，现在已经占了七个位置，就触发了扩容机制，因为它的负载因子是0.7，也就是达到了总位置的百分之七十就需要扩容。

拿HashMap来说，它当前的容量占总容量的百分之七十五的时候就需要扩容，而且这个扩容也不是简单的把数组扩大，而是新创建一个数组是原来的2倍（因为数组扩大了，所以一般哈希函数也会有变化），然后把原数组的所有Entry都重新Hash一遍放到新的数组。

哈希表读取数据

比如现在要通过zhangshang来查找好友。首先通过哈希函数利用zhangshang得出位置1，然后去位置1拿数据，拿到这个Entry之后我们得看看这个Entry的key是不是zhangshang，一看是zhangshan，这不是我们要的key，然后根据这个Entry的next找到下一给位置，再比较key，成功找到张尚。

开放寻址那种也是这个思路，先确定到这个位置，然后再看这个位置上的key是不是我们要的，如果不是就看看下一个位置。

写在最后

如果一个哈希函数设计的足够好的话，就会减少哈希冲突的概率，如果设计的不好，就会经常冲突，那就很影响性能了。在哈希表中，哈希函数的设计很重要，一个好的哈希函数可以极大的提升性能