一、JAVA集合的框架图
常见集合的架构图:

二、Set的底层实现
HashSet
它的构造函数
public HashSet() {
map = new HashMap<>();
}
从上面的构造函数,我们可以得知,它的底层是一个HashMap
Map是存储的键值对,但是Set只存储了值,那它的key-value是如何设计的呢?
我们跟踪一下HashSet的add方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
从上面的add方法我们可以看到,添加到HashSet的元素是作为HashMap的Key,它的Value是一个Object类型的常量对象PRESENT,并且HashSet中所有元素key对应的value都是同一个。
LinkedHashSet
它的构造函数
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
从上 面的构造函数,我们可以得知,它的底层实现是一个LinkedHashMap
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
从上面的add方法我们可以看到,添加到LinkedHashSet的元素是作为LinkedHashMap的Key,它的Value是一个Object类型的常量对象PRESENT,并且LinkedHashSet中所有元素key对应的value都是同一个(LinkedHashSet继承了父类HashSet的add方法没有重写)
TreeSet
它的构造函数
public TreeSet() {
this(new TreeMap<>());
}
从上 面的构造函数,我们可以得知,它的底层实现是一个TreeMap
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
从上面的add方法我们可以看到,添加到TreeSet的元素是作为TreeMap的Key,它的Value是一个Object类型的常量对象PRESENT,并且TreeSet中所有元素key对应的value都是同一个
二、Iterator接口迭代器
java.util.Iterator接口有三个方法
boolean hasNext()
E next()
void remove()
所有的Collection系列的集合都会包含一个方法来获取Iterator对象 Iterator iterator();
iterator() 这个方法返回的是哪个类的对象呢?
public Iterator<E> iterator() {
return new Itr();
}
如:ArrayList,在其内部有一个内部类,Itr,它实现了Iterator接口
Vector中,在其内部有一个内部类,Itr,它实现了Iterator接口
LinkedList中,内部有一个Itr 实现了Iterator,它还有一个ListItr实现了ListIterator
……
每一种Collection系列集合的实现类中都有一个内部类实现Iterator接口
Iterator接口对象的作用是用来做遍历,迭代集合的元素用,设计为内部类的好处,就是可以方便直接访问集合的内部元素
三、Iterator迭代器和foreach遍历,多线程并发问题
public class TestIterator {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("张三");
list.add("李四");
list.add("王五");
list.add("赵六");
Iterator iterator = list.iterator();
while(iterator.hasNext()){
Object next = iterator.next();
//这里使用集合的删除方法,会产生异常java.util.ConcurrentModificationException
list.remove(next);
}
}
}
在使用迭代器或者foreach遍历时,再用集合对象的remove方法时会报ConcurrentModificationException异常
原因:因为迭代器和集合两个同时在操作元素
关于迭代器中的next方法
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
在方法中它首先调用了checkForComodification()方法进行校验,方法的实现如下:
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
这里modCount表示修改的次数
观察一下add添加方法
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
观察一下remove方法
public E remove(int index) {
Objects.checkIndex(index, size);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
这样我们可以看到只要是我们修改了集合中的元素都会修改modcount
关于expectedModCount
在创建迭代器的时候就记录下来了集合的修改次数

当我们在遍历过程中 modCount变化了也就是集合中的元素变化了则会导致如下判断成立
modCount != expectedModCount
这个时候则会抛出异常
throw new ConcurrentModificationException();
去们用集合的remove方法会报错,但是在遍历时使用Iterator的remove方法则不会报错,可以看Iterator中的remove方法如下:
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
从上面可以看到在执行了集合的remove后进行了一个赋值操作 expectedModCount = modCount; 从而保证这两个值一致,所以在checkForComodification()校验时不会抛出异常
设计者为了避免将来其它的线程修改了集合的元素,导致当前这个操作的数据不正确风险,则快速抛出异常而失败掉。
Enumration就不是这样设计的,可能会存在数据的不一致性。
四、ArrayList
ArrayList:动态数组
它的内部实现是数组
内部初始化时数组的大小
在它的内部会创建一个数组
transient Object[] elementData;
它的构造函数如下:
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个是一个空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
在jdk1.8以上可以看到源码中如上代码所表述,它初始化时会置为一个长度为0的空数组:DEFAULTCAPACITY_EMPTY_ELEMENTDATA
在jdk1.6的时候在创建ArrayList对象时,它是直接创建一个长度为10的数组
如果在jdk1.7的时候在创建ArrayList时,它初始化时会创建一个长度为0的数组:EMPTY_ELEMENTDATA
数组扩容方式
当调用add方法时可以看到会调用ArrayList类中方法如下:
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //这里可以看到是扩容为1.5倍
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity); //这一行代码是关键DEFAULT_CAPACITY的常量值被定义为10
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0) //Integer.MAX_VALUE - 8
? newCapacity
: hugeCapacity(minCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}
由于jdk1.7后,ArrayList创建对象时它的数据初始化为一个空数组,所以第一次它会扩展长度为10
在后续如果又不够了这个时候会再扩展为1.5倍
如下测试可以看到确实当开始第二次扩容后,它扩容的长度是原来的1.5倍
public static void main(String[] args) {
ArrayList arrayList = new ArrayList();
System.out.println("在最开始创建ArrayList对象,它的底层数组容量是:" + getCapacity(arrayList));
arrayList.add("张三");
System.out.println("在添加了一个元素后ArrayList对象,它的底层数组容量是:" + getCapacity(arrayList));
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三"); //这是第11个添加的元素,已经超过10个元素了
System.out.println("当添加第11个元素后,ArrayList做底层数组的扩容,扩容后的容量是:" + getCapacity(arrayList));
}
/**
* 通过反射的方式把ArrayList对象中的elementData数组拿出来看看现这个数组的长度
* @param obj 一个ArrayList的对象
* @return length 返回的是当前ArrayList对象底层数组的容量
*/
public static int getCapacity(Object obj){
int length = -1;
Class c = obj.getClass();
Field[] declaredFields = c.getDeclaredFields();
for (Field declaredField : declaredFields) {
if("elementData".equals(declaredField.getName())){
//打开私有访问
declaredField.setAccessible(true);
try {
Object value = declaredField.get(obj);
Object o[] = (Object[]) value;
length = o.length;
} catch (IllegalAccessException e) {
e.printStackTrace();
}
}
}
return length;
}
通过运行上面的代码输出结果如下:

