HashMap源码简析

HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

特性

• HashMap根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。
• HashMap最多只允许一条记录的键为null，允许多条记录的值为null。
• HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。

结构

从结构实现来讲，HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下如所示。

数组中的每个元素是内部类Node，其实现如下：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

HashMap中根据key对象的hash值计算出在数组中的索引，实现数组存储更加均匀，提高性能和效率。

我们上面可知，object对象的hashcode与对象内存地址一一对应，表示对象的唯一性。而通过hashcode计算出key对象的hash值也是唯一的，且对于同一个key对象，任何时候重复计算都会得到同样的hash值，从而定位出在数组中的位置。

hashcode计算出hash值的公式：
在JDK8中，由于使用了红黑树来处理大的链表开销，所以hash这边可以更加省力了，只用计算hashCode并移动到低位就可以了。

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

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
根据hash值计算在table[] 数组中的位置公式：

int index = (hash & 0x7FFFFFFF) % table.length; 

因为某些对象的 hashCode 可能会为负值，与 0x7FFFFFFF 进行与运算可以确保 index 为一个正数。

插入

HashMap的put()方法源码为：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //table为空则创建
        if ((tab = table) == null || (n = tab.length) == 0){
            n = (tab = resize()).length;
        }
        //计算index，并对null做处理
        if ((p = tab[i = (n - 1) & hash]) == null){
            tab[i] = newNode(hash, key, value, null);
        }else {
            Node<K,V> e; K k;
            //节点hash值同，且key值与插入key相同，直接覆盖value
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))){
                e = p;
            } else if (p instanceof TreeNode){
                //判断该链为红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            } else {
                //已经产生碰撞，采用链地址法解决冲突
                for (int binCount = 0; ; ++binCount) {
                    //p第一次指向链表头,以后依次后移
                    if ((e = p.next) == null) {
                        //e为空，表示已到链表尾也没有找到key值相同节点，则新建节点
                        p.next = newNode(hash, key, value, null);
                        //链表长度大于8转换为红黑树进行处理
                        if (binCount >= TREEIFY_THRESHOLD - 1) {
                            // -1 for 1st
                            treeifyBin(tab, hash);
                        }
                        break;
                    }
                    //容许null==null
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //更新p指向下一个节点
                    p = e;
                }
            }
            //更新hash值和key值均相同的节点Value值
            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;
    }

整体流程为：

1. 对key的hashCode()做hash，然后再计算index;
2. 如果没碰撞直接放到哈希桶数组里；
3. 如果碰撞了，以链表的形式存在哈希桶数组后；
4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
5. 如果节点已经存在就替换old value(保证key的唯一性)
6. 如果哈希桶数组满了(超过load factor*current capacity)，就要扩容。

在上面HashMap的插入过程中，如果出现两个key定位到同一个数组位置，表示发生了Hash碰撞。
哈希表为解决碰撞（冲突），可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。
链地址法，简单来说，就是数组加链表的结合。

取值

HashMap的get()方法源码为：

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //hash & (length-1)得到对象key的存储索引
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //hash码相同且key与要get的key的相同则返回数组此处的Node，之后转化为value
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                //如果第一个节点是TreeNode,说明采用的是数组+红黑树结构处理冲突
                if (first instanceof TreeNode){
                    //遍历红黑树，得到节点值
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                }
                //链表结构处理
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

整体流程为：

1. 在哈希桶数组里的第一个节点，直接命中；
2. 如果有冲突（碰撞），则通过key.equals(k)去查找
   • 若为树，则在树中通过key.equals(k)查找，O(logn)；
   • 若为链表，则在链表中通过key.equals(k)查找，O(n)。

小结

• 扩容是一个特别耗性能的操作，所以当程序员在使用HashMap的时候，估算map的大小，初始化的时候给一个大致的数值，避免map进行频繁的扩容。
• 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改，除非情况非常特殊。
• HashMap是线程不安全的，不要在并发的环境中同时操作HashMap，建议使用ConcurrentHashMap。
• JDK1.8引入红黑树大程度优化了HashMap的性能。
• 还没升级JDK1.8的，现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。