Java集合（17）——HashMap源码解析

类图

官方文档

(1) Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

(2) This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the “capacity” of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it’s very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

(3) An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

(4) As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

(5) Note that this implementation is not synchronized. If multiple threads access a hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.)This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be “wrapped” using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

（1）Hash表是基于Map接口实现的。该实现提供了所有可选的映射操作，并允许使用空值和空键。 （HashMap类大致等同于Hashtable，除了它是不同步的并且允许为空值。）这个类不能保证数据的顺序；尤其它不能保证顺序会随着时间的推移保持不变。

（2）这个实现为基本操作（get和put）提供了稳定的性能，假设散列函数在桶之间正确地分散元素。迭代集合视图需要的时间与HashMap实例的“容量”（桶的数量）加上其大小（键值映射的数量）是成正比。因此，如果迭代性能很重要，不要将初始容量设置得太高（或者负载因子太低）。

（3）HashMap的一个实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中桶的数量，初始容量就是哈希表创建时的容量。加载因子是散列表在其容量自动增加之前被允许获得的满量程的度量。当桶的数目（即hashmap中元素的个数）大于capacity*load factor时就需要调整buckets的数目为当前的2倍。

（4）通常，默认加载因子（.75）在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在大部分HashMap类的操作中，包括get和put）。在设置初始容量时，应考虑映射中的条目数量及其负载因子，以尽量减少重新运行操作的次数。如果初始容量大于最大入口数除以负载因子，则不会发生重新刷新操作。

（5） 注意该实现是非同步的，如果多个线程同时访问哈希映射，并且至少有一个线程在结构上修改了映射，则它必须在外部同步。 （结构修改是添加或删除一个或多个映射的任何操作;仅更改与实例已包含的键相关的值不是结构修改。）这个操作是由使用该map类的实体类实现的，如果没有这个类存在，那么map应该使用Collections.synchronizedMap的方法获得线程安全的HashMap。包装操作最好在创建时进行，为了防止一些非同步的访问存在。

Map map = Collections.synchronizedMap(new HashMap());

HashMap的底层实现是：数组＋链表，在jdk8以后又加入了红黑树
HashMap 的特殊存储结构使得在获取指定元素前需要经过哈希运算，得到目标元素在哈希表中的位置，然后再进行少量比较即可得到元素，这使得 HashMap 的查找效率变得很高。下面是hashmap的存储方式

成员方法

成员变量

其中：
DEFAULT_INITIAL_CAPACITY：默认初始容量：16，必须是 2 的整数次方
MAXIMUM_CAPACITY：最大容量（必须是2的幂且小于2的30次方，传入容量过大会被这个值替换）
threshold：阈值，下次需要扩容时的值，等于 容量*加载因子
TREEIFY_THRESHOLD：树形阈值：JDK 1.8 新增的，当使用 树 而不是列表来作为桶时使用。必须必 2 大

成员方法

（42）–（50）方法是留给LinkedHashMap实现的

内部类

HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象，它就是用来处理hash冲突的，形成一个链表。

成员方法源码解析

内部类 static class Node<K,V> implements Map.Entry<K,V>

    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; } //获取当前Node的键
        public final V getValue()      { return value; }//获取当前Node的值
        public final String toString() { return key + "=" + value; } 

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
        //更新当前Node的值
        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;
        }
    }

成员变量

　　table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的。
　　size是HashMap的大小，它是HashMap保存的键值对的数量。
　　threshold是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold的值=”容量*加载因子”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
　　loadFactor就是装载因子。用来描述hash表中元素的填满程度。
　　若装载因子越大，填满的元素越多，好处是：空间利用率高了，但是冲突的机会更大，链表的长度会变长，导致查找效率降低。
　　若装载因子越小，填满的元素越少，好处是：空间利用率降低，因此空间浪费多了，表中的数据过于稀疏，很多空间没有使用，就需要开始扩容

成员方法

