ArrayList
1.动态数组
2.线程不安全
3.存储空间连续
4.查询快，添加删除慢
构造方法
/**
+ Shared empty array instance used for default sized empty instances. We
+ distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
+ first element is added.
*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/**
+ Constructs an empty list with an initial capacity of ten.
*/public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}这个构造方法很简单，初始化了一个空的elementData,并没有赋予数组长度
元素添加
/**
+ Default initial capacity.
*/private static final int DEFAULT_CAPACITY = 10;/**
+ The array buffer into which the elements of the ArrayList are stored.
+ The capacity of the ArrayList is the length of this array buffer. Any
+ empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
+ will be expanded to DEFAULT_CAPACITY when the first element is added.
*/transient Object[] elementData; // non-private to simplify nested class access/**
+ The size of the ArrayList (the number of elements it contains).
*
+ @serial
*/private int size;/**
+ Appends the specified element to the end of this list.
*
+ @param e element to be appended to this list
+ @return <tt>true</tt> (as specified by {@link Collection#add})
*/public boolean add(E e) { // 首先进行扩充
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将元素追加到最后
elementData[size++] = e;
return true;
}// 扩充private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}// 计算数组大小 第一次调用此处的elementData={}，所以返回值为DEFAULT_CAPACITY=10，也就是默认的数组长度是10private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity);
} return minCapacity;
}private void ensureExplicitCapacity(int minCapacity) {
modCount++; // overflow-conscious code
if (minCapacity - elementData.length > 0) // 当加上当前元素后的集合长度（size）大于现在数组长度（elementData.length）在进行扩充
grow(minCapacity);
}// 真正的扩充操作private void grow(int minCapacity) { // overflow-conscious code
int oldCapacity = elementData.length; // 此处oldCapacity=0
int newCapacity = oldCapacity + (oldCapacity >> 1); // 此处newCapacity=0
if (newCapacity - minCapacity < 0) // 此处minCapacity=10
newCapacity = minCapacity; // 此处newCapacity=10
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); //数组拷贝}真正的数组长度是在第一次添加的时候进行初始化的,默认为10
最主要的消耗是在扩容(数组拷贝)
当集合长度大于数组长度的时候进行扩充，扩充的标准是1.5倍[oldCapacity + (oldCapacity >> 1)]
查询
public E get(int index) {
rangeCheck(index);// 校验
return elementData(index);
}E elementData(int index) { return (E) elementData[index];
}Vector
1.动态数组，类似于ArrayList
2.线程安全
3.消耗大
构造方法
public Vector() { this(10); // initialCapacity初始容量}元素添加
/**
* Appends the specified element to the end of this Vector.
*
* @param e element to be appended to this Vector
* @return {@code true} (as specified by {@link Collection#add})
* @since 1.2
*/public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e; return true;
}被synchronized修饰，线程安全，但是效率较低
在指定位置添加元素
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++;
}LinkedList
1.双向链表:jdk1.7/8以后
2.插入快,查询慢
构造函数
/**
* Constructs an empty list.
*/public LinkedList() {
}空的构造方法
元素添加
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++;
}默认添加到链表结尾，prev指向原结尾元素，原结尾元素next指针指向新添加元素，并记录结尾元素为新添加元素。只有指针移动，并没有数组拷贝，所以插入效率较快
查询
public E get(int index) {
checkElementIndex(index); return node(index).item;
}Node<E> node(int index) { // assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first; for (int i = 0; i < index; i++)
x = x.next; return x;
} else {
Node<E> x = last; for (int i = size - 1; i > index; i--)
x = x.prev; return x;
}
}查询采用二分法查找，先将数组拆分成一半，然后进行遍历。所以查询较慢。当index值接近二分之一size时，更慢。
HashMap
1.存储结构：数组+链表/数组+红黑树
2.线程不安全
构造方法
static final float DEFAULT_LOAD_FACTOR = 0.75f;public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}没有初始化数组，负载因子为0.75
添加元素
public V put(K key, V value) { 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; if ((tab = table) == null || (n = tab.length) == 0) //[1]
n = (tab = resize()).length; // [2]
if ((p = tab[i = (n - 1) & hash]) == null) [// [3]
tab[i] = newNode(hash, key, value, null); // [4]
else {
Node<K,V> e; K k; if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))// [5]
e = p; // [6]
else if (p instanceof TreeNode) // [7]
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //[8]
else { //[9]
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { // [10]
p.next = newNode(hash, key, value, null); // [11]
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st [12]
treeifyBin(tab, hash); // [13]
break;
} if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) // [14]
break;
p = e;
}
} if (e != null) { // existing mapping for key [15]
V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) // [16]
e.value = value;
afterNodeAccess(e); return oldValue;
}
}
++modCount; if (++size > threshold) // [17]
resize();
afterNodeInsertion(evict); return null;
}[1]判断table是否为null,长度是否为0，table用于扩充时记录扩充后的新数组
[2]进行数组扩充，将新数组赋值给tab,n为新数组的长度
[3]判断新key需要存储的数组节点是否有值
[4]如果没有值，直接存储于该节点，如果当前数组节点有值
[5]判断新key与当前存储的key是否相同
[6]记录当前存储元素到e
[7]判断当前节点是否为数节点
[8]进行树节点操作
[9]当前节点存储的key与新key不同，并且不是树形结构（链表结构）
[10]循环遍历，找到链表的尾节点
[11]将新元素追加到链表的末尾，即原尾节点的next指针指向新元素
[12]当链表的长度达到8时，转为树形结构[13]
[14]循环过程中如果发现存储的key与新key相同，则中断循环
[15]如果存在匹配的key，则替换value
[16]返回旧值
[17]能走到这里说明是新增元素，并不是更新元素，判断当前集合长度是否大于threshold（threshold=当前集合长度*0.75）,如果大于需要进行扩充
// 扩容final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // [1]
int oldCap = (oldTab == null) ? 0 : oldTab.length; //[2]
int oldThr = threshold; // [3]
int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { // [4]
threshold = Integer.MAX_VALUE; return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) // [5]
newThr = oldThr << 1;
} else if (oldThr > 0) // [6]
newCap = oldThr; else { // [7]
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
} if (newThr == 0) { // [8]
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // [9]
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // [10]
if (oldTab != null) { for (int j = 0; j < oldCap; ++j) {// [11]
Node<K,V> e; if ((e = oldTab[j]) != null) {// [12]
oldTab[j] = null; if (e.next == null)
newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // [13]
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order [14]
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;
}[1]oldTab用来记录上次扩充的table
[2]oldCap用来记录上次扩充table的长度
[3]oldThr用来记录上次扩充的阈值
[4]如果oldCap大于等于最大值（2^30）,threshold等于2^30-1,直接返回，不在进行扩充
[5]newCap等于（oldCap*2），如果newCap小于最大值（2^30）并且oldCap大于初始值（2^4）,则newThr=oldThr*2
[6]如果oldThr大于0，则newCap等于oldThr,上次扩充的阈值
[7]如果oldCap和oldThr都不大于0，则newCap等于2^4,newThr等于2^4*0.75(首次扩充)
[8]当oldCap小于2^4的时，newThr等于0，newThr=2*oldCap*0.75
[9]threshold等于newThr，记录下次需要扩充的阈值
[10]创建新的Node数字，长度为newCap
[11]如果oldTab不为空，则遍历这个数组
[12]将原数组的元素散列到新数组中
[13]以红黑树的结构重新散列元素
[14]以链表的结构重新散列元素
get方法，先根据key计算出对应的数组指针位置，然后遍历链表或者红黑树获取相同key的元素
Iterator<Map.Entry<String, Integer>> entryIterator = map.entrySet().iterator(); while (entryIterator.hasNext()) {
Map.Entry<String, Integer> next = entryIterator.next();
System.out.println("key=" + next.getKey() + " value=" + next.getValue());
}Iterator<String> iterator = map.keySet().iterator(); while (iterator.hasNext()){
String key = iterator.next();
System.out.println("key=" + key + " value=" + map.get(key));
}map.forEach((key,value)->{
System.out.println("key=" + key + " value=" + value);
});hashmap只能在单线程中使用，并尽量减少扩容，循环链表的时间复杂度是O(n),O(logn)
多线程场景下推荐使用ConcurrentHashMap
ConcurrentHashMap
Object put(Object key, int hash, Object value, boolean onlyIfAbsent) {
lock(); try { int c = count; if (c++ > threshold) // ensure capacity
rehash();
HashEntry[] tab = table; int index = hash & (tab.length - 1);
HashEntry first = tab[index];
HashEntry e = first; while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
Object oldValue; if (e != null) {
oldValue = e.value; if (!onlyIfAbsent)
e.value = value;
} else {
oldValue = null;
++modCount;
tab[index] = new HashEntry(key, hash, first, value);
count = c; // write-volatile
} return oldValue;
} finally {
unlock();
}
}ConcurrentHashMap之所以是线程安全的是因为在添加元素的时候先上了一个锁，操作完成在解锁。
HashSet
1.hashmap存储数据
2.不允许存储重复元素的集合
构造方法
public HashSet() {
map = new HashMap<>();
}添加元素
private static final Object PRESENT = new Object();public boolean add(E e) { return map.put(e, PRESENT)==null;
}此方法将添加的元素e作为hashmap的key,value都是相同的PRESENT,因为hashmap的key是不允许重复的，所以相同的元素添加进来，后添加的会覆盖先添加的，这就是不允许重复的原因
原文出处：https://www.cnblogs.com/Smilence1024/p/9605846.html