一 特性

  • 使用hash方法进行区分key
  • 可以存在一个为null的key
  • 线程不安全
  • HashMap在多线程情况下，rehash过程中有可能导致Entry产生环形链

  • 每次扩容原来2倍的大小

    二 属性

    1.   //默认容量 16
    2.   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    3.   //最大容量，2的30次方。
    4.   static final int MAXIMUM_CAPACITY = 1 << 30;
    5.   //加载因子，用于扩容使用。
    6.   static final float DEFAULT_LOAD_FACTOR = 0.75f;
    7.   //当某个桶节点数量大于8时，会转换为红黑树。
    8.   static final int TREEIFY_THRESHOLD = 8;
    9.   //当某个桶节点数量小于6时，会转换为链表，前提是它当前是红黑树结构。
    10.   static final int UNTREEIFY_THRESHOLD = 6;
    11.   //当整个hashMap中元素数量大于64时，也会进行转为红黑树结构。 只有链表中元素到达伐值之后才会进行树化
    12.   static final int MIN_TREEIFY_CAPACITY = 64;
    13.   //存储元素的数组，transient关键字表示该属性不能被序列化
    14.   transient Node<K,V>[] table;
    15.   //将数据转换成set的另一种存储形式，这个变量主要用于迭代功能。
    16.   transient Set<Map.Entry<K,V>> entrySet;
    17.   //元素数量
    18.   transient int size;
    19.   //统计该map修改的次数
    20.   transient int modCount;
    21.   //临界值，也就是元素数量达到临界值时，会进行扩容。
    22.   int threshold;
    23.   //也是加载因子，只不过这个是变量。
    24.   final float loadFactor;

    三 重要方法

  • tableSizeFor

    • 返回大于输入参数且最近的2的整数次幂的数 这里8针对7进行了优化
  • hash
    • 将key的hash值右移动16位后再做异或运算，也是这里限制了容量必须是2的N次方

  • resize

    • 扩容方法

      四 构造方法

  • HashMap(int initialCapacity, float loadFactor)

    • 使用给定的容量和加载因子初始化
  • HashMap(int initialCapacity)
    • 使用给定的容量初始化
  • HashMap()
    • 初始化空的

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

    • 使用给定的map初始化，加载因子使用默认的

      五 添加元素

      1. public V put(K key, V value) {
      2.    return putVal(hash(key), key, value, false, true);
      3. }
      5. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
      6.               boolean evict) {
      7.    //tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标
      8.    Node<K,V>[] tab; Node<K,V> p; int n, i;
      10.    //获取长度并进行扩容，使用的是懒加载，table一开始是没有加载的，等put后才开始加载 调用resize进行加载
      11.    if ((tab = table) == null || (n = tab.length) == 0)
      12.        n = (tab = resize()).length;
      14.    /**如果计算出的该哈希桶的位置没有值，则把新插入的key-value放到此处，此处就算没有插入成功，也就是发生哈希冲突时也会把哈希桶的首节点赋予p**/
      15.    if ((p = tab[i = (n - 1) & hash]) == null)
      16.        tab[i] = newNode(hash, key, value, null);
      18.    else {
      19.        Node<K,V> e; K k;
      20.        //代表插入分重复的元素
      21.        if (p.hash == hash &&
      22.            ((k = p.key) == key || (key != null && key.equals(k))))
      23.            e = p;
      24.        //找到的节点但是是红黑树走红黑树逻辑
      25.        else if (p instanceof TreeNode)
      26.            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
      27.        else {
      28.            //遍历链表找到插入位置 尾插法
      29.            for (int binCount = 0; ; ++binCount) {
      30.                if ((e = p.next) == null) {
      31.                    p.next = newNode(hash, key, value, null);
      32.                    //这里达到树化的条件则会进行树化
      33.                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
      34.                        treeifyBin(tab, hash);
      35.                    break;
      36.                }
      37.                if (e.hash == hash &&
      38.                    ((k = e.key) == key || (key != null && key.equals(k))))
      39.                    break;
      40.                p = e;
      41.            }
      42.        }
      43.        //如果是重复插入则返回原来的元素
      44.        if (e != null) { // existing mapping for key
      45.            V oldValue = e.value;
      46.            if (!onlyIfAbsent || oldValue == null)
      47.                e.value = value;
      48.            afterNodeAccess(e);
      49.            return oldValue;
      50.        }
      51.    }
      52.    //插入后判断是否进行扩容
      53.    ++modCount;
      54.    if (++size > threshold)
      55.        resize();
      56.    afterNodeInsertion(evict);
      57.    return null;
      58. }

      六 删除元素

      1. public V remove(Object key) {
      2.    Node<K,V> e;
      3.    /**调用removeNode(hash(key), key, null, false, true)进行删除，第三个value为null，表示，把key的节点直接都删除了，不需要用到值，如果设为值，则还需要去进行查找操作**/
      4.    return (e = removeNode(hash(key), key, null, false, true)) == null ?
      5.        null : e.value;
      6. }
      8. /**第一参数为哈希值，第二个为key，第三个value，第四个为是为true的话，则表示删除它key对应的value，不删除key,第五个如果为false，则表示删除后，不移动节点**/
      9. final Node<K,V> removeNode(int hash, Object key, Object value,
      10.                           boolean matchValue, boolean movable) {
      11.    Node<K,V>[] tab; Node<K,V> p; int n, index;
      12.    //如果未初始化、删除的位置为空 长度小于0 的等直接返回
      13.    if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) {
      14.        Node<K,V> node = null, e; K k; V v;
      15.        //找到要删除的节点并赋值给node
      16.        if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
      17.            node = p;
      18.        else if ((e = p.next) != null) {
      19.            //对应hash位红黑树查找
      20.            if (p instanceof TreeNode)
      21.                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
      22.            else {
      23.                //链表查找，从头开始
      24.                do {
      25.                    if (e.hash == hash &&
      26.                        ((k = e.key) == key ||
      27.                         (key != null && key.equals(k)))) {
      28.                        node = e;
      29.                        break;
      30.                    }
      31.                    p = e;
      32.                } while ((e = e.next) != null);
      33.            }
      34.        }
      35.        //找到对应的节点进行处理
      36.        if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {
      37.            //红黑树删除
      38.            if (node instanceof TreeNode)
      39.                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
      40.            //是头结点的话则直接设置头结点为下个节点
      41.            else if (node == p)
      42.                tab[index] = node.next;
      43.            else
      44.                //断开，指向下个节点
      45.                p.next = node.next;
      46.            ++modCount;
      47.            --size;
      48.            afterNodeRemoval(node);
      49.            return node;
      50.        }
      51.    }
      52.    return null;
      53. }

      七 获取元素

      1. public V get(Object key) {
      2.    Node<K,V> e;
      3.    return (e = getNode(hash(key), key)) == null ? null : e.value;
      4. }
      6. final Node<K,V> getNode(int hash, Object key) {
      7.    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
      8.    //找到对应的位置的hash值
      9.    if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
      10.        //如果是头结点则直接返回
      11.        if (first.hash == hash && // always check first node
      12.            ((k = first.key) == key || (key != null && key.equals(k))))
      13.            return first;
      14.        //红黑树查找
      15.        if ((e = first.next) != null) {
      16.            if (first instanceof TreeNode)
      17.                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
      18.            //链表查找
      19.            do {
      20.                if (e.hash == hash &&
      21.                    ((k = e.key) == key || (key != null && key.equals(k))))
      22.                    return e;
      23.            } while ((e = e.next) != null);
      24.        }
      25.    }
      26.    return null;
      27. }

      八 tableSizeFor

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

      作用：该方法是求得大于给定值的最小的是2的整数幂的数。
      原理：2的整数幂用二进制表示都是最高有效位为1，其余全是0
      image.png
      核心思想是，先将最高有效位以及其后的位都变为1，最后再+1，就进位到前一位变成1，其后所有的满2变0。所以关键是如何将最高有效位后面都变为1。
      image.png
      基本就是不断的右异运算，再加上或运算，将0移出去，最后再加上1就得到了正确的数。

