JAVA容器相关
HashMap HashTable TreeMap
HashMap的底层实现
Map的最核心结构是table，是一个Node(JDK1.8之前的是Entry)类型的数组，而Node的实现又是一个链表或者是一个红黑树的节点(TreeNode)。如下图所示： 
HashMap的源码实现(1.6和1.8的实现不同,处理hashcode冲突的方法)
构造函数
HashMap的构造方法有三种，如下所示：
// 无参构造方法 HashMap<String, String> map1 = new HashMap<String, String>(); // 含参数构造方法 HashMap<String, String> map2 = new HashMap<String, String>(16); HashMap<String, String> map3 = new HashMap<String, String>(16,0.75F); public HashMap(int initialCapacity, float loadFactor); public HashMap(int initialCapacity); public HashMap();
HashMap中以下几个变量十分重要：
- int threshold，定义数组的长度（阈值），如果HashMap内的数据超过阈值*负载因子(threshold * loadFactor)，就会发生扩容操作。threshold一般是2的平方数。
- float loadFactor，负载系数。
- int capacity，初始容量，用来计算threshold阈值。
默认的构造方法会赋值loadFactor为默认的0.75,初始化容量为1<<4即16，所以可以得出当默认的HashMap容量达到16*0.75=9的时候，便会发生扩容操作。 一个参数的构造方法传入的是初始容量，两个参数的构造方法传入的是初始容量和负载因子，然后根据传入的初始容量和负载因子计算阈值。
put()方法
- 对key的HashCode()再做hash,然后计算数组的下标
- 如果该下标下无数据，直接放入该存储桶内
- 如果下标冲突了，去比较key值，如果在该下标的链表或红黑树上没有相同的key值，说明发生了hash冲突，则将该值链接在链表后或者存在红黑树
- 如果该下标下有相同的key值，说明发生了元素替换
- 如果存储数量超过负载因子*容量，会发生resize操作
- 在JDK1.8中如果链表过长会转化为红黑树存储
public V put(K key, V value) { // 对key的hashCode()做hash return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // tab为空则创建 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 计算index，并对null做处理 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 节点存在 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); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 写入 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 超过load factor*current capacity，resize if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
get()方法
- 根据传递的key的hashCode()再hash，然后计算下标
- 查找该下标下的值，通过遍历链表或红黑树，找到key相同的一个值
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 && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // 未命中 if ((e = first.next) != null) { // 在树中get if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); // 在链表中get do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
hash()方法的实现
调用hashCode得到Key的hashcode，然后用该值异或该值的高16位，得到新的hash值，然后用hashMap初始化的大小-1和该hash值取与，便得到了下标： 
resize()方法的实现
当目前的存储桶已经使用超过容量*负载因子的时候便会发生resize()操作，简单地说就是把数组扩大两倍，然后重新计算数组下标，把节点放入新的存储桶内。元素要么在原位置，要么会移动到原位置+2次幂的位置。 扩充HashMap的时候，不需要进行重新hash操作，只需要将原来的hash值新增1bit即可，如果为0，下标不变，如果为1，变为原来的下标+原始长度的位置，如下图所示：
代码实现如下：
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 超过最大值就不再扩充了，就只好随你碰撞去吧 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 没超过最大值，就扩充为原来的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 计算新的resize上限 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { // 把每个bucket都移动到新的buckets中 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 原索引 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 原索引+oldCap else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 原索引放到bucket里 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 原索引+oldCap放到bucket里 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
HashMap的同步类ConcurrentHashMap的实现(锁分离技术)
本文主要解析的是JDK1.6中的ConcurrentHashMap实现，1.8与其实现稍有不同，ConcurrentHashMap的实现主要解决了以下三个问题：
- 通过锁分段技术保证并发下的写操作
- 通过保证HashEntry next属性的不变性，Volatile变量的可见性和加锁重读机制保证读操作的高效性
- 通过不加锁计算两遍比对和加锁计算保证size()等跨段方法的最终一致性
原理图
其余参考： JDK1.6中的ConcurrentHashMap实现
HashMap在1.6和1.8之间的区别
- Hash桶冲突处理不同，1.6采用的是链表处理，通过key依次查找，如果冲突比较多时效率会降低，1.8采用的是链表+红黑树存储，链表长度超过阈值时，会转换为红黑树，效率增加
- 优化了hash算法，使高位和地位都参与运算
- 扩容机制，不需要重新计算hash值，只需要根据hash值的新增的一位来确定将其索引变为1+扩容长度（新增的一位为1）或不改变位置（新增的一位为0）
HashMap的相关问题
HashMap和HashTable的区别
HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。 HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。
HashMap和HashSet的区别
| HashMap | HashSet |
|---|---|
| HashMap实现了Map接口 | HashSet实现了Set接口 |
| HashMap储存键值对 | HashSet仅仅存储对象 |
| 使用put()方法将元素放入map中 | 使用add()方法将元素放入set中 |
| HashMap中使用键对象来计算hashcode值 | HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false |
| HashMap比较快，因为是使用唯一的键来获取对象 | HashSet较HashMap来说比较慢 |
同步容器
简介
同步容器是JAVA内部提供的并发工具类（但不但表可以直接使用在并发环境中），可以简单的理解为普通容器使用了synchronized修饰，因为普通的容器类或接口，如ArrayList、LinkedList、HashMap类等，是不能直接用在多线程环境中的。
同步容器分类
可以简单的将JAVA中的同步容器分为一下几种：
Vector:可以简单的理解为一个synchronized修饰的ArrayList，其中的set或get方法都是使用synchronized修饰的。
HashTable: 实现了Map接口，对HashMap中的put和get等方法使用了synchronized修饰。
其他
创建同步容器和普通容器不同，可以使用Collections类创建，Collections类提供了不同的同步容器类的工厂构造方法。
使用同步容器类会使插入或读取的性能降低，因为其使用了synchronized修饰，其只能有一个线程进行读取或插入操作。但是可能会出现一个线程进行读取，另一个线程执行删除的操作，从而导致抛出ConcurrentModificationException异常，该异常在单线程环境下，该异常主要出现在其迭代操作数组中的元素时，可以使用iterator的remove方法解决，多线程环境下则需要对多线程使用synchronized或使用并发容器CopyOnWriteArrayList代替Vector或ArrayList。
并发容器CopyOnWriteList和CopyOnWriteSet
简介
除了上方的ConcurrentHashMap之外，并发容器还有CopyOnWriteList和CopyOnWriteSet，CopyOnWrite是一种读写优化策略，即读操作所有的线程都操作同一份实例，在需要写操作时，便复制一份副本进行写入，写入完成之后，将指针指向新的实例，便可以实现并发读操作。CopyOnWrite容器在写入时会加锁，以免复制出多份副本，不能保证最终一致性，但是在读取时是不会加锁的，而且写入过程中会保持两份内存副本，原来数据会保持不变，因为新容器中保存的是原容器对象的引用，只有新写入的对象才会添加到新容器中。因此其适用于读取多更新少的场景，且不适用于实时一致性较高的场景。
源码参考
这里我们参考CopyOnWrite的原理，实现一个CopyOnWriteMap，其代码如下：
import java.util.Collection; import java.util.Map; import java.util.Set; public class CopyOnWriteMap<K, V> implements Map<K, V>, Cloneable { private volatile Map<K, V> internalMap; public CopyOnWriteMap() { internalMap = new HashMap<K, V>(); } public V put(K key, V value) { synchronized (this) { Map<K, V> newMap = new HashMap<K, V>(internalMap); V val = newMap.put(key, value); internalMap = newMap; return val; } } public V get(Object key) { return internalMap.get(key); } public void putAll(Map<? extends K, ? extends V> newData) { synchronized (this) { Map<K, V> newMap = new HashMap<K, V>(internalMap); newMap.putAll(newData); internalMap = newMap; } } }