HashMap

HashMap 1.7

数据结构： 数组+链表

元素结构：Entry

1
2
3
4
5
6
static class Entry<K,V> implements Map.Entry<K,V>{
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
}

capacity：当前数组容量，始终保持 2^n，可以扩容，扩容后数组大小为当前的 2 倍。

loadFactor：负载因子，默认为 0.75。

threshold：扩容的阈值，等于 capacity * loadFactor

HashMap如果key为null则放入table[0]中

遍历完链表发现没有key，就需要添加entry。

添加entry前判断是否需要扩容（如果当前 HashMap 大小已经达到了阈值，并且新值要插入的数组位置已经有元素了，那么要扩容）

put 过程分析

  1. 如果HashMap未被初始化，则初始化
  2. 如果key为null，则下标为0
  3. 如果key不为null，计算hash值并找到对应下标
  4. 遍历下标处的链表看是否存在重复key，存在则覆盖。
  5. 不存在的话，判断是否需要扩容。
  6. 不需要扩容就将entry头插法添加到链表中。

get 过程分析

相对于 put 过程，get 过程是非常简单的。

  1. 根据 key 计算 hash 值。
  2. 找到相应的数组下标：hash & (length - 1)。
  3. 遍历该数组位置处的链表，直到找到相等(==或equals)的 key。

HashMap扩容死锁问题

因为在 JDK1.7 中采取的是头插法，遍历一个节点就插入一个节点到新的哈希桶数组，所以才会导致出现循环链表。但 JDK1.8 中是采用两个头结点来保持旧链表的引用，直到该索引处对应的链表全部遍历完之后再分别把头结点放在新的哈希桶数组对应的位置。而不是遍历一个节点就插入一个节点到新的哈希桶数组。所以不会出现死链。

HashMap 1.8

将Entry改名为Node

Java7 是先扩容后插入新值的，Java8 先插值再扩容

Java7是头插法，Java8是尾插法

put方法的逻辑

  1. 如果HashMap未被初始化，则resize初始化

  2. 对Key求Hash值，然后再计算下标

  3. 如果没有碰撞，直接放入桶中

  4. 如果碰撞了，key相等就取出节点

  5. 如果是红黑树就以红黑树的方式插入节点，如果为链表以链表的方式链接到后面，

  6. 如果插入后链表长度超过阈值8，就把链表转成红黑树

  7. 如果节点已经存在就替换旧值

  8. 如果桶满了（容量16*加载因子0.75），就需要resize（扩容2倍后重排）

get方法的逻辑

  1. 计算 key 的 hash 值，根据 hash 值找到对应数组下标: hash & (length-1)

  2. 判断数组该位置处的元素是否刚好就是我们要找的

  3. 如果不是，判断该元素类型是否是 TreeNode，如果是，用红黑树的方法取数据。

    4 . 如果不是，遍历链表，直到找到相等(==或equals)的 key。