备注：
位移运算符相关知识：https://www.jianshu.com/p/927009730809
来源：https://www.cnblogs.com/xiyixiaodao/p/14483876.html

九 hash

  1.     static final int hash(Object key) {
  2.         int h;
  3.         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  4.     }
  6.     //具体的使用过程 找到对应的下标  计算结果和 hash % n 结果是一样的
  7.     (n - 1) & hash

首先看一下 (n - 1) & hash 这个如何求得的对应数组的位置，使用与运算。这样操作只能获取到长度的二进制的后边的几位数字。
比如：
n=16，则(n-1) = 15 = 01111
hash = 101010 = 42
&的时候高位补0 最终结果是 001010 = 10 = 42%16

再看下扰动函数
从上边可以看到使用的过程也就是保留低位的hash值，但是如果出现两个hash值的低位一样，就会发生hash冲突，所以使用扰动函数进行重新计算，保留高位特性，降低冲突的可能性

十 resize

  1.   final Node<K,V>[] resize() {
  2.           //老数组
  3.         Node<K,V>[] oldTab = table;
  4.           //老的长度 未初始化则为0
  5.         int oldCap = (oldTab == null) ? 0 : oldTab.length;
  6.           //老的临界值
  7.         int oldThr = threshold;
  8.           //新长度  新临界值
  9.         int newCap, newThr = 0;
  10.           //代表已经进行初始化过
  11.         if (oldCap > 0) {
  12.             //如果老的长度已经到达最大长度则不再进行扩容
  13.             if (oldCap >= MAXIMUM_CAPACITY) {
  14.                 threshold = Integer.MAX_VALUE;
  15.                 return oldTab;
  16.             }
  17.             //老的长度左移一位后小于最大长度 临界值也乘以2
  18.             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  19.                      oldCap >= DEFAULT_INITIAL_CAPACITY)
  20.                 newThr = oldThr << 1; // double threshold
  21.         }
  22.           //使用  HashMap(int initialCapacity, float loadFactor) 进行初始化的  oldCap是空的，但是oldThr不是
  23.         else if (oldThr > 0) // initial capacity was placed in threshold
  24.             newCap = oldThr;
  25.         else {
  26.             //首次初始化
  27.             // zero initial threshold signifies using defaults
  28.             newCap = DEFAULT_INITIAL_CAPACITY;
  29.             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  30.         }
  31.           //初始化临界值
  32.         if (newThr == 0) {
  33.             float ft = (float)newCap * loadFactor;
  34.             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  35.                       (int)ft : Integer.MAX_VALUE);
  36.         }
  37.         threshold = newThr;
  38.           //这里重新实例化一个数组
  39.         @SuppressWarnings({"rawtypes","unchecked"})
  40.             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  41.         table = newTab;
  42.           //实际的扩容操作
  43.         if (oldTab != null) {
  44.             //循环老数组每个节点进行扩容
  45.             for (int j = 0; j < oldCap; ++j) {
  46.                 Node<K,V> e;
  47.                 //如果老数组的当前节点不为空则开始迁移
  48.                 if ((e = oldTab[j]) != null) {
  49.                     //老节点位置先设置为null，减少引用
  50.                     oldTab[j] = null;
  51.                     if (e.next == null)
  52.                         //如果没有后续的节点则直接迁移，重新计算下标
  53.                         newTab[e.hash & (newCap - 1)] = e;
  54.                     else if (e instanceof TreeNode)
  55.                         //如果当前节点已经是红黑树则走红黑树的迁移
  56.                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  57.                     else { 
  58.                         //也就是链表的迁移 这里会将链表拆分成两个，拆分的依据是(e.hash & oldCap) == 0
  59.                         // preserve order
  60.                         Node<K,V> loHead = null, loTail = null;
  61.                         Node<K,V> hiHead = null, hiTail = null;
  62.                         Node<K,V> next;
  63.                         do {
  64.                             next = e.next;
  65.                             //根据(e.hash & oldCap) == 0 判断进行拆分链表 偏移量是oldCap
  66.                             if ((e.hash & oldCap) == 0) {
  67.                                 if (loTail == null)
  68.                                     loHead = e;
  69.                                 else
  70.                                     loTail.next = e;
  71.                                 loTail = e;
  72.                             }
  73.                             else {
  74.                                 if (hiTail == null)
  75.                                     hiHead = e;
  76.                                 else
  77.                                     hiTail.next = e;
  78.                                 hiTail = e;
  79.                             }
  80.                         } while ((e = next) != null);
  81.                         if (loTail != null) {
  82.                             loTail.next = null;
  83.                             newTab[j] = loHead;
  84.                         }
  85.                         if (hiTail != null) {
  86.                             hiTail.next = null;
  87.                             newTab[j + oldCap] = hiHead;
  88.                         }
  89.                     }
  90.                 }
  91.             }
  92.         }
  93.         return newTab;
  94.     }

