HashMap结构

底层数据结构 数组 + 链表（或红黑树）。Map实现了Map接口，继承AbstractMap。其中Map接口定义了键映射到值的规则（一个map不能包含重复的key，每个key最多只能对应一个value，HashMap最多只允许一条记录的键为null，允许多条记录的值为null。），而AbstractMap类提供 Map 接口的骨干实现，以最大限度地减少实现此接口所需的工作，其实AbstractMap类已经实现了Map。

默认容量（哈希表桶的数量）和装载因子是16和0.75，也就是元素超过16*0.75时，会再哈希，每次在哈希默认容量乘以2，容量的最大值是2的30次方。(不对)Node<K,V>是HashMap的内部类，每次新建一个HashMap时，都会初始化一个Node<K,V>数组,而Node<K,V>实现Map.Entry<K,V>。table数组的元素为Entry节点。Node为HashMap的内部类，它包含了键key、值value、下一个节点next，以及hash值，正是由于Node才构成了Node数组的项为链表结构。

put()过程

1. table数组为空则扩容
2. 计算hash值，计算索引下标 （数组长度-1）& hash
3. 该位置是否有值（节点），没有则直接插入，如果有判断是否是红黑树，如果是红黑树直接调整树，不是则为链表，判断链表超过8则转为红黑树，否则插入链表
4. ++size > threshold ? resize（）：结束

参见该文中的图

负载因子为什么是0.75

根据统计学的结果, hash冲突是符合泊松分布的, 而冲突概率最小的是在7-8之间, 都小于百万分之一了; 所以HashMap.loadFactor选取只要在7-8之间的任意值即可, 但是为什么就选了3/4这个值,table.length * 3/4可以被优化为(table.length >> 2) << 2) - (table.length >> 2) == table.length - (table.lenght >> 2), JAVA的位运算比乘除的效率更高, 所以取3/4在保证hash冲突小的情况下兼顾了效率

resize() 过程

1. 如果table == null, 则为HashMap的初始化, 生成空table返回即可;

2. 如果table不为空, 需要重新计算table的长度, newLength = oldLength << 1(注, 如果原oldLength已经到了上限, 则newLength = oldLength);

3. 遍历oldTable:

3.1 首节点为空, 本次循环结束;

3.2 无后续节点, 重新计算hash位, 本次循环结束;

3.3 当前是红黑树, 走红黑树的重定位;

3.4 当前是链表, JAVA7时还需要重新计算hash位, 但是JAVA8做了优化, 通过(e.hash & oldCap) == 0来判断是否需要移位; 如果为真则在原位不动, 否则则需要移动到当前hash槽位 + oldCap的位置;

详解释见

时候会触发扩容

当 size > threshold （容量 * 装在因子） 的时候进行扩容

并发场景resize形成环形链表，get死循环

多线程resize，由于1.7 resize 后链表顺序会反转，并发resize过程形成环形链表

1.8中是否解决

JDK8的resize是让节点的顺序发生改变的, 也就是没有倒排问题了，不会形成环
详解释见

为什么线程不安全

HashMap 在并发时可能出现的问题主要是两方面,首先如果多个线程同时使用put方法添加元素，而且假设正好存在两个 put 的 key 发生了碰撞(根据 hash 值计算的 bucket 一样)，那么根据 HashMap 的实现，这两个 key 会添加到数组的同一个位置，这样最终就会发生其中一个线程的 put 的数据被覆盖。第二就是如果多个线程同时检测到元素个数超过数组大小* loadFactor ，这样就会发生多个线程同时对 Node 数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给 table，也就是说其他线程的都会丢失，并且各自线程 put 的数据也丢失。
关于 HashMap 线程不安全这一点，《Java并发编程的艺术》一书中是这样说的：

HashMap 在并发执行 put 操作时会引起死循环，导致 CPU 利用率接近100%。因为多线程会导致 HashMap 的 Node 链表形成环形数据结构，一旦形成环形数据结构，Node 的 next 节点永远不为空，就会在获取 Node 时产生死循环。