1. static final int hash(Object key)方法

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

源码解析：

• 功能：返回当前HashMap的hash码
• 源码思路：
  
  • 判断如果集合中的键为null，则返hash码为0，如果集合中的键不为null，则该集合的hash码只与键的hashCode码有关

由于哈希表的容量都是 2 的 N 次方，在当前，元素的 hashCode() 在很多时候下低位是相同的，这将导致冲突（碰撞），因此 1.8 以后做了个移位操作：将元素的 hashCode() 和自己右移 16 位后的结果求异或。
由于 int 只有 32 位，无符号右移 16 位相当于把高位的一半移到低位：

2. static int compareComparables(Class<?> kc, Object k, Object x)方法

    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc ? 0 :
                ((Comparable)k).compareTo(x));
    }

源码解析：

• 功能：比较两个Object实体的大小
• 源码思路：
  
  • 判断x是否等于null与x的class类型是否与给定的kc类类型一致，如果都满足则调用compareTo方法判断两个实体的大小是否相等

3. static final int tableSizeFor(int cap)方法

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

4. public HashMap(int initialCapacity, float loadFactor)方法

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

源码解析：

• 功能：带参数的构造方法，参数为：初始容量、负载因子
• 源码思路：
  
  • （1）首先判断初始容量是否小于0，如果小于0，则抛出异常
  • （2）判断初始容量和集合中最大能容纳的元素个数，如果初始容量大于集合中最大能容纳的元素个数MAXIMUM_CAPACITY，则将MAXIMUM_CAPACITY赋值给初始容量
  • （3）判断负载因子是否小于等于0以及负载因子是否是数值类型，如果不是抛出异常，否则执行步骤（4）
  • （4）将初始容量和负载因子的值赋值给当前的集合

5. public HashMap(int initialCapacity)方法

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

源码解析：

• 功能：带参数的构造方法，参数为：HashMap的最大容量，即为底层数组的长度（初始容量）
• 源码思路：
  
  • 调用带两个参数的构造方法，其中初始容量为传递的数值，负载因子为默认的值

6. public HashMap()方法

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

源码解析：

• 功能：不带参数的构造方法
• 源码思路：
  
  • 其中初始容量和负载因子都为默认初始值：16和0.75

7. public HashMap(Map<? extends K, ? extends V> m)方法

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

源码解析：

• 功能：该类的带参数构造方法，参数为：Map类型的参数m；使用现有的map类型的值来创建新的对象
• 源码思路：
  
  • （1）将当前新对象的负载因子设置为默认值
  • （2）调用putMapEntries（）方法实现创建对象的功能

8. final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict)方法

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

源码解析：

• 功能：Map.putAll方法和Map构造方法的核心方法
• 源码思路：
  
  • （1）定义int类型变量s，其值为集合m的长度
  • （2）判断如果s的值>0则执行以下操作，否则返回null
  • （3）如果结点table为null，判断集合最大容纳元素量与capacity * load factor值进行比较，如果小于capacity * load factor，则将threshold值扩大；否则调用resize（）方法
  • （4）使用for循环，将参数m中的元素全部放入当前集合中，调用putVal（）方法实现该功能

9. public int size()方法

    public int size() {
        return size;
    }

源码解析：

• 功能：返回集合中key-value键值对的个数

10. public boolean isEmpty()方法

    public boolean isEmpty() {
        return size == 0;
    }

源码解析：

• 功能：判断集合中是否有元素

11. public V get(Object key)方法

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

源码解析：

• 功能：得到键为key的值
• 源码思路：
  
  • （1）定义一个Node类型的变量e
  • （2）通过调用getNode（）方法将得到的结点放在e中，并判断e是否为null，如果为空，该方法返回null，否则返回e的value

12. final Node<K,V> getNode(int hash, Object key)方法

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                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;
    }

源码解析：

