一:Collection
二:List,有序, 可重复,有下标索引
1.ArrayList
底层动态数组,单线程,线程不安全,初始容量10,1.5倍扩容,查询效率高,增/删/改效率低
public class ArrayList<E>
{
transient Object[] elementData;
private int size;
}
-
扩容:
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//1.5倍扩容
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
2.LinkedList
双向链表实现,单线程,线程不安全,无限扩容,增删快,查询慢,
public class LinkedList<E>
{
transient int size = 0;
/**
* 头节点
*/
transient Node<E> first;
/**
* 尾节点
*/
transient Node<E> last;
private static class Node<E> {
//当前节点
E item;
//下一个节点
Node<E> next;
//前一个节点
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
3.Vector
底层动态数组,多线程(Synchronized同步方法),线程安全,初始容量10,2倍扩容,查询效率比LinkedList高,比ArrayList低(线程安全,消耗资源)
4.ArrayList比LinkedList查询效率高的原因:
ArrayList在内存中是连续、成块的,只需要根据首地址+偏移量即可快速计算出查找节点的内存地址,LinkedList在内存中是不连续的,每一个节点都需要2个指针分别指向上一个节点和下一个节点,只能通过遍历的方式获取元素(源码采用二分查找算法,以提高效率)
-
ArrayList查找源码:
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
-
LinkedList查找源码:
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
//二分查找,先定位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;
}
}
5.ArrayList比LinkedList修改效率低的原因:
ArrayList在插入/删除元素时,该元素插入位置后的数据的内存地址要依次向后移动,而LinkedList是双向链表最多只会影响到插入/删除元素前后2个位置节点的信息
-
LinkedList插入/删除源码:
/**
* 节点尾部插入元素
*/
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;
}
/**
* 删除元素
*/
E unlink(Node<E> x) {
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;
return element;
}
-
ArrayList插入/删除源码:
// ensureCapacityInternal() 方法内部会调用 System.arraycopy()
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public E remove(int index) {
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
return oldValue;
}
6.LinkedList比ArrayList占用更多的内存:
ArrayList每个节点存储的是实际数据内容,而LinkedList每个节点存储的是实际数据及前后节点的内存地址
7.扩容的目的:
减少链表的长度,元素分配更均匀
8.ArrayList是线程不安全的,请编写一个不安全的案例,并给出解决方案?
- 故障现象
- 导致原因
- 解决方案
- 优化建议
三:Set,无序, 不重复,无下标索引
1.HashSet
底层是HashMap,数组+链表结构,初始容量16,加载因子0.75,扩容1倍,存储元素时先计算该元素的HashCode值,根据HashCode值和集合的长度计算出该元素在集合中的下标,如果该下标处没有元素就直接存储,如果有通过equals方法比较是否是同一个对象,如果是不存储,如果不是通过链接的方式在该下标处存储元素
2.LinkedHashSet
HashSet的子类,比HashSet多了一个存储顺序的维护
3.TreeSet
- 底层是TreeMap,根据元素的compareTo()方法或者是根据指定的比较器对象的compare()来决定元素的存储的位置,数据结构使用树的结构,
- 存储到TreeSet的元素,要可比较的,要么元素本身是实现了Comparable接口的,要么为这个元素的类型单独指定一个比较器,这个比较器实现了Comparator接口
- 元素如果实现了Comparable接口,重写了compareTo()方法,那么按照逻辑角度,应该也重写equals方法,使得e1.compareTo(e2)==0,e1.equals(e2)==true保持一致,那么equals重写,往往hashcode方法也要重写
四:Map
1.HashMap
- 底层数组+链表结构,线程不安全,entry类型数组,初始容量16,加载因子0.75,扩容1倍,key、value允许为null值
- 存储过程:计算key的HashCode值,根据HashCode值计算出该元素在entry数组中对应的索引下标,如果该下标处没有元素就直接存储,如果有通过equal方法比较,如果相同就不存储,如果不相同就以链接的形式在该下标处存储元素
- 扩容:可能造成无效扩容,在插入元素后再判断是否需要扩容(有可能插入元素后扩容了,但不再有元素进来)
- index计算: hash & (tab.length – 1)
1.7和1.8区别
1.7的数据结构为:动态数组+单链表,1.8的数据结构为:动态数组+(链表+红黑树),链表长度>8转换为红黑树
2.LinkedHashMap
- HashMap的子类,用一个链表维护了元素的存储顺序,可以按照存储顺序遍历取出存储的元素
3.TreeMap
底层实现:红黑树
线程非安全,不允许null,key不可以重复,value允许重复
key类型必须是可排序的,
(1)key类型本身或它的父类实现了Comparable接口,自然排序,实现了int compareTo(T t);
(2)为key类型实现了一个Comparator比较器,定制排序,实现了int compare(T t1,T t2)
- key调用compare或compareTo方法比较,决定存储的位置
4.ConcurrentHashMap
- JDK1.7 实现
- 数据结构:分段数组+链表
- 底层实现:
分段锁机制
,Segment+ReentrantLock+HashEntyy
将Map分为N个Segment,线程安全,但效率提升N倍,默认16倍
核心静态内部类:Segment、HashEntry
1)Segment继承ReentrantLock充当锁的角色
2)HashEntry封装表的键值对
- JDK1.8 实现
- 数据结构:接近HashMap的结构,动态数组+链表
- 底层实现:synchronized+cas+HashEntry+红黑树
put 操作:
1)如果没有初始化,就调用initTable()进行初始化
2)如果没有Hash冲突,就直接cas插入
3)如果存在hash冲突,synchronized加锁保证线程安全(锁住链表或红黑树的头节点),有2种情况,一种是链表形式直接遍历尾端插入,一种是红黑树结构插入
4)如果链表的长度>8,就先转换为红黑树
5)添加成功,就调用addCount()方法,统计size(),并检查是否需要扩容
get 操作:
1)计算hash值,定位到在数组中的下标,如果是下标处链表的首节点就返回
2)如果遇到扩容,会调用标志正在扩容节点ForwardingNode的find方法,查找该节点,匹配就返回
3)以上都不符合,遍历链表,匹配就返回,不匹配返回null
- 区别:
锁的粒度
1.7锁的粒度是segment,包含多个Hashentry,1.8只锁一个HashEntry,首节点
链表遍历效率
1.8使用红黑树优化链表,当链表的长度>8,就转换为红黑树,链表的查询效率提高了
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode()); //两次hash,减少hash冲突,可以均匀分布
int binCount = 0;
for (Node<K,V>[] tab = table;;) { //对这个table进行迭代
Node<K,V> f; int n, i, fh;
//这里就是上面构造方法没有进行初始化,在这里进行判断,为null就调用initTable进行初始化,属于懒汉模式初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果i位置没有数据,就直接无锁插入
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)//如果在进行扩容,则先进行扩容操作
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//如果以上条件都不满足,那就要进行加锁操作,也就是存在hash冲突,锁住链表或者红黑树的头结点
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { //表示该节点是链表结构
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
//这里涉及到相同的key进行put就会覆盖原先的value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
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时就会进行红黑树的转换
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);//统计size,并且检查是否需要扩容
return null;
}
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode()); //计算两次hash
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {//读取首节点的Node元素
if ((eh = e.hash) == h) { //如果该节点就是首节点就返回
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//hash值为负值表示正在扩容,这个时候查的是ForwardingNode的find方法来定位到nextTable来
//查找,查找到就返回
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode,那就往下遍历
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
5.HashTable
- 底层实现:数组+链表,线程安全(相比ConcurrentHashMap效率低,锁住整张表),key和value不能为null,
- 扩容:初始容量11,2倍+1扩容
- index计算:(hash & 0x7FFFFFFF) % tab.length
6.HashTable与HashMap的区别
线程安全性
HashTable线程安全(synchronized,1.5之后提供了ConcurrentHashMap,它是HashTable的替代,比HashTable扩展性更好),HashMap线程不安全
null值
HashTable中key和value都不允许出现null值,HashMap中null可以作为主键(只有一个),当使用get()方法返回null值,不一定表示该HashMap没有该值,需要用containsKey()方法来判断
性能
当线程场景下,HashMap性能好于HashTable
哈希值的使用
HashTable直接使用对象的HashCode值,HashMap重新计算
初始化大小和扩容方式不同,
HashTable数组默认为11,old*2+1扩容,加载因子0.75,HashMap默认数组大小为16,2倍扩容,加载因子0.75