Java容器类介绍
这里主要介绍常用的集合的结构。
涉及到ArrayList,HashSet,LinkedList,TreeSet，HashTable，ConcurrentHashMap。
容器类分为Collection和Map这里是摘抄自网上的一张继承关系图。
Map是用于保存具有映射关系的数据(key——value)
关于HashMap，之前有一篇文章讲到过，区别于ArrayMap，HashTable。
HashMap小解
基本的Api就不写了，主要写写区别。
HashSet
实现
HashSet实现了Set接口，去看他的构造函数，你会发现他其实是包装了一个HashMap
public HashSet() {
map = new HashMap<>();
}
所以，在不看他代码之前，你有没有什么想法呢。显然，他有Set的属性，其他的添加删除以及判断方法都和HashMap有关。比如 add()方法：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
<strong>这里有个点，hashset判断两个对象是否相同，用的是和hashmap判断key一个方法，只不过key变成了当前的object</strong>
可能你会好奇这个PRESENT是干嘛的，
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
假如让我来设计这个HashSet，我哪里会那么多脑细胞给你想这个，但是我懂HashMap啊，刚好HashMap的key不会重复，可以拿来用。判断是否添加成功就看在put的时候，这个值是不是null(知识点：HashMap的put方法会返回oldValue)。至于value放什么无所谓了，HashSet造了个假数据，就叫PRESENT
诶，这里就有疑问了，为什么不直接用null呢，效率高。
- HashSet的remove
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
<strong>用的是hashmap的remove，那你想啊，我remove之后返回了个null，我是remove掉一个null呢，还是本身就没有这个key。但是用PRESENT就不一样了，你不可能和我一样。</strong>
（最近晚上睡不着会听相声，写个博客都像在说单口）
LinkedHashSet
实现
他的实现说来写的也简单。直接在构造函数那里就留一个配置项给子类。
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
不得不佩服作者的这些巧妙的地方，就像以前写作文，谁都会背书上的那些古诗，可是能把他们融入到作文中的才厉害。
Hashtable
我几乎每次面试都会问到Hashtable。
实现
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {...}
public class HashMap<K, V>
extends AbstractMap<K, V>
implements Map<K, V>, Cloneable, Serializable {...}
这样看比较明显。
我们发现他俩直接父类不一样，Dictionary是个什么鬼？
- The <code>Dictionary</code> class is the abstract parent of any
- class, such as <code>Hashtable</code>, which maps keys to values.
- Every key and every value is an object. In any one <tt>Dictionary</tt>
- object, every key is associated with at most one value. Given a
- <tt>Dictionary</tt> and a key, the associated element can be looked up.
- Any non-<code>null</code> object can be used as a key and as a value.
- As a rule, the <code>equals</code> method should be used by
- implementations of this class to decide if two keys are the same.
- <strong>NOTE: This class is obsolete（过时）. New implementations should
- implement the Map interface, rather than extending this class.</strong>
哈哈，这段英文大概都能看得懂， 简单讲了自己是键值对的一个父类，你需要重写equals方法，但是已经过时了，推荐你用map接口(ConcurrentHashMap)。
讲归这么讲，但是面试官问你你总不能说过时了吧，知其然知其所以然嘛。
详细的代码就自己去看吧，他是JDK1.0引入的，和hashmap(JDK1.2)非常相似，
public synchronized V put(K key, V value) {...}
从这里你也看得出，他是线程安全的，同时加了重入锁之后也会有效率低下的问题。
区别于HashMap
继承父类
hashtable线程安全
-
hashtable的value和key为null的时候会空指针，hashmap的key为null的时候会放在第0个位置。但是看代码的时候你会发现hashtable只对value做了null判断，key为null是在key.hashcode()之后，给了个运行时异常，这里不是很懂为什么作者不直接判断。
Hashtable public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } HashMap public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); ··· } private V putForNullKey(V value) { ··· addEntry(0, null, value, 0); return null; } -
HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。 HashTable的 containsValue方法直接返回了contains方法，可能在那个年代这样做是为了人性化？
public boolean containsValue(Object value) { return contains(value); } 两个遍历方式的内部实现上不同。Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。
hash值不同。哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。
ConcurrentHashMap
你可以使用Collections.synchronizedMap(HashMap)来包装HashMap作为同步容器，这时它的作用几乎与Hashtable一样,当每次对Map做修改操作的时候都会锁住这个Map对象，而ConcurrentHashMap会基于并发的等级来划分整个Map来达到线程安全，它只会锁操作的那一段数据而不是整个Map都上锁。
实现
ConcurrentHashMap,Hashtable,Collection.synchronizedMap区别
Hashtable和Collection.synchronizedMap的实现方式类似，在所有方法上都加了synchronized锁，唯一一点区别就是，后者有更多的扩展性，只要是map都可以进行线程安全的处理
Collection.synchronizedMap(HashMap),Collection.synchronizedMap(ArrayMap)ConcurrentHashMap默认支持16个线程并发访问，而不用添加外部的锁，内部用了CAS锁技术，JDK8之前用的是分段锁(Segment[可以了解一下这俩锁])。处理并发请求的时候，他并不是将整个map锁住，ConcurrentHashMap的锁的粒度达到哈系桶的水平，只锁住部分，所以它处理并发的性能比其他两个好太多。
ConcurrentHashMap和Hashtable一样不允许空值，但是Collection.synchronizedMap允许.
延伸【SynchronizedList和Vector的区别】
他俩的关系和Collection.synchronizedMap与Hashtable有些像，vector的锁加在方法上，synchronizedList锁在代码块上，代码很简单，看代码能发现add()方法中明显的区别。
Vector的实现：
public void add(int index, E element) {
insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1);
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj;
elementCount++;
}
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
synchronizedList的实现：
public void add(int index, E element) {
synchronized (mutex) {
list.add(index, element);
}
}
ArrayList的add方法:
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
如果使用add方法，那么他们的扩容机制不一样(vector和arraylist的扩容区别),ArrayList以1.5倍的方式在扩容、Vector 当扩容容量增量大于0时、新数组长度为原数组长度+扩容容量增量、否则新数组长度为原数组长度的2倍。
-
SynchronizedList可以指定锁定的对象
mutex(SynchronizedMap不支持，锁定对象是自己生成的)。static <T> List<T> synchronizedList(List<T> list, Object mutex) { return (list instanceof RandomAccess ? new SynchronizedRandomAccessList<>(list, mutex) : new SynchronizedList<>(list, mutex)); }
小结
深入的东西肯定还有很多，比如树TreeMap。每天上班的时间也很拥挤，先介绍到这里吧。
革命尚未成功，同志仍需努力！