• 功能：通过hash码和键两个条件 ，找到该集合中满足这两个条件的结点
• 源码思路：
  
  • （1）tab指向哈希表，其存储哈希表中的元素；n是哈希表的长度，first在程序中会被赋值为（n-1）&hash位置处的桶中的第一个结点（即用(n-1)&hash来计算桶的位置）
  • （2）如果桶里的第一个结点就相等，直接返回该结点
  • （3）否则就通过while循环进行遍历：如果是树形结点，就调用树形结点的get方法

13. public boolean containsKey(Object key)方法

    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }

源码解析：

• 功能：判断集合中是否存在键为key的值
• 源码思路：
  
  • 调用getNode（）方法实现该功能

14. public V put(K key, V value)方法

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

源码思路：

• 功能：将键为key，值为value的实体插入到集合中，如果集合中存在该键，则更新该键对应的值为新的value
• 源码思路：
  
  • 调用putVal（）方法实现该功能

15. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)方法

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //如果当前哈希表的内容为空，新建一个hash标，n是指向最后一个桶的位置，tab是hash标的另一个引用 
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //找到要插入的桶的位置，将该位置放置在变量p中，如果要插入的桶p中已经存在结点，替换该结点的值，e指向被替换的结点
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            //p指向要插入的桶的第一个元素的位置，如果P的hash值、键和将要添加的结点的一样，就停止查找，e直接被赋值为p
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果不一样，并且当前采用的存储方式还是jdk8以后的树形结点，需要调用putTreeVal方法进行插入，否则就用传统的链表数组进行查找和替换
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)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);
                        //当这个桶内的链表个数大于8，就要讲这个链表进行树形化
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果找到要替换的结点，就停止查找，此时e指向要被替换的结点
                    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;
        ////如果超出阈值，需要调用resize方法进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

16. final Node<K,V>[] resize()方法

