1 Java集合概览
2 List接口下集合源码分析
2.1 ArrayList
（1）集合体系
（2）基本使用
//实例化
ArrayList<Integer> list = new ArrayList<>(5);
//添加元素
list.add(1);
list.add(2);
//遍历元素
for (Integer i : list) {
System.out.print(i);
}
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i));
}
//删除元素
System.out.println(list.remove(0));
（3）源码剖析
线程安全问题：线程不安全public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}理由：没有任何线程同步机制和分段锁等保护线程安全的措施扩容机制：当元素添加满时将数组大小扩大1.5倍//主要是调用grow方法进行扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}元素是否可以为null：可以为nullpublic boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}添加元素时并没有代码要求元素不能为null2.2 LinkedList
（1）集合体系
（2）基本使用
//实例化
LinkedList linkedList = new LinkedList();
//添加元素
linkedList.add(23);
linkedList.add(44);
linkedList.add(12);
//删除元素，删除的是第一个结点
linkedList.remove();
//修改某个结点对象
linkedList.set(1, 999);
//获取链表的第二个对象
Object o = linkedList.get(1);
//遍历
Iterator iterator = linkedList.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.print(next);
}
for (Object o1 : linkedList) {
System.out.print(o1);
}
for (int i = 0; i < linkedList.size(); i++) {
System.out.print(linkedList.get(i));
}
（3）源码剖析
是否需要扩容：不需要扩容，添加元素时直接放在队列的尾部，由上一个元素的next指针指该元素public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}删除元素过程：将被删除元素的上一个节点的next指针指向被删除元素的下一个节点public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}2.3 Vector
（1）集合体系
（2）基本使用
//实例化
Vector vector = new Vector(18);
//添加元素
vector.add(100);
（3）源码剖析
是否线程安全：线程安全，具有互斥锁synchronizedpublic synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}扩容机制：当元素添加满时默认将数组大小扩大2倍，可以实例化时指定扩容的大小capacityIncrementprivate void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}3 Set接口下集合源码分析
3.1 HashSet
（1）集合体系
（2）基本使用
HashSet hashSet = new HashSet();
hashSet.add(null);
hashSet.add(null);
hashSet.add("2");
System.out.println("hashSet=" + hashSet);
hashSet.forEach(s -> System.out.println(s));
hashSet.remove(null);
System.out.println(hashSet.contains("2"));
System.out.println(hashSet.contains(null));
（3）源码剖析
底层：HashMappublic HashSet() {
map = new HashMap<>();
}add方法：将HashMap的减存放元素，将HashMap的值放入空对象PRESENT，然后直接调用HashMap的add方法// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}元素是否可以为null：可以3.2 TreeSet
（1）集合体系
（2）基本使用
TreeSet treeSet = new TreeSet(new Comparator() {
//排序规则
@Override
public int compare(Object o1, Object o2) {
return ((String) o1).compareTo((String) o2);
}
});
treeSet.add("zs");
treeSet.add("ls");
treeSet.add("ww");
treeSet.add("zl");
（3）源码剖析
自定义元素排序规则：TreeSet treeSet = new TreeSet(new Comparator() {
//排序规则 o1和o2代表先后元素的比较规则 (String) o1).compareTo((String) o2表示比较字符串的阿斯卡码 相同时不放入
@Override
public int compare(Object o1, Object o2) {
return ((String) o1).compareTo((String) o2);
}
});add方法：底层调用了TreeMap的put方法 m.put(e, PRESENT)public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}3.3 LinkedHashSet
（1）集合体系
（2）基本使用
LinkedHashSet linkedHashSet = new LinkedHashSet();
linkedHashSet.add(1);
linkedHashSet.add(2);
linkedHashSet.add(new Student(1));
linkedHashSet.add(new Student(1));//只显示一个Student(1)
（3）源码剖析
略
4 Map接口下集合源码分析
4.1 HashMap
（1）集合体系
（2）基本使用
//实例化
HashMap<String, Object> map = new HashMap<>();
//放入元素
map.put("1", "zs");
map.put("2", "ls");
map.put("3", "ww");
//获取元素
Object o = map.get("1");
//遍历
map.forEach((k, v) -> {
System.out.println(k+"-"+v);
});
（3）源码剖析
哈希表默认大小和加载因子：默认大小16，加载因子0.75，加载因子表示哈希表使用了75%则进行扩容static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0
Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}put方法过程：执行put 调用 hash方法，计算 key的 hash值 (h = key.hashCode()) ^ (h >>> 16)public V put(K key, V value) {
//调用putVal方法
return putVal(hash(key), key, value, false, true);
}
//真正的put方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果底层的table 数组为null, 或者 length =0 , 就扩容到16
if ((tab = table) == null
(n = tab.length) == 0)
n = (tab = resize()).length;
//取出hash值对应的table的索引位置的Node, 如果为null, 就直接把加入的k-v, 创建成一个 Node ,加入该位置即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果table的索引位置的key的hash相同和新的key的hash值相同，并满足(table现有的结点的key和准备添加的key是同一个对象
equals返回真)就认为不能加入新的k-v
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
//加入后，判断当前链表的个数，是否已经到8个，到8个，后就调用 treeifyBin 方法进行红黑树的转换
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;
//如size > 临界值，就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}树化过程：final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果table 为null ,或者大小还没有到 64，暂时不树化，而是进行扩容.
if (tab == null
(n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}扩容机制：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;
}
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);
}
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) {
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;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}4.2 HashTable
（1）集合体系
（2）基本使用
同HashMap
（3）源码剖析
是否线程安全：线程安全值是否可以为null：不可以为nullpublic synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}4.3 TreeMap
（1）集合体系
（2）基本使用
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
//按照Key的长度大小排序 相等时只插入一个
return ((String) o2).length() - ((String) o1).length();
}
});
treeMap.put("1", "zs");
treeMap.put("11", "ls");
treeMap.put("12", "ww");
（3）源码剖析
排序机制：构造方法中传入Comparator接口的匿名内部类public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}4.4 Properties
（1）集合体系
（2）基本使用
Properties properties = new Properties();
properties.put("1", "zs");
properties.put("2", "ls");
properties.put("3", "ww");
//通过key获取对应值
properties.get("1");
//删除
properties.remove("2");
（3）源码剖析
略
4.5 LinkedHashMap
（1）集合体系
（2）基本使用
LinkedHashMap<String, Object> map = new LinkedHashMap<>();
map.put("1","zs");
map.put("2","ls");
map.get("1");
（3）源码剖析
Entry结构：在HashMap的基础上将Entry像链表一样链接了起来private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
