Java集合—

Map集合

在这里插入图片描述

Map用于保存具有映射关系的数据，以键值对的形式存储，支持通过key来访问value，因此key不能重复。

Map接口下主要有Hashtable、HashMap、LinkedHashMap、ConcurrentHashMap 四个主要的实现类，实现的基本原理类似，主要详解HashMap和ConcurrentHashMap

1. HashMap

使用频率最高的键值存储集合，底层采用数组+链表+红黑树存储数据 (JDK1.8) 。访问速度快，线程不安全，最多允许一个key为null ，允许多个value为null

hashCode()对key求哈希值，然后根据哈希值和数组长度-1 做与运算 得到数组下标位置，数组中存储的值存放的是key value组成的结点，如果两个两个key不同但是哈希值相同，就在对应数组位置创建一个链表，如果链表长度超过8，此时数组长度 >= 64 链表转为红黑树，否则扩容数组。（详见哈希冲突和哈希函数）

在JDK1.7中HashMap 底层采用数组+链表实现，且链表采用头插法，在多线程并发环境下rehash扩容容易造成死循环（详见 Java HashMap的死循环）

如果创建是不指定大小 HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍，如果指定大小

HashMap 会将其扩充为 2 的幂次方大小（为了方便求数组下标）

指定容量和负载因子的构造函数（负载因子是哈希表中键值对 / 数组容量 0.75是时间和空间的综合考量）

   // 默认容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量static final int MAXIMUM_CAPACITY = 1 << 30;//默认负载因子 0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 有参构造函数
public HashMap(int initialCapacity, float loadFactor) {// 初始化容量<0 报非法参数异常if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);// 大于最大容量就初始化为最大容量if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// 负载因子<=0 或为NaN 报非法参数异常if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);
}

tableSizeFor方法保证容量是 2 的幂次方大小

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;
}

put过程

public V put(K key, V value) {return putVal(hash(key), key, value, false, true); 
}// onlyIfAbsent参数如果是true，那么只有不存在该key时才会进行put操作，默认为false可以覆盖
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 第一次put的时，通过resize()创建数组并初始化数组长度if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 寻找数组下标，如果该位置没有值，直接初始化一个结点，将key value存入结点，并把结点放入数组if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// 数组该位置已经存在数据Node<K,V> e; K k;// 首先，判断该位置第一个数据与待put的key是否equals相等，相等就取出这个结点if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 如果该节点是代表红黑树的结点，调用红黑树插值方法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);// TREEIFY_THRESHOLD为8，如果新增元素是第8个尝试转化红黑树if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);break;}// 在链表中 找到了equals相等的key，取出这个结点if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 结点不为null说明存在equals相等的key，需要进行value覆盖 并返回旧值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;// 如果新put的元素导致size超过了阈值，需要扩容if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

resize() 方法用于初始化数组或数组扩容，如果是扩容，扩容后容量为原来的 2 倍

get()过程分析

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}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 && ((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 {// 遍历链表查找keyif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}// 没有找到就返回nullreturn null;
}

2. Hashtable

Hashtable与HashMap类似，底层采用数组+链表实现。不过Hashtable是线程安全的，通过加synchronized关键字保证，不允许key和value为null，在并发性上不如ConcurrentHashMap

为什么Hashtable效率低

因为synchronized 关键字对整个对象进行加锁，锁住了Hash表

3. ConcurrentHashMap

与HashMap 类似唯一区别在于ConcurrentHashMap 是线程安全的 key和value不能为null

JDK1.7，底层采用分段的数组+链表 ，使用分段锁保证线程安全。

ConcurrentHashMap在对象中保存了一个Segment数组，将整个Hash表划分为多个分段（默认16段）；而每个Segment元素，即每个分段则类似于一个Hashtable。在执行put操作时首先根据hash算法定位到元素属于哪个Segment，然后对该Segment加锁而不影响其他Segment。因此，ConcurrentHashMap在多线程并发编程中可是实现多线程put操作。Segment 通过继承 ReentrantLock 来进行加锁

JDK1.8，ConcurrentHashMap 底层采用数组+链表+红黑树，加锁采用CAS和synchronized实现。锁粒度更细，synchronized 只锁当前链表或红黑树的首节点，这样只要 hash值 不冲突，就不会发生并发，不会影响其他 Node结点的读写，效率大幅提升。

put()过程

public V put(K key, V value) {return putVal(key, value, false);
}final V putVal(K key, V value, boolean onlyIfAbsent) {// key和value不能为nullif (key == null || value == null) throw new NullPointerException();// 计算hash值int hash = spread(key.hashCode());// 记录链表的长度int binCount = 0;for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;// 数组为null或空 就初始化数组if (tab == null || (n = tab.length) == 0)tab = initTable();// 找到hash值对应的数组下标，下标的第一个结点felse if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// 如果数组该位置为空，通过一次CAS操作将这个值放入 结束// 如果CAS失败，说明有并发，循环进行下一次CAS操作if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))break;                  }// 需要扩容else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);// f为该位置的头结点，且不为nullelse {V oldVal = null;// 获取头结点的监视器锁synchronized (f) {if (tabAt(tab, i) == f) {// 头结点的hash值>=0 说明是链表if (fh >= 0) {//累计链表的长度binCount = 1;// 遍历链表for (Node<K,V> e = f;; ++binCount) {K ek;// 如果有equals相等的key，判断是否进行值覆盖 随后breakif (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {oldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}// 链表中不存在该key，插入链表尾部Node<K,V> pred = e;if ((e = e.next) == null) {pred.next = new Node<K,V>(hash, key,value, null);break;}}}// 红黑树else if (f instanceof TreeBin) {Node<K,V> p;binCount = 2;// 往红黑树中插入新节点if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}}if (binCount != 0) {// 判断是否将链表转化为红黑树，临界值为8// 如果数组长度小于64 选择扩容数组而不转红黑树if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}addCount(1L, binCount);return null;
}

get()过程

public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;// 计算哈希值int h = spread(key.hashCode());// 找数组对应位置if ((tab = table) != null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) != null) {if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;}// 如果头结点的 hash值 < 0 说明 正在扩容/该位置为红黑树else if (eh < 0)return (p = e.find(h, key)) != null ? p.val : null;// 遍历链表查找while ((e = e.next) != null) {if (e.hash == h &&((ek = e.key) == key || (ek != null && key.equals(ek))))return e.val;}}// 不存在 返回nullreturn null;
}