这个方法很重要，每一次的添加都会需要比较当前元素个数size和阈值threshold之间的关系,如果size>threshold就需要进行扩容操作

    if(++size > threshold)
        resize();

    final Node<K,V>[] resize() {
        //定义一个变量，用来存储当前集合中的哈希表信息
        Node<K,V>[] oldTab = table;
        //保留旧的元素个数，如果为空，该值为0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //保留旧的阈值
        int oldThr = threshold;
        int newCap, newThr = 0;
        //如果旧的元素个数大于0
        if (oldCap > 0) {
            //如果旧的元素个数大于最大容量，则需要将阈值调整为整型的最大值，并返回
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //扩展新的容量范围为旧的容量的2倍，这里还需要判断如果旧的容量小于MAXIMUM_CAPACITY 值，新的阈值变为旧的阈值的2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        //如果旧的容量为0，旧的阈值>0，说明之前创建了哈希表，但是没有向表中插入元素，因此初始化容量等于阈值
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        //旧的阈值和容量都为0，说明还没有创建哈希表，新的容量值为默认容量，新的阈值为默认阈值
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //如果新的阈值是0，就需要使用newCap * loadFactor再更新一次
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        //将旧哈希表中的元素通过for循环移入到新的哈希表中
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //定义变量e，其值等于旧的桶的第j个元素
                if ((e = oldTab[j]) != null) {
                    //将旧的桶设置为null
                    oldTab[j] = null;
                    //如果该元素的下一个元素为null，说明当前桶只有一个元素，直接赋值给对应的新桶的位置即可
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果旧的哈希表中的这个位置的桶的形状是树形结构，就需要把哈希表中当前桶也变为树形结构
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        //表刘旧的哈希表桶中链表的顺序
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

整个扩容的过程包括：
（1）重新计算hash值，找到桶的位置
（2）迭代每个桶的链表结构，保存原来的链表结构，或者树形结构

17. final void treeifyBin(Node<K,V>[] tab, int hash)方法

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

源码解析：

• 功能：如果集合中元素的个数超过一定限制，则将链表结构变为红黑树结构

18. public void putAll(Map<? extends K, ? extends V> m)方法

    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }

源码解析：

• 功能：将集合m中的元素插入当前集合中
• 源码思路：
  
  • 调用putMapEntrie（）方法实现该功能

19. public V remove(Object key)方法

    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

源码解析：

• 功能：将键为key的元素从集合中移除，如果该键不存在，则返回null
• 源码思路：
  
  • （1）定义一个Node类型的变量e
  • （2）调用removeNode（）方法，在集合中查找键为key的元素，找到后，将该方法返回的值赋值给e，如果e为null说明集合中不存在该键，则返回null，否则返回该键对应的值
  • （3）移除操作是由removeNode（）方法实现的

20. final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable)方法

    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

源码解析：

• 功能：从集合中移除键为key，值为value的结点

21. public void clear()方法

    public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

源码解析：

• 功能：将集合中的元素全部清除
• 源码思路：
  
  • （1）该方法是对集合的结构上的修改，因此需要修改modCount的值，将该值自加1
  • （2）判断如果集合中的元素不为空，并且集合的size大于0，则修改size的值，将其置为0
  • （3）通过for循环，将集合中的元素都赋值为null

22. public boolean containsValue(Object value)方法

    public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        //判断集合中是否有元素，如果有元素进行下列操作，如果没有元素，则返回false
        if ((tab = table) != null && size > 0) {
            //通过for循环进行遍历，遍历直到最后一个桶
            for (int i = 0; i < tab.length; ++i) {
                //遍历每个桶的链表，直到遍历到链表结尾，或者遍历到希望判断的元素为止
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

源码解析：

• 功能：判断集合中是否包含值为value的元素，如果有则返回true，否则返回false
• 源码思路：
  
  • （1）有两层for循环，外层循环用来遍历桶
  • （2）内层循环用于遍历每个桶的链表，直到找到想要找的元素或者找到最后一个桶的最后一个元素为止

23. public Set<K> keySet()方法

    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }

源码解析：

• 功能：返回集合中的键key集合，返回的结果是Set类型

  1. public Collection<V> values()方法

    public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }

源码解析：

• 功能：返回集合中值的集合，返回的类型为Collection类型

25. public Set<Map.Entry<K,V>> entrySet()方法

    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }

源码解析：

• 功能：返回集合中实体entry的集合，返回的集合类型为Set<Map.Entry<K,V>>

HashMap的常见面试问题

1. HashMap有什么特点？

（1）HashMap实现了Map接口
（2）存储键值对时，它可以存储键值对为null的键与值，key为null的键值对永远都放在以table[0]为头结点的链表中
（3）它是非同步的
（4）HashMap拥有Entry(hash,key,value,next)对象

2. 你知道HashMap的工作原理吗？

（1）通过hash的方法，通过put和get存储和获取对象。
（2）存储对象时，我们将K和V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。
（3）获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。
（4）如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。

3. 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？

通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点

4. 你知道hash的实现吗？为什么要这样实现？

在Java 1.8的实现中，是通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在bucket的n比较小的时候，也能保证考虑到高低bit都参与到hash的计算中，同时不会有太大的开销。

5. 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

HashMap默认的负载因子大小为0.75，也就是说，当一个map填满了75%的空间的时候，和其它集合类(如ArrayList等)一样，则会重新resize一个原来长度两倍的HashMap，并且重新调用hash方法，并将原来的对象放入新的数组中。

6. 如果两个键的hashcode相同，你如何获取值对象

HashMap在链表中存储的是键值对，找到哈希地址位置之后（即找到桶后），会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象

7. 为什么String, Interger这样的wrapper类适合作为键？

String, Interger这样的wrapper类是final类型的，具有不可变性，而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的，因为为了要计算hashCode()，就要防止键值改变，如果键值在放入时和获取时返回不同的hashcode的话，那么就不能从HashMap中找到你想要的对象。 使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。