google 了一下，才知道死循环并不是发生在 put 操作时，而是发生在扩容时。详细的解释可以看下面几篇博客：
• 酷壳-Java HashMap的死循环
• HashMap在java并发中如何发生死循环
• How does a HashMap work in JAVA

长度为什么是2的n次幂

在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，具体证明可以参考http://blog.csdn.net/liuqiyao_01/article/details/14475159，HashMap采用这种非常规设计，主要是为了在取模（取模转为位运算提高效率）和扩容时做优化（不用重新hash，直接计算出新的位置，见上面 resize 的过程），同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程（解释见）。找到数组下标的方法：(数组长度 - 1) & hash，hash 过程如下：

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

hash的实现

1。7的hash方法是纯数学计算，在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。取模用位运算(hash & (arrayLength-1))会比较快
这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

rehash的过程：

rehash的判断条件实际上就是当前的 数据量是否达到了当前容量乘以负载因子，如果达到了，只要再新加数据就会触发rehash。
如果当前容量已经达到了最大用量 ，则不扩充，直接更新threshold的值为int的最大值MAX_VALUE = 0x7fffffff;（2的31次幂减一），否则就扩充容量为当前容量的两倍。
主要在代码的transfer方法来完成的，实际上就是一次取出原始table中的数据，计算他们在newTable的 位置 ，插入即可。

http://www.xiaomager.com/299.html

hashmap jdk8优化

jdk8以前：我们可以看出Entry是一个单向链表，这也是我们为什么说HashMap是通过拉链法解决hash冲突的。
jdk8后：不再使用链表，改用了红黑树，提高了查找效率。
jdk1.8中，hash map增加了比较的接口 在Map接口的Entry接口增加了 comparingByKey comparingByValue

在Java 8之前的实现中是用链表解决冲突的，在产生碰撞的情况下，进行get时，两步的时间复杂度是O(1)+O(n)。因此，当碰撞很厉害的时候n很大，O(n)的速度显然是影响速度的。因此在Java 8中，bucket中碰撞冲突的元素超过某个限制(默认是8)，利用红黑树替换链表，这样复杂度就变成了O(1)+O(logn)了，这样在n很大的时候，能够比较理想的解决这个问题.
这一动态的特性使得HashMap一开始使用链表，并在冲突的元素数量超过指定值（8）时用平衡二叉树替换链表。不过这一特性在所有基于hash table的类中并没有，例如Hashtable和WeakHashMap。
目前，只有ConcurrentHashMap,LinkedHashMap和HashMap会在频繁冲突的情况下使用平衡树。

hash优化

我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”

与其他map的比较

Hashtable

Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap，因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用，不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。

LinkedHashMap

LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。LinkedHashMap=散列表+循环双向链表 见：http://www.cnblogs.com/chenpi/p/5294077.html

TreeMap

TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

TreeMap 本质是红黑树，树节点 Entry<K,V>，它包含了红黑数的6个基本组成成分：key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)。Entry节点根据key进行排序，Entry节点包含的内容为value。

hashset

hashset底层使用的是hashmap

【参考】
Java HashMap工作原理及实现 ：http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/
美团：Java 8系列之重新认识HashMap：http://tech.meituan.com/java-hashmap.html
疫苗：Java HashMap的死循环：http://coolshell.cn/articles/9606.html
HashMap多线程死循环问题：http://blog.csdn.net/xuefeng0707/article/details/40797085

如何线程安全的使用 HashMap http://yemengying.com/2016/05/07/threadsafe-hashmap/

Java 8系列之重新认识HashMap

最后

以上就是迅速金针菇为你收集整理的Java——HashMapHashMap结构put()过程负载因子为什么是0.75resize() 过程时候会触发扩容并发场景resize形成环形链表，get死循环为什么线程不安全长度为什么是2的n次幂hash的实现rehash的过程：hashmap jdk8优化与其他map的比较的全部内容，希望文章能够帮你解决Java——HashMapHashMap结构put()过程负载因子为什么是0.75resize() 过程时候会触发扩容并发场景resize形成环形链表，get死循环为什么线程不安全长度为什么是2的n次幂hash的实现rehash的过程：hashmap jdk8优化与其他map的比较所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。