HashMap概述

HashMap存储的时key-value的键值，允许key为null,也允许value为null。HashMap内部为数据+链表的结构，会根据hashCode的值来确定数据索引（确定存放在哪个桶），如果遇到索引相同的key,那么会被存放到同同一个桶中(hash冲突)，如果发生hash冲突，HashMap会将同一个桶中的数据以链表的形式存储，但如果发生hash冲突的概率比较高，就会导致同一个桶中的链表长度过长，遍历效率降低，所以在JDK1.8中如果链表长度达到阀值（默认时8），就会将链表转成红黑二叉树。

HashMap数据结构

HashMap1.8 - 图1

  1. //Node本质上是一个Map.存储着key-value
  2.     static class Node<K,V> implements Map.Entry<K,V> {
  3.         final int hash;             //保存该桶的hash值
  4.         final K key;                //不可变的key
  5.         V value;                    
  6.         Node<K,V> next;      //指向一个数据的指针
  8.         Node(int hash, K key, V value, Node<K,V> next) {
  9.             this.hash = hash;
  10.             this.key = key;
  11.             this.value = value;
  12.             this.next = next;
  13.         }

构造函数

1.1 HashMap()

  1.     // 1.无参构造方法、
  2.     // 构造一个空的HashMap，初始容量为16，负载因子为0.75
  3.     public HashMap() {
  4.         this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  5.     }

1.2 HashMap(int initialCapacity)

  1.     // 2.构造一个初始容量为initialCapacity，负载因子为0.75的空的HashMap，
  2.     public HashMap(int initialCapacity) {
  3.         this(initialCapacity, DEFAULT_LOAD_FACTOR);
  4.     }

1.3 HashMap(int initialCapacity, float loadFactor)

  1.      // 3.构造一个空的初始容量为initialCapacity，负载因子为loadFactor的HashMap
  2.     public HashMap(int initialCapacity, float loadFactor) {
  3.         if (initialCapacity < 0)
  4.             throw new IllegalArgumentException("Illegal initial capacity: " +
  5.                                                initialCapacity);
  6.         if (initialCapacity > MAXIMUM_CAPACITY)
  7.             initialCapacity = MAXIMUM_CAPACITY;
  8.         if (loadFactor <= 0 || Float.isNaN(loadFactor))
  9.             throw new IllegalArgumentException("Illegal load factor: " +
  10.                                                loadFactor);
  11.         this.loadFactor = loadFactor;
  12.         this.threshold = tableSizeFor(initialCapacity);
  13.     }
  15.     //最大容量
  16.     //static final int MAXIMUM_CAPACITY = 1 << 30;
  1. initialCapacity:初始容量、MAXIMUM_CAPACITY：最大容量
  3. 当指定的初始容量< 0时抛出IllegalArgumentException异常，当指定的初始容量> MAXIMUM_CAPACITY时，
  4. 就让初始容量 = MAXIMUM_CAPACITY。
  5. 当负载因子小于0或者不是数字时，抛出IllegalArgumentException异常。
  7. 设定threshold。 这个threshold = capacity * load factor 。
  8. 当HashMap的size到了threshold时，就要进行resize，也就是扩容。
      //对于给定的目标容量，返回两倍大小的幂。
    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;
    }

tableSizeFor()的主要功能是返回一个比给定整数大且最接近的2的幂次方整数，
如给定10，返回2的4次方16.

1.4 HashMap(Map<? extends K, ? extends V> m)

        // 4. 构造一个和指定Map有相同mappings的HashMap，初始容量能充足的容下指定的Map,负载因子为0.75
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    /**
     * 将m的所有元素存入本HashMap实例中
     */
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        //得到 m 中元素的个数
        int s = m.size();
        //当 m 中有元素时，则需将map中元素放入本HashMap实例。
        if (s > 0) {
            // 判断table是否已经初始化，如果未初始化，则先初始化一些变量。（table初始化是在put时）
            if (table == null) { // pre-size
                // 根据待插入的map 的 size 计算要创建的　HashMap 的容量。
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                // 把要创建的　HashMap 的容量存在　threshold　中
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            // 如果table初始化过，因为别的函数也会调用它，所以有可能HashMap已经被初始化过了。
            // 判断待插入的　map 的 size,若　size 大于　threshold，则先进行　resize()，进行扩容
            else if (s > threshold)
                resize();
            //然后就开始遍历 带插入的 map ，将每一个 <Key ,Value> 插入到本HashMap实例。
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                // put(K,V)也是调用　putVal　函数进行元素的插入
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

HashMap 重要的几个成员变量

    //实际存储key，value的数组，只不过key，value被封装成Node了
    transient Node<K,V>[] table;

    /**
     * 此映射中包含的键-值映射的数量。
     */
    transient int size;

    //HashMap结构修改次数
    transient int modCount;

    //因为 tableSizeFor(int) 返回值给了threshold
    int threshold;

    //加载因子
    final float loadFactor;

面试题：
1.HashMap数据结构
HashMap是数组+链表的数据机构
2.HashMap原理
HashMap是数据+链表的数据结构，默认初始化大小是16，加载因子是0.75，扩容后的大小是原来的2倍。
HashMap put 是通过hash算法和取模运算来获取下标，存放数据。
HashMap get 是通过获取下标，遍历链表获取数据
3.HashMap什么时候扩容
当数组长度大于阀值的时候进行扩容
4.HashMap扩容为什么是2的次幂
必须是2的次幂，减少hash碰撞，使得数据分布更加散列
5.HashMap怎么解决hash碰撞
当产生hash碰撞的时候，对象会存储到链表的下一个节点中