8. HashMap与Hashtable的区别

（1）HashMap继承于AbstractMap，而Hashtable继承于Dictionary；
（2）线程安全不同。Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程。而HashMap的函数则是非同步的，它不是线程安全的。若要在多线程中使用HashMap，需要我们额外的进行同步处理；
（3）null值。HashMap的key、value都可以为null。Hashtable的key、value都不可以为null；
（4）迭代器(Iterator)。HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException。
（5）容量的初始值和增加方式都不一样：HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”。Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”；
（6）添加key-value时的hash值算法不同：HashMap添加元素时，是使用自定义的哈希算法。Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。
（7）速度。由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。

9. HashMap中hash函数怎么是是实现的？还有哪些 hash 的实现方式？

（1）对key的hashCode做hash操作（高16bit不变，低16bit和高16bit做了一个异或）；
（2） h & (length-1); //通过位操作得到下标index。

10. 针对 HashMap 中某个 Entry 链太长，查找的时间复杂度可能达到 O(n)，怎么优化？

将链表转为红黑树，实现 O(logn) 时间复杂度内查找。JDK1.8 已经实现了。

11. 能否让HashMap同步？

HashMap可以通过下面的语句进行同步：Map m = Collections.synchronizeMap(hashMap);

12. jdk8和jdk7在哈希表的存储方面发生的改变是什么？

如果多个hashCode()的值落到同一个桶内的时候，这些值是存储到一个链表中的。最坏的情况下，所有的key都映射到同一个桶中，这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。
如果某个桶中的记录过大的话（当前是TREEIFY_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。它是如何工作的？前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。

13. 我们可以使用自定义的对象作为键吗？

这是前一个问题的延伸。当然你可能使用任何对象作为键，只要它遵守了equals()和hashCode()方法的定义规则，并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象是不可变的，那么它已经满足了作为键的条件，因为当它创建之后就已经不能改变了。

14. 我们可以使用CocurrentHashMap来代替Hashtable吗？

这是另外一个很热门的面试题，因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable，但是HashTable提供更强的线程安全性。

15. 为什么HashMap是线程不安全的，实际会如何体现？

第一，如果多个线程同时使用put方法添加元素
假设正好存在两个put的key发生了碰撞(hash值一样)，那么根据HashMap的实现，这两个key会添加到数组的同一个位置，这样最终就会发生其中一个线程的put的数据被覆盖。
第二，如果多个线程同时检测到元素个数超过数组大小*loadFactor
这样会发生多个线程同时对hash数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给table，也就是说其他线程的都会丢失，并且各自线程put的数据也丢失。且会引起死循环的错误。

16. 为什么HashTable的默认大小和HashMap不一样？

前面分析了，Hashtable 的扩容方法是乘2再+1，不是简单的乘2，故hashtable保证了容量永远是奇数，合之前分析hashmap的重算hash值的逻辑，就明白了，因为在数据分布在等差数据集合(如偶数)上时，如果公差与桶容量有公约数 n，则至少有(n-1)/n 数量的桶是利用不到的，故之前的hashmap 会在取模（使用位与运算代替）哈希前先做一次哈希运算，调整hash值。这里hashtable比较古老，直接使用了除留余数法，那么就需要设置容量起码不是偶数（除（近似）质数求余的分散效果好）。

17. 你了解重新调整HashMap大小存在什么问题吗？

你可能回答不上来，这时面试官会提醒你当多线程的情况下，可能产生条件竞争(race condition)。
当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail
traversing)。如果条件竞争发生了，那么就死循环了。

感谢

[1] 作者： 张拭心 https://blog.csdn.net/u011240877/article/details/53351188
[2] http://yikun.github.io/2015/04/01/Java-HashMap工作原理及实现/
[3] https://blog.csdn.net/u012512634/article/details/72735183
[4] https://blog.csdn.net/shengmingqijiquan/article/details/73801228