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

一、概述

在JDK1.6，JDK1.7中，HashMap采用数组（数组中的每一个索引看作一个位桶）+链表实现，即使用链表处理冲突,同一hash值的键值对会被放在同一个位桶里，当桶中元素较多时，通过key值查找的效率较低。 而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）,时，将链表转换为红黑树，这样大大减少了查找时间。 二、JDK1.8中的HashMap 1.8中改为数组+链表+红黑树实现的好处是，如果hash冲突较多时，查找的效率更高。如果说成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费O(N)的查找时间，这将是多么大的性能损失。这个问题终于在JDK8中得到了解决。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。 基本属性：

transient Node
   
    [] table; //Node类型的数组，记我们常说的bucket数组，其中每个元素为链表或者树形结构transient int size;//HashMap中保存的数据个数int threshold;//HashMap需要resize操作的阈值final float loadFactor;//负载因子，用于计算threshold。计算公式为：threshold = loadFactor * capacitystatic final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 数组初始大小，hashmap的初始容量static final float DEFAULT_LOAD_FACTOR = 0.75f;//负载因子transient int size; //数组已使用的大小int threshold;//table数组扩容的阈值 = 容量x负载因子 transient int modCount;//HashMap修改的次数，Fail-fast错误检测机制用到，当迭代器遍历次集合时，不允许其他线程修改此集合static final int TREEIFY_THRESHOLD = 8;//链表变为红黑树的阈值
   

HashMap将元素存储在一个名为table的数组中：

transient Node
   
    [] table;
   

数组中的元素类型为Node<K,V>类型：

static class Node
   
     implements Map.Entry
    
      {        final int hash;        final K key;        V value;        Node
     
       next;        }
     
    
   

我们使用HashMap时，一个键值对对应一个Node，键存储在key中，值存储在value中。Node是单向链表的节点，它实现了Map.Entry接口。

将元素存放在HashMap中

使用put方法将元素放进HashMap中

public V put(K key, V value) {        return putVal(hash(key), key, value, false, true);    }

调用 putVal（）方法将元素放进table数组内

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {        Node
   
    [] tab;        Node
    
      p;        int n, i;        if ((tab = table) == null || (n = tab.length) == 0)//判断长度是否为空            n = (tab = resize()).length;//长度为0就初始化数组，并        if ((p = tab[i = (n - 1) & hash]) == null)            tab[i] = newNode(hash, key, value, null);        else {            Node
     
       e; K k;            if (p.hash == hash &&                ((k = p.key) == key || (key != null && key.equals(k))))                e = p;            else if (p instanceof TreeNode)                e = ((TreeNode
      
       )p).putTreeVal(this, tab, hash, key, value);            else {                for (int binCount = 0; ; ++binCount) {                    if ((e = p.next) == null) {                        p.next = newNode(hash, key, value, null);                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                            treeifyBin(tab, hash);                        break;                    }                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k))))                        break;                    p = e;                }            }            if (e != null) { // existing mapping for key                V oldValue = e.value;                if (!onlyIfAbsent || oldValue == null)                    e.value = value;                afterNodeAccess(e);                return oldValue;            }        }        ++modCount;        if (++size > threshold)            resize();        afterNodeInsertion(evict);        return null;    }
      
     
    
   

在，调用putVal方法前，先使用hash（）方法计算key的hash值（不是hashCode）

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

计算hash值的方法是，先计算key的hashCode，然后将hashCode按位右移16位，最后将hashCode和右移16位后的值做异或运算（任何数跟0异或都是其本身）。

右移16位相当于取原值的高16位，即将原数的高16位放到低16位中，再将高16位都置0。 异或计算后的数值是名为hash的32位int类型，高16位为key的hashCode的高16位，低16位为key的高16位和低16位的异或运算值。该值会存放再Node中。这样计算的原因是将int类型的hashCode值都用上了。 在计算完hash值后，进入putVal方法内，先判断原数组是否为空，若为空使用resize（）方法将数组初始化，并返回数组的大小n。 tab[i = (n - 1) & hash] 假设你为16，n-1之后为15，用二进制表示高28位位0，低4位全为1，再与计算的key的hash值做与运算，得到的值为hash值的后4位，这样i的值就位0-15之间，i就是改值放在table数组中的位置。 根据之前计算的hash值和key、value的值新建一个Node，存放再table[i]处。 ++modCount;集合的修改值加一。 hash冲突解决办法 当之前计算的table[i]处已经有值时，就发生了hash冲突， 扩容 当数组的长度达到 threshold = capacity * load factor时，使用resize()方法进行扩容。 达到阈值进行扩容的原因是减少hash冲突，当达到16才扩容，可能此时链表的长度已经很长了，影响查询效率。

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