续接上一话：
目录
一、ArrayList的使用（续）
1、ArrayList的扩容机制（续）
ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式：
Object[] elementData; // 存放元素的空间
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间
private static final int DEFAULT_CAPACITY = 10; // 默认容量大小
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private 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)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// 获取旧空间大小
int oldCapacity = elementData.length;
// 预计按照1.5倍方式扩容
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用copyOf扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
// 如果minCapacity小于0，抛出OutOfMemoryError异常
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}总结：
（1）检测是否真正需要扩容，如果是调用grow准备扩容
（2）预估需要库容的大小
初步预估按照1.5倍大小扩容
如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
（3）使用copyOf进行扩容
五、ArrayList的相关练习
1、杨辉三角
分析：
这里就是外侧全是1，其他的分别是上面紧挨着的两个的加和。但是，显然我们不能像左图一样创建顺序表，可以转换成如右图所示的样式！！！如右图，最外侧都为1，若位置为（i，j）,则[i][j] = [i-1][j] + [i-1][j-1]
因此，我们创建一个空列表ret，用来存储所有的行（每行是一个整数列表）。
先处理第一行，元素为1；再循环生成一共numRows行，将每行的第一个元素添加为1。
利用上一行计算中间元素，最后添加上尾巴（1）。
class Solution {
public static List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> list0 = new ArrayList<>();
list0.add(1);
ret.add(list0);
//从第2行开始 进行求每个元素
for (int i = 1; i < numRows; i++) {
//处理第一个元素
List<Integer> curRow = new ArrayList<>();
curRow.add(1);
//中间
List<Integer> preRow = ret.get(i-1);
for (int j = 1; j < i; j++) {
int val1 = preRow.get(j);
int val2 = preRow.get(j-1);
curRow.add(val1+val2);
}
//尾巴
curRow.add(1);
ret.add(curRow);
}
return ret;
}
}2、简单的洗牌算法
（一副新牌，四种花色（♥，♦，♠，♣），数值分别为1--13，经过一系列的洗牌之后，分别发给三个人每人5张（轮流抓牌），最后展示剩余牌和三人手里的牌）
public class Card {
private String suit;//花色
private int rank; //牌面值
public Card(String suit, int rank) {
this.suit = suit;
this.rank = rank;
}
@Override
public String toString() {
/*return "Card{" +
"suit='" + suit + '\'' +
", rank=" + rank +
'}';*/
return String.format("[%s %d]", suit, rank);
}
}import java.util.List;
import java.util.ArrayList;
import java.util.Random;
public class CardDemo {
public static final String[] suits = {"♥","♠","♣","♦"};
//买来一副新牌
public List<Card> buyCard() {
List<Card> cardList = new ArrayList<>(52);
for (int i = 1; i <= 13; i++) {
for (int j = 0; j < 4; j++) {
int rank = i;
String suit = suits[j];
Card card = new Card(suit,rank);
cardList.add(card);
}
}
return cardList;
}
//洗牌
public void shuffle(List<Card> cardList) {
Random random = new Random();
for (int i = cardList.size()-1; i > 0 ; i--) {
int index = random.nextInt(i);
swap(cardList,i,index);
}
}
private void swap(List<Card> cardList,int i,int j) {
/*
Card tmp = cardList[i];
cardList[i] = cardList[j];
cardList[j] = tmp;
*/
Card tmp = cardList.get(i);
cardList.set(i,cardList.get(j));
cardList.set(j,tmp);
}
//分别发牌
public List<List<Card>> play(List<Card> cardList) {
List<Card> hand0 = new ArrayList<>();
List<Card> hand1 = new ArrayList<>();
List<Card> hand2 = new ArrayList<>();
List<List<Card>> hand = new ArrayList<>();
hand.add(hand0);
hand.add(hand1);
hand.add(hand2);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
Card card = cardList.remove(0);
//怎么把对应的牌 放到对应的人的手里面
hand.get(j).add(card);
}
}
return hand;
}
}import java.util.*;
public class Test {
public static void main(String[] args) {
CardDemo cardDemo = new CardDemo();
//1. 买52张牌
List<Card> cardList = cardDemo.buyCard();
System.out.println("刚买回来的牌：");
System.out.println(cardList);
//2. 洗牌
cardDemo.shuffle(cardList);
System.out.println("洗过的牌:");
System.out.println(cardList);
//3. 3个人每个人轮流发牌5张
List<List<Card>> ret = cardDemo.play(cardList);
for (int i = 0; i < ret.size(); i++) {
System.out.println("第"+(i+1)+"个人的牌："+ret.get(i));
}
System.out.println("剩下的牌：");
System.out.println(cardList);
}运行程序可以得到类似的运行结果：
刚买回来的牌:
[[♠ 1], [♠ 2], [♠ 3], [♠ 4], [♠ 5], [♠ 6], [♠ 7], [♠ 8], [♠ 9], [♠ 10], [♠ 11], [♠ 12], [♠ 13], [♥ 1], [♥ 2], [♥ 3], [♥ 4], [♥ 5], [♥ 6], [♥ 7],
[♥ 8], [♥ 9], [♥ 10], [♥ 11], [♥ 12], [♥ 13], [♣ 1], [♣ 2], [♣ 3], [♣ 4], [♣ 5], [♣ 6], [♣ 7], [♣ 8], [♣ 9], [♣ 10], [♣ 11], [♣ 12], [♣
13], [♦ 1], [♦ 2], [♦ 3], [♦ 4], [♦ 5], [♦ 6], [♦ 7], [♦ 8], [♦ 9], [♦ 10], [♦ 11], [♦ 12], [♦ 13]]
洗过的牌:
[[♥ 11], [♥ 6], [♣ 13], [♣ 10], [♥ 13], [♠ 2], [♦ 1], [♥ 9], [♥ 12], [♦ 5], [♥ 8], [♠ 6], [♠ 3], [♥ 5], [♥ 1], [♦ 6], [♦ 13], [♣ 12], [♦ 12],
[♣ 5], [♠ 4], [♣ 3], [♥ 7], [♦ 3], [♣ 2], [♠ 1], [♦ 2], [♥ 4], [♦ 8], [♠ 10], [♦ 11], [♥ 10], [♦ 7], [♣ 9], [♦ 4], [♣ 8], [♣ 7], [♠ 8], [♦ 9], [♠
12], [♠ 11], [♣ 11], [♦ 10], [♠ 5], [♠ 13], [♠ 9], [♠ 7], [♣ 6], [♣ 4], [♥ 2], [♣ 1], [♥ 3]]
第1个人的牌:[[♥ 11], [♣ 10], [♦ 1], [♦ 5], [♠ 3]]
第2个人的牌:[[♥ 6], [♥ 13], [♥ 9], [♥ 8], [♥ 5]]
第3个人的牌:[[♣ 13], [♠ 2], [♥ 12], [♠ 6], [♥ 1]]
剩下的牌:
[[♦ 6], [♦ 13], [♣ 12], [♦ 12], [♣ 5], [♠ 4], [♣ 3], [♥ 7], [♦ 3], [♣ 2], [♠ 1], [♦ 2], [♥ 4], [♦ 8], [♠ 10], [♦ 11], [♥ 10], [♦ 7], [♣ 9], [♦
4], [♣ 8], [♣ 7], [♠ 8], [♦ 9], [♠ 12], [♠ 11], [♣ 11], [♦ 10], [♠ 5], [♠ 13], [♠ 9], [♠ 7], [♣ 6], [♣ 4], [♥ 2], [♣ 1], [♥ 3]]六、ArrayList的问题及思考
1. ArrayList底层使用连续的空间，任意位置插入或删除元素时，需要将该位置后序元素整体往前或者往后搬 移，故时间复杂度为O(N)
解决方案：
使用LinkedList：链表结构插入删除时间复杂度为O(1)
分段数组：将大数组分成多个小数组块
树状数组：使用树形结构维护数据
链表+数组组合（Unrolled Linked List）
class Chunk {
private static final int CHUNK_SIZE = 64;
private Object[] data;
private int size;
private Chunk next;
// 插入删除只在当前chunk内搬移数据
// 大大减少数据移动量
}2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
解决方案：
预分配策略：根据业务场景预估容量
增量式扩容：每次只扩容部分空间
内存池技术：预先申请大块内存
使用链表结构：完全避免扩容问题
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继 续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
解决方案：
更合理的扩容因子：1.5倍或其他经验值
缩容机制：当空间利用率低于阈值时自动缩容
弹性数组：动态调整容量
内存碎片整理：定期整理内存空间
弹性数组（弹性扩容因子）
class ElasticArrayList<T> {
private static final double GROW_FACTOR = 1.5;
private static final double SHRINK_THRESHOLD = 0.3;
private Object[] elementData;
private int size;
// 根据使用情况动态调整扩容因子
private int calculateNewCapacity(int minCapacity) {
if (size < 1000) return (int)(size * 1.8);
else if (size < 10000) return (int)(size * 1.5);
else return (int)(size * 1.2);
}
// 自动缩容机制
public void trimToUsage() {
if (size < elementData.length * SHRINK_THRESHOLD) {
elementData = Arrays.copyOf(elementData, size);
}
}
}