java集合之Map

发表于 2020-08-13 更新于 2020-12-25 分类于 java

Java Map

Set 与 Map家族

Set： hashSet, LinkedHashSet （HashSet + LinkedList）,TreeSet

Map: HashMap, LinkedHashMap (hashMap + 双向链表)， TreeMap

Screen Shot 2020-08-14 at 1.43.38 PM

Hash函数 -> Bucket

冲突

重写hashcode + equals， Object做key时，hashcode 和equal 一致。否则，两个逻辑相同的对象，会到不同bucket。

OBject Default：

equal：同一个reference
hashcode：不同对象返回唯一的哈希值

链地址 + 开放地址法： 1.8 之前，bucket后加链表存储hashcode的相同, 1.8 引入红黑树

jdk1.8: 当链表长度太长（默认超过 8）时，链表就转换为红黑树。我们可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。当红黑树结点个数少于 8 个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。

preview

rehashing

capacity
load factor ： 加载因子 = 填入表中的元素个数 / 散列表的长度

如果超过load factor（0.75），数组扩容至2倍，导致重新计算的bucket index发生变化

高并发的rehashing以及线程安全¹

例如在resize的临界点，多线程执行put ； resize + rehash 会导致并发问题。

在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

参考

高并发下的HashMap

为什么HashMap是线程不安全的吗

详解并发下的HashMap以及JDK8的优化

LinkedHashMap

LinkedHashMap = HashMap + 双向链表。

可以按照插入的顺序(或者访问顺序)输出，取决于accessOrder (true时表示按访问顺序排序，false表示按插入顺序排序。)

accessOrder 为true, get 和 update 都会把元素挪到双向链表的尾部（类似LRU）

TreeMap

treeMap底层是红黑树，按照key的自然顺序（或指定顺序comparator）

NavigableMap
SortedMap

head, tail, floor , ceiling ...

HashMap 1.8 源代码

成员变量：

/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) */

Node<K,V>[] table
int size;

/**
The number of times this HashMap has been structurally modified
Structural modifications are those that change the number of mappings in
the HashMap or otherwise modify its internal structure (e.g.,
rehash). This field is used to make iterators on Collection-views of
the HashMap fail-fast. (See ConcurrentModificationException). */
int modCount;
threshold;
loadFactor

put 方法

resize 方法

Screen Shot 2020-08-14 at 2.59.14 PM

newCap = oldCap << 1  // new cap 设置为原来两倍，通过移位操作

// 旧数据迁移

// 若节点是单个节点，直接在 newTab　中进行重定位
if (e.next == null)
	newTab[e.hash & (newCap - 1)] = e;

// 若节点是　TreeNode 节点，要进行 红黑树的 rehash　操作
else if (e instanceof TreeNode)
  ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

// 若是链表，进行链表的 rehash　操作
else { // preserve order
  Node<K,V> loHead = null, loTail = null;
  Node<K,V> hiHead = null, hiTail = null;
  Node<K,V> next;
  // 将同一桶中的元素根据(e.hash & oldCap)是否为0进行分割，分成两个不同的链表，完成rehash
  do {
    next = e.next;
    // 根据算法　e.hash & oldCap 判断节点位置rehash　后是否发生改变
    //最高位==0，这是索引不变的链表。
    if ((e.hash & oldCap) == 0) { 
      if (loTail == null)
        loHead = e;
      else
        loTail.next = e;
      loTail = e;
    }
    //最高位==1 （这是索引发生改变的链表）
    else {  
      if (hiTail == null)
        hiHead = e;
      else
        hiTail.next = e;
      hiTail = e;
    }
  } while ((e = next) != null);
  if (loTail != null) {  // 原bucket位置的尾指针不为空(即还有node)  
    loTail.next = null; // 链表最后得有个null
    newTab[j] = loHead; // 链表头指针放在新桶的相同下标(j)处
  }
  if (hiTail != null) {
    hiTail.next = null;
    // rehash　后节点新的位置一定为原来基础上加上　oldCap
    newTab[j + oldCap] = hiHead;
  }
}