可以从上面返回的结果可以看到当最初new ArrayList对象的时候底层的那个数据容量默认是0,当添加第一个元素后,它的容量设置为了10,当继续添加元素以至于超过了10元素后则需要进行再次扩容,这个时候的扩容按旧的容量的1.5倍进行扩容。
当我们再次把元素删除后它的容量会不会缩小?ArrayList原码如下:
public E remove(int index) {
Objects.checkIndex(index, size);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
删除的时候会先对底层数组的元素进行整理(如果删除的不是最后一个则需要进行移动元素)
从上面的源码可以看到--size表示size是减少了,但是底层数组的容量并不会减少
同样使用自己测试类进行删除操作后测试
public static void main(String[] args) {
ArrayList arrayList = new ArrayList();
System.out.println("在最开始创建ArrayList对象,它的底层数组容量是:" + getCapacity(arrayList));
arrayList.add("张三");
System.out.println("在添加了一个元素后ArrayList对象,它的底层数组容量是:" + getCapacity(arrayList));
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三"); //这是第11个添加的元素,已经超过10个元素了
System.out.println("当添加第11个元素后,ArrayList做底层数组的扩容,扩容后的容量是:" + getCapacity(arrayList));
arrayList.remove(0);
System.out.println("删除一个元素,此时元素只有" + arrayList.size() +",ArrayList做底层数组当前容量是:" + getCapacity(arrayList));
arrayList.remove(0);
System.out.println("删除一个元素,此时元素只有" + arrayList.size() +",ArrayList做底层数组当前容量是:" + getCapacity(arrayList));
}
/**
* 通过反射的方式把ArrayList对象中的elementData数组拿出来看看现这个数组的长度
* @param obj 一个ArrayList的对象
* @return length 返回的是当前ArrayList对象底层数组的容量
*/
public static int getCapacity(Object obj){
int length = -1;
Class c = obj.getClass();
Field[] declaredFields = c.getDeclaredFields();
for (Field declaredField : declaredFields) {
if("elementData".equals(declaredField.getName())){
//打开私有访问
declaredField.setAccessible(true);
try {
Object value = declaredField.get(obj);
Object o[] = (Object[]) value;
length = o.length;
} catch (IllegalAccessException e) {
e.printStackTrace();
}
}
}
return length;
}
输出的结果如下:

ArrayList中预留了一个方法(trimToSize)可以把底层数组的容量为当前元素的大小 源码 如下
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
//再次调用自己的测试类进行验证
public static void main(String[] args) {
ArrayList arrayList = new ArrayList();
System.out.println("在最开始创建ArrayList对象,它的底层数组容量是:" + getCapacity(arrayList));
arrayList.add("张三");
System.out.println("在添加了一个元素后ArrayList对象,它的底层数组容量是:" + getCapacity(arrayList));
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三");
arrayList.add("张三"); //这是第11个添加的元素,已经超过10个元素了
System.out.println("当添加第11个元素后,ArrayList做底层数组的扩容,扩容后的容量是:" + getCapacity(arrayList));
arrayList.remove(0);
System.out.println("删除一个元素,此时元素只有" + arrayList.size() +",ArrayList做底层数组当前容量是:" + getCapacity(arrayList));
arrayList.remove(0);
System.out.println("删除一个元素,此时元素只有" + arrayList.size() +",ArrayList做底层数组当前容量是:" + getCapacity(arrayList));
arrayList.trimToSize();
System.out.println("调用trimToSize方法后,此时元素只有" + arrayList.size() +",ArrayList做底层数组当前容量是:" + getCapacity(arrayList));
}
/**
* 通过反射的方式把ArrayList对象中的elementData数组拿出来看看现这个数组的长度
* @param obj 一个ArrayList的对象
* @return length 返回的是当前ArrayList对象底层数组的容量
*/
public static int getCapacity(Object obj){
int length = -1;
Class c = obj.getClass();
Field[] declaredFields = c.getDeclaredFields();
for (Field declaredField : declaredFields) {
if("elementData".equals(declaredField.getName())){
//打开私有访问
declaredField.setAccessible(true);
try {
Object value = declaredField.get(obj);
Object o[] = (Object[]) value;
length = o.length;
} catch (IllegalAccessException e) {
e.printStackTrace();
}
}
}
return length;
}
运行后输出结果如下:

五、LinkedList
当我们去new一个LinkedList的时候它的无参构造函数如下:
public LinkedList() {
}
它的内部实现是链表,记录了Node有两个,一个头部的一个尾部的
transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;
//调用add方法,它默认添加的位置是在链表的最后
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++;
}
调用add的方法,此方法中我们指定添加元素的索引位置时
public void add(int index, E element) {
checkPositionIndex(index); //检查指定的索引位置是否合法
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
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;
}
}
remove方法,remove(int index)
public E remove(int index) {
checkElementIndex(index); //检查要删除元素位置
return unlink(node(index));
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
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;
}
remove方法,remove(Object obj)
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
这里要注意了,根据元素来进行删除的时候它是从前往后找的,如果LinkedList中存在多个相同的元素,则只会删除第一个匹配到的元素删除,后面相同的元素并不会做删除操作
六、HashMap
在JDK1.7及以前的版本
HashMap的底层实现是数组+链表,其结构类似如下:

数组的数据类型:Entry<k,v>,Entry实现了Map.Entry<k,v>,Entry<k,v>是HashMap的内部类类型
Entry<k,v>中不仅仅有key,value还有next,这里的next又是一个Entry<k,v>
数组和名称为table
链表的存在意义
计算出每一对映射关系的key的hash值,然后根据hash值决定存在table数组的哪一个位置(index)
两个key的hash值相同,但是equals不一样,这里算出来的index会一样
两个key的hash值不一样,equals出不一样,但是是在运算后index也一样
那么当index中的值一样的时候,但这时需要存储多个值,这时就使用链表的方式把它们串起来
数组的初始化长度:16,在源码中的写法如下(注意:长度可以在new时进行手动指定,当指定的长度不是2的n次方则会进行纠正)
static final int DEFAULT_INITIAL_CAPACITY = 1<<4;
这里也体现出长度必须是2的n次方(这里也是因为后面在计算存储数据计算数组index时的位运算有关)
数组的扩容方式
扩容的原因是,如果数组不进行扩容,会导致每一个index下的链表会很长,在进行查找、添加时效率都会很低
扩容是的时机点:有一个变量:threshold阈值来判断是否扩容
当变量的值达到临界值时,则会考虑进行扩容
DEFAULT_LOAD_FACTOR:默认加载因子,它的值是0.75
threshold = table.length * DEFAULT_LOAD_FACTOR
默认:16*0.75 = 12,当size达到12个,则会考虑扩容
还有一个需要判断当前添加(key,value)时:table[index] == null,是否成立,如果成立则本次暂时不做扩容否则会进行扩容
注意,当扩容后,后来数组中存放的链表的数据也会进行调整(会重新进行计算)
index值的计算方式
当key的值是null,则会直接把index置为0
如果key的值不是null,通过key拿到hash值(它确保可以相对均匀的分散数值),再通过hashCode与table.length-1进行按位与计算index。
key是不可以重复的
如果key相等时,则会使用新的 元素进行替换
key的判断:先判断hash是否相等,如果相等,再判断key的地址值 或 equals值是否相同,如果满足同表示key相等
在存入元素(key,value)时,添加到table[index]时,发现table[index]不为空,则会在链表上链接新的元素
链接的方式是新的元素会做为table[index]的头,而原来下面的元素会做为新元素的next
JDK1.8后版本
底层实现:数组+链表/红黑树
这里修改为链表/红黑树的原因:
当链表比较长的时候,我们查找的效率会比较慢,为了提高查询的效率,那么则把table[index]下的链表做调整
如果table[index]的链表的节点的个数少(8个以内),则保持链表结构;如果超过8个则考虑把链表转为红黑树
static final int TREEIFY_THRESHOLD = 8; //树化的阈值,从链表转为红黑树的长度
红黑树:它是一个自平衡的二叉树,它可以自动调整左右节点的个数,尽量保存节点在两个是均匀
树化的注意点:
当table[index]下的节点数达到8个不一定会做树化,还要判断是:table.length是否达到64,如果没有达到则先做扩容不做树化
static final int MIN_TREEIFY_CAPACITY = 64; //这是表示最小树化的容量
注意:与jdk1.7的版本不一样的是,它在新增元素时会做为table[index]原来元素中的next
树化是否会变化链表
当删除结节点,当树的节点个数少于6个,会把树变成链表(要做反树是因为树的结构复杂,当节点元数少时可以把复杂度降低)
static final int UNTREEIFY_THRESHOLD = 6;
使用put方法存储元素时
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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)
n = (tab = resize()).length;
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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
put的过程:
index的计算
-
使用key的hashCode值调用hash()函数,干扰hash值,使得(key,value)更加均匀分布table数组中(jdk1.8后的版本对hash()算法做了优化)
-
使用hash值与table.length-1进行按位与运算,保证index在[0,length-1]的范围
扩容
第一种:当某个table[index]的链表个数达到8个,并且table.length<64,那么会扩容为链表(table.length>=64时会转为树)
第二种:当size>=threshold,并且table[index] !=null
threshold = table.length*loadFator(这个的默认值是0.75)