十一 线程安全问题

1.7的扩容代码如下

  1. void resize(int newCapacity) {
  2.     Entry[] oldTable = table;
  3.     int oldCapacity = oldTable.length;
  4.     if (oldCapacity == MAXIMUM_CAPACITY) {
  5.         threshold = Integer.MAX_VALUE;
  6.         return;
  7.     }
  9.     Entry[] newTable = new Entry[newCapacity];
  10.     transfer(newTable, initHashSeedAsNeeded(newCapacity));
  11.     table = newTable;
  12.     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
  13. }
  15. // 新建一个数组并循环赋值 采用头插法
  16. void transfer(Entry[] newTable, boolean rehash) {
  17.     int newCapacity = newTable.length;
  18.     for (Entry<K,V> e : table) {
  19.         while(null != e) {
  20.             Entry<K,V> next = e.next;
  21.             if (rehash) {
  22.                 e.hash = null == e.key ? 0 : hash(e.key);
  23.             }
  24.             int i = indexFor(e.hash, newCapacity);
  25.             e.next = newTable[i];
  26.             newTable[i] = e;
  27.             e = next;
  28.         }
  29.     }
  30. }

1.7的扩容在并发的情况下会存在可能生成环、
1.8的扩容如上解析，会将链表拆分为两个链表，根据(e.hash & oldCap) == 0，这样会发生数据丢失的风险，一个线程已经将节点异走，但是最终更新table的的是另一个线程。

