HashMap 源码分析

近几年HashMap是各大公司面试的热点，并由此延伸出非常多的东西，下面我们来讲解一些小知识点：

①HashMap的基本信息

②HashMap和HashTable的区别

③HashMap的底层实现

④HashMap解决碰撞问题

⑤ConcurrentHashMap的实现原理

 

一、HashMap的基本信息

       基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 HashMap是无序的线程非安全的。

 

二、HashMap和HashTable的区别

       ①HashMap是线程非安全的，HashTable是线程安全的。

       ②HashMap可以接受null值和null键，HashTable不接受。

       ③HashMap的迭代器是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。

       ④在单线程环境下，HashMap的速度比HashTable快，线程非安全的比线程安全的速度快，因为线程安全的存在一个加锁解锁的过程，当大量的这些过程累加到一块，是一个非常可观的时间。

       ⑤HashMap不能保证随着时间的推移元素的次序不发生变化。

 

三、HashMap的底层实现：

       HashMap在1.8之前底层是由Entry 数组和链表组成，1.8是由Entry数组、链表和红黑树组成；先来讲一下1.8之前的底层实现；

 HashMap采用 Entry 数组来存储，每一个键值对组成一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，代码如下：

 

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

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

 1.8及之后加入了红黑树的概念，每当一个链表的长度大于8的时候，便自动转化为红黑树 ，结构如下图：

 

 HashMap按照key的hash值来计算Entry在HashMap中的储存位置的，当value值相同时候可以存在在不同的链表中去 ；

 

四、HashMap对HashCode碰撞的处理

       运用拉法来解决：HashCode是使用key通过hash函数计算出来的，由于不同的key，通过此函数可能会算出同样的HashCode，所以采用拉链法来解决冲突，把HashCode相同的 value连成链表，但是get的时候根据key又去桶里找，如果是在一个链表中说明是冲突的，此时还需要检测key是否相同；

       用拉链法解决问题的时候，在调用HashMap的put方法的时候，都会首先调用HashCode去查找相关的key，当有冲突的时候，在调用equals方法；

       当两个不同的键有相同的HashCode的时候，他们会存储在同一个 bucket位置的链表中，键对象的equals（）来找到对应的键值对；

 

五、 ConcurrentHashMap的实现原理

        ConcurrentHashMap是线程安全且高效的HashMap，在并发程序中使用HashMap可能导致程序死循环，而使用线程安全的HashTable效率又非常低下。

        HashMap在并发执行put操作的时候会引起死循环，是因为多线程会导致HashMap的Entry链表形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry；

       HashTable在多线程环境下，当一个线程访问HashTable的同步方法，其他线程也访问HashTable的时候，会进入阻塞或者轮询状态；

       ConcurrentHashMap是Segment数组结构和HashEntry数组结构构成，Segment是 一种可重入锁，在ConcurrentHashMap中扮演锁的角色，HashEntry则用于存储键值对数据：

结构图如下图所示：

 

ConcurrentHashMap使用 分段锁Segment来保护不同段的数据，每一把锁用于锁容器中的一部分数据，当多线程访问容器里面不同数据段的数据时，线程就不会存在锁竞争，，从而有效的提高并发访问效率。