一. 集合分类
| 集合类型 | 简点描述 |
|---|---|
| Set | 无序、不可重复的集合 |
| List | 有序、重复的集合 |
| Queue | 队列集合 |
| Map | 具有映射关系的集合 |
Java集合.png
二. 常用的List
(A). ArrayList分析
面试的时候总被问，ArrayList底层是有什么实现的？它为什么查询，修改快。 插入，删除慢呢？
- ArrayList是以数组实现的
transient Object[] elementData; // 非私有以简化嵌套类访问
- ArrayList 默认第一次插入元素时创建大小为10的数组
private static final int DEFAULT_CAPACITY = 10;//默认初始容量。
3.ArrayList的插入 add(E e) / add(int index, E e)
public void add(int index, E element) {
//检查是否指针越界
rangeCheckForAdd(index);
//确保内部能力
ensureCapacityInternal(size + 1); // 增量modCount ! !
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
//确保明确的能力
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩展
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩展为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩为1.5倍还不满足需求，直接扩为需求值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//minCapacity通常接近于size，所以这是一个胜利
elementData = Arrays.copyOf(elementData, newCapacity);
}
- ArrayList的删除 remove(int index) / remove(Object o)
public E remove(int index) {
rangeCheck(index);//检查是否越界
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0){
// 把后面的往前移
System.arraycopy(elementData, index+1, elementData, index, numMoved);
}
// 把最后的置null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
5.ArrayList 查找,修改
public E set(int index, E element) {
rangeCheck(index);//检查是否越界
E oldValue = elementData(index);
elementData[index] = element; //新的值 替换 老的
return oldValue;
}
public E get(int index) {
rangeCheck(index);//检查是否越界
return elementData(index);
}
6.ArrayList总结
数组实现。节约空间，但数组有容量限制。超出限制时会增加50%容量，用System.arraycopy()复制到新的数组，因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。
按数组下标访问元素—get(i)/set(i,e) 的性能很高，这是数组的基本优势。
直接在数组末尾加入元素—add(e)的性能也高，但如果按下标插入、删除元素—add(i,e), remove(i), remove(e)，则要用System.arraycopy()来移动部分受影响的元素，性能就变差了，这是基本劣势。
(B). LinkedList分析
- LinkedList使用双向链表实现，内部提供了一个内部类 “Node<E>”。
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; 当前Item
this.next = next; 上一个
this.prev = prev; 下一个
}
}
LinkedList.jpg
(C). 一些学习链接
源码分析网上有很多，也各有千秋。我把自己看的文章比较好的贴出来，感谢这些作者的总结，更深层次的了解java集合。
-
HashMap分析总结：
https://www.jianshu.com/p/e5c8a814c0ca
https://www.jianshu.com/p/8324a34577a0 -
Java集合这些类大体应用场景：https://zhuanlan.zhihu.com/p/118656578
网友评论