十二 树化操作

  1. //这里是插入的一段代码，在遍历链表的时候会判断当前链表是否超过TREEIFY_THRESHOLD 否则就会进行树化
  2. if ((e = p.next) == null) {
  3.      p.next = newNode(hash, key, value, null);
  4.      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  5.      treeifyBin(tab, hash);
  6.      break;
  7. }
  9. //解除树化 发生在resize阶段 将一个链表拆解为两个
  11.         final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
  12.             TreeNode<K,V> b = this;
  13.             // Relink into lo and hi lists, preserving order
  14.             TreeNode<K,V> loHead = null, loTail = null;
  15.             TreeNode<K,V> hiHead = null, hiTail = null;
  16.             int lc = 0, hc = 0;
  17.             for (TreeNode<K,V> e = b, next; e != null; e = next) {
  18.                 next = (TreeNode<K,V>)e.next;
  19.                 e.next = null;
  20.                 if ((e.hash & bit) == 0) {
  21.                     if ((e.prev = loTail) == null)
  22.                         loHead = e;
  23.                     else
  24.                         loTail.next = e;
  25.                     loTail = e;
  26.                     ++lc;
  27.                 }
  28.                 else {
  29.                     if ((e.prev = hiTail) == null)
  30.                         hiHead = e;
  31.                     else
  32.                         hiTail.next = e;
  33.                     hiTail = e;
  34.                     ++hc;
  35.                 }
  36.             }
  38.             if (loHead != null) {
  39.                 if (lc <= UNTREEIFY_THRESHOLD)
  40.                     tab[index] = loHead.untreeify(map);
  41.                 else {
  42.                     tab[index] = loHead;
  43.                     if (hiHead != null) // (else is already treeified)
  44.                         loHead.treeify(tab);
  45.                 }
  46.             }
  47.             if (hiHead != null) {
  48.                 if (hc <= UNTREEIFY_THRESHOLD)
  49.                     tab[index + bit] = hiHead.untreeify(map);
  50.                 else {
  51.                     tab[index + bit] = hiHead;
  52.                     if (loHead != null)
  53.                         hiHead.treeify(tab);
  54.                 }
  55.             }
  56.         }

十三 常见问题

HashTable和HashMap的区别？

  • HashTable是线程安全的，HashMap是线程不安全的。
  • HashTable中的value不能为null，否责会抛出空指针异常。
  • HashTable扩容时，新数组长度为原数组长度的二倍加一，HashMap是原来的二倍。
  • HashTable的扩容方式是遍历数组位值，遍历链表用key的hash值与数组长度直接取余，之后使用头插法插入。HashMap是遍历数组，之后遍历链表生成高低位两个链表，使用的尾插法，之后将两个链表分别放到原位置和原位置加原数组长度位置。

  • HashTable只使用链表，HashMap在链表长度操作8时会将链表转化为红黑树。

    ConcurrentHashMap和HashTable选择？

  • 毫无疑问选择ConcurrentHashMap，HashTable是将方式用synchronized锁住，即使同时插入的键值对对应的数组index不同也会阻塞。ConcurrentHashMap（1.8）是通过锁数组index位置的节点来控制并发，这样即使同时插入，但是如果在数组的index不同也可以同时插入，而且ConcurrentHashMap使用了大量的cas操作，降低了线程在不同状态转化的消耗，ConcurrentHashMap源码解析以后会写。

    HashMap数组长度为什么必须是2的整数次幂

  • 数组下标通过hash & (n - 1)来进行计算，当数组长度n为2的正数次幂时，n-1结果的二进制全都是1，这样可以使得&操作的结果更加分散。如果n不是2的幂次，那么减1就可能有的位是0，那么与hash值做&操作，无论hash值的对应位是0还是1都会被散列到同一个位置。

  • 因为hashmap确定键值对位置是通过key的hash值与数组长度减一做与操作来确定，只有数组长度是2的整数次幂才能使(hash & (length-1)) == (hash % length)。

    HashMap的hash函数为什么要对高16位做异或操作

  • 这个操作叫做扰动函数，因为这样可以结合hash值的高16位的特性，减少低16位相同高16位不相同的key发生碰撞，减少hash冲突概率。

    有什么方法可以减少碰撞？

  • 扰动函数可以减少碰撞

  • 使用String，Interger这样的wrapper类作为键是非常好的选择。

    拉链法导致的链表过深问题为什么不用二叉查找树代替

  • 之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构

  • 红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快，解决链表查询深度的问题

    解决hash 碰撞还有那些办法

  • 开放定址法