本文共 3197 字，大约阅读时间需要 10 分钟。

HashMap概述

哈希表也称为散列表，是根据关键码值来确定数据的位置进行访问以提高查询速度，这种映射关系（函数）称为散列函数，存放数据的数组称为散列表。

它的数据存储形式是以键值对（key-value）的形式存储的，散列表的数据结构是数组+链表的形式。

哈希函数

哈希表的节点内部类存放的有数据，指向下一个节点的引用，以及哈希码，这个哈希码的作用就是将这个节点和它的存放位置做一个对应关系，那么这个对应关系就是哈希函数。

比如哈希函数式为：f(x) = x mod 7，那么就是将该节点中的hash码模7，得到的结果就是该节点在散列表中的下标位置。

选择一个好的哈希函数，可以减少哈希冲突的发生，但是哈希冲突无法避免。

哈希冲突

无论如何选择哈希函数，都无法避免哈希冲突，即同一个映射关系，不同的hash码会获得同一个散列表存储位置，要解决哈希冲突，有一种方法为链地址法，即如果发生哈希冲突，就将同一个位置的节点以链表的格式链在第一个节点后面，搜索时，如果同一个位置有多个节点，那么将搜索该链表，直到找到为止。

还有解决办法，如开放地址法，公共溢出法，再哈希法。

HashMap源码浅解析

HashMap类位于util工具包中。

它的父类是AbstractMap类，实现了Map，Cloneable(可克隆的)，Serializable(可序列化的)接口。

常量属性

DEFAULT_INITIAL_CAPACITY常量是散列表的默认初始化大小，大小是1<<4，即16。 这里注释了大小必须是2的幂次方，为什么？ MAXIMUM_CAPACITY常量是散列表的最大容量，大小是1<<30，即1073741824。 DEFAULT_LOAD_FACTOR常量是散列表的默认负载因子，如果插入的数据量大于数组的length乘负载因子，那么数组将扩容。 TREEIFY_THRESHOLD常量和UNTREEIFY_THRESHOLD常量用于界定链表和红黑树结构的转换。在解决哈希冲突时，链表的查询效率是线性的，但是树形结构的查询效率是nlog2n，所以如果链的节点太多（超过8个），就会把链表转换为红黑树结构以节省时间，如果节点小于6个，就会转回链表结构。

内部类

内部类的属性有hash码，key-value，next引用。

成员变量

存放数据的数组 数据个数 修改次数 阈值 负载因子

构造函数

可以传两个参数，一个是初始化数组大小，一个是负载因子。 也可以只传一个初始化数组的大小，负载因子将使用默认值。 也可以什么都不传，两个参数都将使用默认值。 也可以传一个Map对象，将把Map转换为HashMap。

增加一个节点方法

首先 会判断table，即存放数据的数组是否为空，或者其长度是否为0，如果是，则执行resize()函数，并把resize后的数组长度赋值给变量n。（resize()函数顾名思义，是重新给table一个size，resize具体怎么实现看后面。） 这个if语句是在判断当前(n-1)& hash的下标位置有没有元素（节点），如果没有（即为null），则直接在这里放值（节点）。 那么(n-1) & hash是什么？和n % tab.length()有什么不同？这里为什么不用后者？你可能会认为位运算比较快，那么既然前后者都可以用，那么就说明这两个是等价的，现在来证明它们等价。假设现在table的大小未指定，那么它的大小应该为默认值1<<4 ，即16，则n为16，二进制为10000，所以n-1为01111。&运算符的性质就是和0与，结果为0，和1与不变，那么01111和其他值取与运算，大小是取决于后几位1的，因为前几位都是0，0与任何值结果为0。那么如果与的数后4位是0000，那么结果的最小值就是0，如果与的数后4位是1111，那么结果的最大值就是15，所以实现了0-15的取值范围。（这里解释了为什么数组大小必须是2的幂次方，因为只有2的幂次方-1，后几位才全是1。） 所以借此来实现和%运算符同样的效果，但是位运算符稍快。

之后，进入else语句块，说明该下标有值，那么需要判断这个节点的下面连接的是树型结构还是链表结构，

如果p是树形结构(instanceof 关键字用来判断是不是类的实例)，那么用putTreeVal()方法放入树结构中。 如果不是树形结构，就说明是链表结构，那么遍历这个链表， 直到p.next，即p的下一个节点为null时，尾插入链表，然后判断链表长度是否大于8，如果大于要转为树型结构。 之后需要对onlyIfAbsent参数进行操作，如果onlyIfAbsent为true，则不覆盖已经存在的值，否则覆盖存在的值，并把覆盖掉的值返回。 之后修改次数+1，并判断数组是否需要扩容。

resize()函数：

首先获取原数组长度，如果长度大于0，即原数组不是null，再判断原数组长度长度是否大于允许的最大值1<<30，如果大于，说明这个数组不能再扩容了。否则，就2倍扩容原数组，阈值也双倍扩大。 进行临界值判断。 初始化新的table，之后涉及到一个重新哈希的过程，因为数组扩大了，那么在原来数组上发生的哈希冲突就得被缓解，所以要对发生哈希冲突的节点进行重新哈希，也就是重新定位他们在新数组中的存储位置。 首先判断节点的下一个节点有没有节点，如果没有节点，直接重新哈希， 如果有节点，分两种情况，一种是后面的节点是红黑树的节点， 一种是链表的节点，那么对它进行遍历，这里有一个细节，为什么 这里重新哈希后的节点位置只有两种位置，一种是j，也就是原来位置不变，一种是j+oldCap，也就是原来位置+原来数组长度？即下图为什么要判断(e.hash & oldCap) == 0？ 这是因为假设oldCap为16，即10000，前面给它减了1，与上hash码得到0000，那么hash码的右数第5个位是不确定的，有可能是1，也有可能是0，现在不给oldCap减1即10000，与上hash码，如果还是0，那么说明第5个位是0（有0为0，无0为1），即重新哈希后位置不变，如果不是0，就给他加上oldCap，即10000，这样才满足oldCap-1 & hash为0，所以重新哈希的位置为oldCap+j。

删除一个节点方法

删除一个节点的思路同添加一个方法 首先获得要删除的节点，因为方法最后要返回删除的节点，即node。 之后对节点进行删除，分三种情况，如果删除的节点存在于树形结构中，那么调用removeTreeNode方法删除节点，如果删除的节点是根节点的下一个节点，直接将node节点的next引用指向根节点，否则直接将该节点的next指向删除节点的下一个即可。 之后修改次数+1，有效个数-1并返回删除的节点node。

如何使用HashMap

常用的HashMap迭代方式有三种。

1.通过Map.keySet()遍历key和value。 2.通过Map.entrySet()遍历key和value。 3.通过Map.values()遍历value，但是不能遍历key。

ConcurrentHashMap

在看HashMap的源码时，我们没有看到一个加锁的过程，那么就说明HashMap不是线程安全的，所以就有了ConcurrentHashMap，但是它也不是给每个方法都加上synchronized关键字，那样就成了HashTable。

其实ConcurrentHashMap采用了分段锁机制，它的内部存在一个Segment内部类

每个Segment内部是一个小型的HashMap结构。

//待续

转载地址：http://mfwqi.baihongyu.com/