集合源码
工欲善其事必先利其器
CodeSheep——Java源码盘起来！演示搭建JDK源码阅读环境，利用IDEA搭建Java源码阅读环境视频教程
ArrayList
一、ArrayList底层数据结构
1、ArrayList集合介绍
ArrayList是List集合可变大小的数组的实现
2、数组
数组大小一旦确定，就无法改变
增删慢：每次添加或删除元素，都需要更改数组长度、拷贝以及移动元素位置
查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素
二、ArrayList继承关系
1、Serializable标记性接口
此处可以查看CodeSheep——《序列化/反序列化，我忍你很久了！》
介绍
- 类的序列化由实现java.io.Serializable接口的类启用
- 不实现此接口的类将不会使任何状态序列化或反序列化
- 可序列化类的所有子类型都是可序列化的
- 序列化接口没有方法或字段，仅用于标识可串行化的语义
序列化：将对象的数据写入到文件(写对象)
反序列化：将文件中对象的数据读取出来(读对象)
如果不想对某些变量进行序列化（如密码等），可以在前面加上 transient 关键字，表示该字段不想被序列化
public interface Serializable {
}案例
Student类
public class Student implements Serializable {
private static final long serialVersionUID = 7515669154157983943L;
String name;
int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}测试类
//不使用集合
public class Demo1 {
public static void main(String[] args) throws IOException, ClassNotFoundException {
write();
read();
}
public static void write() throws IOException {
//创建对象操作流，进行序列化操作
ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream("student.txt"));
//创建Student类的对象
Student student = new Student("Nyima", 12);
//调用操作流写对象的方法，将对象的数据写入文件中
objectOutputStream.writeObject(student);
//关闭输出流
objectOutputStream.close();
}
public static void read() throws IOException, ClassNotFoundException {
ObjectInputStream objectInputStream = new ObjectInputStream(new FileInputStream("student.txt"));
Student student = (Student) objectInputStream.readObject();
System.out.println(student);
objectInputStream.close();
}
}
//使用集合
public class Demo2 {
public static void main(String[] args) throws Exception{
Student student1 = new Student("Chen", 1);
Student student2 = new Student("Pan", 1);
Student student3 = new Student("Wen", 1);
ArrayList<Student> lists = new ArrayList<>();
lists.add(student1);
lists.add(student2);
lists.add(student3);
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("stu.txt"));
//通过集合进行序列化
oos.writeObject(lists);
oos.close();
ObjectInputStream ois = new ObjectInputStream(new FileInputStream("stu.txt"));
lists = (ArrayList<Student>) ois.readObject();
for(Student student : lists) {
System.out.println(student);
}
ois.close();
}
}2、Cloneable标记性接口
此处可以查看CodeSheep——《一个工作三年的同事，居然还搞不清深拷贝/浅拷贝，被老大批了》
介绍
一个类实现 Cloneable 接口来指示 Object.clone() 方法，该方法对于该类的实例进行字段的复制是合法的。在不实现 Cloneable 接口的实例上调用对象的克隆方法会导致异常 CloneNotSupportedException 被抛出。
简言之：克隆就是依据已经有的数据，创造一份新的完全一样的数据拷贝
public interface Cloneable {
}条件
被克隆对象所在的类必须实现Cloneable接口
重写clone()方法
使用
基本使用
public class Demo3 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("Hello");
list.add("World");
Object o = list.clone();
System.out.println(o == list);
System.out.println(list.toString());
System.out.println(o.toString());
}
}运行结果
复制过程
在调用clone方法的地方打上断点
ArrayList实现clone()方法源码解析
public Object clone() {
try {
//此处调用了Object的clone()方法
//Object的clone()方法，此处调用了本地方法(native)
//protected native Object clone() throws CloneNotSupportedException;
ArrayList<?> v = (ArrayList<?>) super.clone();
//elementData先保存了我们被复制的集合的数据，其中elementData对象为无法被序列化的Object类型的数组
//size为被复制数组的大小
//transient Object[] elementData;
//然后调用Arrays类的copyOf方法给elementData对象赋值
//copyOf()方法的调用见下面
v.elementData = Arrays.copyOf(elementData, size);
//用于记录此列表被记录修改的次数
v.modCount = 0;
//返回拷贝对象
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
//copyOf()方法
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
//创建一个和原集合相同大小的集合copy
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//调用System的arraycopy方法进行复制
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
//返回copy集合
return copy;
}图解
浅拷贝
public class Demo4 {
public static void main(String[] args) throws CloneNotSupportedException {
Skill skill = new Skill("Foot Attack");
Hero hero1 = new Hero("LiQing", 25, skill);
//调用hero1对象的克隆方法
Hero hero2 = hero1.clone();
//打印结果
System.out.println(hero1 == hero2);
System.out.println(hero1);
System.out.println(hero2);
//更改hero2的年龄和技能
hero2.setName("Kasa");
skill.setSkillName("Fly in the Sky");
hero2.setSkill(skill);
//打印结果
System.out.println(hero1 == hero2);
System.out.println(hero1);
System.out.println(hero2);
}
}
class Hero implements Cloneable {
String name;
int age;
//技能类
Skill skill;
/**
*
* @return 克隆后的对象
* @throws CloneNotSupportedException
*/
@Override
protected Hero clone() throws CloneNotSupportedException {
return (Hero) super.clone();
}
public Hero(String name, int age, Skill skill) {
this.name = name;
this.age = age;
this.skill = skill;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public Skill getSkill() {
return skill;
}
public void setSkill(Skill skill) {
this.skill = skill;
}
@Override
public String toString() {
return "Hero{" +
"name='" + name + '\'' +
", age='" + age + '\'' +
", skill=" + skill +
'}';
}
}
class Skill {
String skillName;
public Skill(String skillName) {
this.skillName = skillName;
}
public String getSkillName() {
return skillName;
}
public void setSkillName(String skillName) {
this.skillName = skillName;
}
@Override
public String toString() {
return "Skill{" +
"skillName='" + skillName + '\'' +
'}';
}
}运行结果
说明：
创建了一个Hero对象hero1，然后通过其clone()方法克隆了一个hero2对象。然后我们修改hero2对象的姓名和技能，其中技能是Skill类构成的。修改后发现。hero1的name没有收到波及，但是hero1的Skill被改变了
这就是浅拷贝存在的问题：基本数据类型可以达到完全复制，引用数据类型则不可以。这是因为在hero1被克隆的时候，其属性skill(引用数据类型)仅仅是拷贝了一份引用，因此当skill的值发生改 变时，被克隆对象hero1的属性skill也将跟随改变
深拷贝
public class Demo4 {
public static void main(String[] args) throws CloneNotSupportedException {
Skill skill = new Skill("Foot Attack");
Hero hero1 = new Hero("LiQing", 25, skill);
//调用hero1对象的克隆方法
Hero hero2 = hero1.clone();
//打印结果
System.out.println(hero1 == hero2);
System.out.println(hero1);
System.out.println(hero2);
//更改hero2的年龄和技能
hero2.setName("Kasa");
skill.setSkillName("Fly in the Sky");
hero2.setSkill(skill);
//打印结果
System.out.println(hero1 == hero2);
System.out.println(hero1);
System.out.println(hero2);
}
}
class Hero implements Cloneable {
String name;
int age;
Skill skill;
/**
*
* @return 克隆后的对象
* @throws CloneNotSupportedException
*/
@Override
protected Hero clone() throws CloneNotSupportedException {
//克隆个英雄对象
Hero hero = (Hero) super.clone();
//调用Skill的clone()方法，克隆出一个skill对象，并赋值给Hero对象
this.skill = this.skill.clone();
return hero;
}
public Hero(String name, int age, Skill skill) {
this.name = name;
this.age = age;
this.skill = skill;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public Skill getSkill() {
return skill;
}
public void setSkill(Skill skill) {
this.skill = skill;
}
@Override
public String toString() {
return "Hero{" +
"name='" + name + '\'' +
", age='" + age + '\'' +
", skill=" + skill +
'}';
}
}
class Skill implements Cloneable{
String skillName;
//重写克隆方法
@Override
protected Skill clone() throws CloneNotSupportedException {
return (Skill)super.clone();
}
public Skill(String skillName) {
this.skillName = skillName;
}
public String getSkillName() {
return skillName;
}
public void setSkillName(String skillName) {
this.skillName = skillName;
}
@Override
public String toString() {
return "Skill{" +
"skillName='" + skillName + '\'' +
'}';
}
}运行结果
深拷贝与浅拷贝的不同是：若被拷贝对象中引用了其他类，被引用类也需要实现Cloneable接口，并重写clone()方法
同时被拷贝对象的clone()方法不能只是调用父类的clone()方法，需要重写，规则如下
先调用父类的clone()方法，克隆出一个被拷贝对象
Hreo hero = (Hero)super.clone();调用被引用类的clone()方法，克隆出一个被引用对象
Skill skill = (Skill) this.skill.clone()将克隆的被引用对象赋值给被拷贝对象
this.skill = skill;
3、 RandomAccess标记性接口
介绍
标记接口由 List 实现使用，以表明它们支持快速（通常为恒定时间）随机访问
此接口的主要目的是允许通用算法更改其行为，以便在应用于随机访问列表或顺序访问列表时提供良好的性能
ArrayList
实现了RandomAccess接口，随机访问速度比顺序访问更快
注意ArrayList底层为数组，所以随机访问的效率高。RandomAccess接口只是用来标识其是否支持随机访问，而不是实现了该接口就能使随机访问效率更高
public class Demo1 {
public static void main(String[] args) {
//使用ArrayList
ArrayList<String> list = new ArrayList<>();
//向list中添加十万条数据
for (int i = 0; i < 100000; i++) {
list.add("a");
}
//随机访问，并计算访问用时
long startTime = System.currentTimeMillis();
for(int i = 0; i < 100000; i++) {
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("随机访问时间：" + (endTime - startTime));
//顺序访问
startTime = System.currentTimeMillis();
for(Iterator iterator = list.iterator(); iterator.hasNext();) {
iterator.next();
}
endTime = System.currentTimeMillis();
System.out.println("顺序访问时间：" + (endTime - startTime));
}
}运行结果
LinkedList
LinkedLis随机访问比顺序访问更慢。因为LinkedList底层为链表，随机访问效率低，所以没有实现RandomAccess接口。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable代码
public class Demo2 {
public static void main(String[] args) {
//使用LinkedList
LinkedList<String> list = new LinkedList<>();
//向list中添加十万条数据
for (int i = 0; i < 100000; i++) {
list.add("a");
}
//随机访问，并计算访问用时
long startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
list.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("随机访问时间：" + (endTime - startTime));
//顺序访问
startTime = System.currentTimeMillis();
for (Iterator iterator = list.iterator(); iterator.hasNext(); ) {
iterator.next();
}
endTime = System.currentTimeMillis();
System.out.println("顺序访问时间：" + (endTime - startTime));
}
}运行结果
为什么LinkedList随机访问的效率这么低呢
随机访问的时候源码底层每次都需要进行折半的动作，再经过判断是从头还是从尾部一个个寻找
顺序访问只会在获取迭代器的时候进行一次折半的动作，以后每次都是在上一次的基础上获取下一个元素
因此顺序访问要比随机访问快得多
应用
遍历集合前使用 instanceof 关键字来判断集合是否实现了 RandomAccess 接口
- 如果实现了，就使用随机访问
- 如果没实现，就使用顺序访问
代码
public class Demo3 {
public static void main(String[] args) {
//链表
LinkedList<String> linkedList = new LinkedList<>();
//数组
ArrayList<String> arrayList = new ArrayList<>();
//向集合中添加十万条数据
for (int i = 0; i < 100000; i++) {
arrayList.add("a");
linkedList.add("b");
}
//通过判断集合是否实现了RandomAccess接口，来选择适当的遍历方法
if (arrayList instanceof RandomAccess) {
System.out.println("随机访问");
for (int i = 0; i < arrayList.size(); i++) {
arrayList.get(i);
}
} else {
System.out.println("顺序访问");
//实现了迭代器的集合，foreach会使用迭代器
for (String s : arrayList) {
//取出元素，不做任何操作
}
}
if (linkedList instanceof RandomAccess) {
System.out.println("随机访问");
for (int i = 0; i < linkedList.size(); i++) {
linkedList.get(i);
}
} else {
System.out.println("顺序访问");
//实现了迭代器的集合，foreach会使用迭代器
for (String s : linkedList) {
//取出元素，不做任何操作
}
}
}
}4、AbstractList抽象类
该抽象类含有一个空构造方法，以及一些需要子类去实现的抽象方法
三、ArrayList源码分析
1、构造方法
无参构造器
public class ArrayList {
//默认的初始化容量
private static final int DEFAULT_CAPACITY = 10;
//默认的Object类型的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//不可序列化的Object类型数组，用于存储ArrayList元素的数组
transient Object[] elementData;
public ArrayList() {
//如果没有指定集合的大小，当第一次向集合中添加元素时，集合容量会扩充为10
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
}无参构造方法没有指定集合的大小，所以当第一次向集合中添加元素的时候，集合的容量会扩充为10
initialCapacity构造方法
//空的Objcet类型数组，区别于DEFAULTCAPACITY_EMPTY_ELEMENTDATA
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
//如果容量大于0
if (initialCapacity > 0) {
//根据传入的容量大小创建Objcet类型的数组，赋值给elementData
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果容量等于0，就将elementData赋值为一个Object类型的空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
//如果容量小于0，就抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}initialCapacity构造函数会根据传入的容量大小来创建满足要求的集合
Collection构造方法
public ArrayList(Collection<? extends E> c) {
// 将传入的集合转成数组
elementData = c.toArray();
//判断传入集合的大小是否为0
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// 存在一个bug，c.toArray方法的返回值可能不是一个Object类型的数组
// 如果elementData的类型不是一个Object类型的数组
if (elementData.getClass() != Object[].class)
// 就再次进行拷贝操作
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
// 如果传入集合的大小为0，就赋值为一个空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
// toArray方法
public Object[] toArray() {
// 调用了copyOf方法
return Arrays.copyOf(elementData, size);
}
// copyOf方法
public static <T> T[] copyOf(T[] original, int newLength) {
调用了重载后的copyOf方法，对集合进行拷贝操作
return (T[]) copyOf(original, newLength, original.getClass());
}Collection构造方法主要是将传入的集合转变为数组类型。在转换后根据elementData的大小再次对elementData进行了赋值操作
- 当size != 0时，要判断 c.toArray() 所返回的结果是不是Objcet类型的数组，如果不是，则还需要elementData该为Object数组
- 当size == 0时，将其赋值为一个空数组
2、添加方法
add(E e)方法
public class Demo1 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
// 向集合中添加一个元素时，会调用add(E e)方法
list.add("Nyima");
}
}
public boolean add(E e) {
// 传入需要扩容的最小容量，值为元素个数+1
ensureCapacityInternal(size + 1); // Increments modCount!!
// 扩容后，放入要添加的元素
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 调用calculateCapacity方法，计算最小容量
//然后再调用ensureExplicitCapacity方法，来增加数组被修改次数modCount，以及查看是否真正需要扩容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static final int DEFAULT_CAPACITY = 10;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果集合是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，也就是创建集合时没有传入容量大小，并且是第一次进行添加操作
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 返回默认容量10，和最小容量的较大者
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 返回最小容量
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// 增加modCount++
// modCount用于保存集合被修改的次数
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倍数
// 右移 >> : 右移多少位就是除以2的多少次幂，这里是除以2
// 左移 << : 左移多少位就是乘以2的多少次幂
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容1.5倍后的容量小于最小容量
if (newCapacity - minCapacity < 0)
// 就按照最小容量进行扩容（选取较大的扩容方式）
newCapacity = minCapacity;
// 如果新容量大于数组的最大容量
// private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//就将其令为最大容量
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 将数组根据newCapacity扩容，并将其原来的元素放入到elementData中
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;
}总结
- 向集合中添加元素时，先进行容量检测，在进行添加操作
- 容量检测操作如下
- 最小扩容容量为当前数组元素个数+1
- 判断当前数组是否为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，也就是调用了无参构造函数来创建集合
- 如果是，最小容量就变为DEFAULT_CAPACITY(10)和最小容量的较大者
- 如果不是，就返回较小容量
- 返回得到的最小扩容容量
- 然后调用方法，增加集合被修改的次数（modCount++），然后再次确定最小扩容容量是否大于数组当前的大小（也就是放入元素后会不会大于数组的当前长度，容量不足），如果满足，则调用最重要的grow方法进行数组的扩容，方法执行的操作如下
- 用变量oldCapacity保存扩容前数组的大小（数组中元素的个数）
- 进行扩容，扩容大小为原容量的1.5倍（右移一位，表示除以2）
- 查看扩容后的容量是否小于最小扩容容量（如果原容量为0，如初始化了集合大小，newCapaticy就还是0，所以需要比较）
- 如果是，就以最小扩容容量来进行扩容
- 如果不是，就扩大为原容量的1.5倍
补充：集合在被操作的时候，都会增加modCount的值，那么这个值到底有什么用呢？
在使用迭代器进行迭代时会用到这个变量。这个变量是用来保证线程的安全性的。如果在进行迭代的时候，发现modCount的值被修改了，那么就会抛出ConcurrentModificationException
后面分析迭代器时，还会具体分析modCount
add(int index, E element)方法
public class Demo1 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>(1);
list.add("Nyima1");
list.add("Nyima2");
list.add("Nyima3");
//向指定位置插入元素
list.add(1, "Nyima4");
}
}
public void add(int index, E element) {
// 判断插入的位置是否合法
rangeCheckForAdd(index);
// 对数组容量进行检查，查看是否需要进行扩容，并增加数组被修改的次数modCount
ensureCapacityInternal(size + 1); // Increments modCount!!
/**
* 进行拷贝操作，将插入位置及其后面的所有元素后移一位
* @param src the source array.
* @param srcPos starting position in the source array.
* @param dest the destination array.
* @param destPos starting position in the destination data.
* @param length the number of array elements to be copied.
*/
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 在目标位置插入该元素
elementData[index] = element;
// 集合容量加1
size++;
}
private void rangeCheckForAdd(int index) {
// 如果插入位置超出了数组的范围，就抛出异常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}addAll(Collection<? extends E> c)方法
public class Demo1 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>(1);
ArrayList<String> list2 = new ArrayList<>();
list.add("Nyima1");
list.add("Nyima2");
list.add("Nyima3");
// 此处调用了addAll方法，将list集合中的所有元素插入到list2集合的末尾
list2.addAll(list);
}
}
public boolean addAll(Collection<? extends E> c) {
// 将要插入的集合转为Object类型的数组
Object[] a = c.toArray();
// 得到插入数组的长度
int numNew = a.length;
// 增加modCount并根据需求进行扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 调用数组拷贝的方法，将数组a中的所有元素添加到elementData数组的末尾
System.arraycopy(a, 0, elementData, size, numNew);
// 数组的大小增加，增加大小为被拷贝集合的大小
size += numNew;
// 返回是否添加成功。如果被添加集合是一个空数组，则添加失败
return numNew != 0;
}addAll(int index, Collection<? extends E> c)方法
public class Demo1 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>(1);
ArrayList<String> list2 = new ArrayList<>();
ArrayList<String> list3 = new ArrayList<>();
list.add("Nyima1");
list.add("Nyima2");
list.add("Nyima3");
list2.add("Nyima4");
list2.add("Nyima5");
// 在指定位置插入所有集合
list2.addAll(1, list);
}
}
public boolean addAll(int index, Collection<? extends E> c) {
// 进行边界检查，如果超出集合范围，则会抛出异常
rangeCheckForAdd(index);
// 将要插入的集合转为Object类型的数组
Object[] a = c.toArray();
// 得到插入数组的长度
int numNew = a.length;
// 根据需求进行扩容操作
ensureCapacityInternal(size + numNew); // Increments modCount
// 计算需要移动的步数
int numMoved = size - index;
// 如果需要移动的步数大于0， 则进行移动操作
if (numMoved > 0)
// 先将被插入数组中在index之后的元素向后移动
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 在指定位置插入数组
System.arraycopy(a, 0, elementData, index, numNew);
// 增加size的大小
size += numNew;
// 返回是否插入成功
return numNew != 0;
}这里的插入操作和 add(int index, E element) 方法有一些类似。边界判断、集合转数组、数组扩容等。并且在移动被插入数组中的元素时，都用到了 System.arraycopy() 方法。只不过 add(int index, E element) 只用插入一个元素，所以直接插入就可以了。而 addAll(int index, Collection<? extends E> c) 方法因为需要插入多个元素，所以再次用到了 System.arraycopy() 方法，来进行多个元素的插入操作
3、移除方法
remove(int index)方法
public E remove(int index) {
// 判断是否越界
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 需要移动的元素个数
int numMoved = size - index - 1;
// 从index+1开始，后面的元素全部前移1位
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 让最后一个元素置空，让GC来清楚它
elementData[--size] = null; // clear to let GC do its work
// 返回被移除的元素
return oldValue;
}remove(Object o)方法
public boolean remove(Object o) {
// 被移除的元素为空
if (o == null) {
for (int index = 0; index < size; index++)
// 移除为空的元素
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
// 移除指定的元素
if (o.equals(elementData[index])) {
// 每次删除一个元素
fastRemove(index);
return true;
}
}
// 移除失败
return false;
}
// 这个方法和remove(int index)方法有些类似，只不过不用返回被删除的元素
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 让最后一个元素置空，让GC来清楚它
elementData[--size] = null; // clear to let GC do its work
}4、set/get方法
set(int index, E element)方法
public E set(int index, E element) {
// 判断索引是否越界
rangeCheck(index);
// 用oldValue保存数组中index位置上的元素
E oldValue = elementData(index);
// 将要插入的元素插入到数组的index位置上
elementData[index] = element;
// 返回index原来位置上的元素
return oldValue;
}set方法在改变数组中指定位置的元素时，会返回被覆盖的元素
get(int index)方法
public E get(int index) {
// 判断索引是否越界
rangeCheck(index);
// 返回数组中index位置上的元素
return elementData(index);
}5、转化方法
toString()方法
ArrayList 的 toString 方法调用的是其祖宗类 AbstractCollection 的toString 方法
public abstract class AbstractCollection<E> implements Collection<E> {
public String toString() {
// 获取迭代器
Iterator<E> it = iterator();
// 如果迭代器为空，就返回"[]"
if (! it.hasNext())
return "[]";
// 使用StringBuilder来进行字符串的拼接
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
// 获取一个元素
E e = it.next();
// 进行拼接操作
sb.append(e == this ? "(this Collection)" : e);
// 看是否还有下一个元素
if (! it.hasNext())
// 如果没有，就加上']'，并调用toStrng方法转化为String类型
return sb.append(']').toString();
// 如果还有下一个元素，就加上 ", " 进行分割
sb.append(',').append(' ');
}
}
}6、迭代器
iterator()普通迭代器
案例一：使用迭代器遍历获取集合的每一个元素
public Iterator<E> iterator() {
return new Itr();
}
// Itr为ArrayList中的内部类
private class Itr implements Iterator<E> {
// 光标，用于指向下次被查看的元素。 一开始为0
int cursor; // index of next element to return
// 最后一个元素的索引，如果没有元素就是-1
int lastRet = -1; // index of last element returned; -1 if no such
// 期望的被修改次数 = 开始迭代时被修改的次数。主要是为了检查多线程情况下，是否出现了并发安全性问题
int expectedModCount = modCount;
// 无参构造函数
Itr() {}
// 查看是否到了末尾， 如果光标和数组大小相等，则到了末尾
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
// 检查是否有并发安全性问题
checkForComodification();
// i 用来访问数组中的元素。 把光标的值赋值给i
int i = cursor;
// 如果越界，抛出异常
if (i >= size)
throw new NoSuchElementException();
// 将被迭代的数组赋值给elementData
Object[] elementData = ArrayList.this.elementData;
// 是否越界
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 光标后移
cursor = i + 1;
// 给lastRet赋值，同时返回 i 指向的元素
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
// 看当前的 modCount 和迭代开始前的 modCount (expectedModCount)是否相同
if (modCount != expectedModCount)
// 如果不同，抛出异常
throw new ConcurrentModificationException();
}
}案例二：在使用迭代器遍历元素时，删除最后一个元素
public class Demo3 {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("Nyima1");
arrayList.add("Nyima2");
arrayList.add("Nyima3");
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
String tempStr = (String) iterator.next();
// 移除最后一个元素
if(tempStr.equals("Nyima3")) {
arrayList.remove(tempStr);
}
}
}
}运行结果
问题分析
每次进行遍历操作调用 next 方法时，在开头都会先调用checkForComodification方法，来判断modCount是否和expectedModCount是否一致
在删除指定元素前的遍历中，可以看到 modCount 和 expectedModCount 相同，都为3
进行删除操作，删除操作会使得数组的大小-1
public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } /* * Private remove method that skips bounds checking and does not * return the value removed. */ private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // 这里会使得数组的大小-1 elementData[--size] = null; // clear to let GC do its work }继续向下执行，会发现在遍历了所有元素之后，循环并没有第一时间就停下来！
- 可以看到，hasNext 是根据光标和数组大小是否一致来判断是否有下一个元素的
- 再次执行next，此时发现modCount是否和expectedModCount不一致！便抛出了异常
- modCount的增加是因为前面进行了删除操作，使得modCount的值+1了
结论：在使用迭代器进行遍历时，如果中途移除了最后一个元素，则会出现并发修改异常。因为在遍历过程中modCount的值被修改了
案例三：使用迭代器删除倒数第二个元素
public class Demo3 {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("Nyima1");
arrayList.add("Nyima2");
arrayList.add("Nyima3");
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
String tempStr = (String) iterator.next();
// 移除倒数第二个元素
if(tempStr.equals("Nyima2")) {
arrayList.remove(tempStr);
}
}
}
}运行结果：没有抛出异常
问题分析：
在删除第二个元素的时候，modCount确实增加了 3->4
因为删除了一个元素，此时的数组大小 size = 2，与光标cursor的大小一致了 ！
- 所以还没来得及做下一次 modCount 和 expectedModCount 的检测，就跳出了循环
在遍历ArrayList时，不要对集合中的元素进行增加与修改操作。如果要进行元素的删除，最好使用迭代器自身的 remove() 方法
iterator.remove();迭代器默认remove()方法
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
// 调用方法检测 modCount 和 expectedModCount，此时还未进行删除操作，所以两个值相同
checkForComodification();
try {
// 调用ArrayList的remove(index)方法进行删除，此操作会修改modCount的值
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// 更新 expectedModCount 的值
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}可以看出，迭代器默认的remove方法，在进行完删除操作后，更新了 expectedModCount 的值，使得其与modCount一致
7、清空方法
clear()方法
public void clear() {
modCount++;
// clear to let GC do its work
// 依次将数组中的元素置为null，方便GC来回收内存
for (int i = 0; i < size; i++)
elementData[i] = null;
// 将容量设置为0
size = 0;
}8、包含方法
contains(Object o)方法
// 将参数转为了Object类型
public boolean contains(Object o) {
// 调用 indexOf 方法，查找o的索引。如果索引值大于等于0，就返回true，反之返回false
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
// 传入参数是否为 null
if (o == null) {
// 依次遍历数组，返回遇到的第一个null的索引
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
// 遍历数组，返回遇到的第一个o的索引
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
// 如果数组中没有该元素，就返回-1
return -1;
}LinkedList
一、LinkedList底层数据结构
1、LinkedList集合介绍
LinkedList底层由一个拥有头、尾指针的双向链表构成
2、链表
链表的增删插入效率高，但是查找效率较低
详细可见Java数据结构与算法——链表
二、LinkedList继承关系
1、继承关系图
LinkedList也实现了Serializable和Clonealbe接口，但因为链表随机访问效率较低，所以未实现RandomAccess方法
2、clone方法
public Object clone() {
// 调用本地方法，将链表进行克隆，此时clone里元素与被克隆链表的元素一致
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
// 克隆出来的链表的头、尾指针都为null。此时clone被清空了，因为没有指针指向clone链表的任意元素
clone.first = clone.last = null;
// 克隆出来的链表size为0
clone.size = 0;
// 修改次数为0
clone.modCount = 0;
// Initialize clone with our elements
// 初始化克隆链表，为其添加元素
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
// 返回克隆链表
return clone;
}
private LinkedList<E> superClone() {
try {
// 调用本地方法进行克隆操作
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}三、LinkedList源码分析
1、构造方法
无参构造方法
// 链表的容量
transient int size = 0;
// 链表的头指针
transient Node<E> first;
// 链表的尾指针
transient Node<E> last;
// 创建了一个空链表
public LinkedList() {
}Collection构造方法
public LinkedList(Collection<? extends E> c) {
// 先调用无参构造函数， 初始化集合容积 size = 0， 并创建头尾指针
this();
// 调用方法，将传入的集合c添加到集合尾部
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
// 调用重载后的addAll()方法，并返回其结果
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 检查索引是否越界， 通过0和size来判断
checkPositionIndex(index);
// 将传入的集合转成Object类型的数组
Object[] a = c.toArray();
// 获得传入集合的长度，也就是需要插入的集合中元素的个数
int numNew = a.length;
// 如果其长度为0，则返回添加失败
if (numNew == 0)
return false;
// 创建两个节点
// pred保存插入位置的前驱节点， succ保存插入位置的节点
Node<E> pred, succ;
// 如果是在集合的末尾进行插入
if (index == size) {
// succ为空，pred为尾节点
succ = null;
pred = last;
} else {
// 如果不是在末尾进行插入, succ保存插入位置的节点，pred保存插入位置节点的前驱结点
succ = node(index);
pred = succ.prev;
}
// 使用增加for，通过迭代器顺序访问插入集合
for (Object o : a) {
// 将遍历的元素o赋值给变量e
@SuppressWarnings("unchecked") E e = (E) o;
// 创建Node对象，Node为LinkedList的内部类。
// 传入的值依次为：插入节点的前驱节点，该节点存储的数据，后继节点为null
Node<E> newNode = new Node<>(pred, e, null);
// 如果没有前驱节点，也就是在链表头部进行插入
if (pred == null)
// 该节点就是头结点
first = newNode;
else
// 如果有前驱结点，前驱结点就指向该节点
pred.next = newNode;
// 前驱节点后移，指向该节点
pred = newNode;
}
// 如果是在尾部进行插入
if (succ == null) {
// pred节点就是尾节点
last = pred;
} else {
// 否则 pred 与 succ 互相指向对方
pred.next = succ;
succ.prev = pred;
}
// size扩大
size += numNew;
// 修改次数+1
modCount++;
// 返回修改成功
return true;
}
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;
}
}该构造函数先创建了一个空链表，然后调用了addAll()方法将待插入集合插入链表中
图解插入过程：addAll()方法
情况一：在尾部插入
- pred指向尾部的节点，succ指向null
- 遍历待插入数组，取出第一个元素
- 调用Node<>的构造方法，在初始化节点时，将其前驱结点赋值为pred节点
- 放在pred节点的后面，pred.next指向newNode。此时succ依然指向null
- pred后移，指向刚插入的节点
- 重复上面的步骤，直到待插入集合中所有元素都插入到链表当中
- 插入完毕后，因为succ为null，所以尾指针last变为pred
情况二：在中间进行插入
- 在index=2处（第三个节点）处进行插入，succ保存了插入位置的节点，pred为其前驱节点
- 在pred后面插入元素
- 一直插入元素，直到插入完成
- 如果succ不为空（指向了插入位置处的节点），pred的后继节点为succ，succ的前驱为pred
可见，在LinkedList中间进行插入，是在index处节点之前进行插入操作的
情况三：在头部进行插入
先使用头插法插入第一个元素
- succ指向了头结点，pred指向其前驱，此时为null
- 如果pred为空，则头指针 first 指向 newNode。让pred指向newNode
- 然后在头结点之后插入剩余元素，因为此时的pred已经不为空了
- pred指向新插入的节点，此时待插入集合为空。pred 与 succ 互相指向对方。插入完毕
2、添加方法
addFirst(E e)方法
public void addFirst(E e) {
// 调用linkFirst()方法
linkFirst(e);
}
// 私有方法，用头插法插入元素
private void linkFirst(E e) {
// 用 f 保存插入前链表中的头节点
final Node<E> f = first;
// 创建一个新节点，值为待插入元素的值(e)， 后继节点为 f (插入前的头结点)
final Node<E> newNode = new Node<>(null, e, f);
// 头结点变为新插入的节点newNode
first = newNode;
// 如果 f 为空，也就是插入前链表为空
if (f == null)
// newNode同时也是尾节点
last = newNode;
else
// 否则，newNode 为 f 的前驱结点
f.prev = newNode;
size++;
modCount++;
}addFirst进行头插法插入元素时，会调用私有方法linkFirst来进行插入操作
addLast(E e)方法
public void addLast(E e) {
// 调用linkLast()方法来进行尾部插入
linkLast(e);
}
void linkLast(E e) {
// 用 l 来保存链表的尾节点
final Node<E> l = last;
// 创建新节点，值为待插入节点的值（e），前驱节点为l，也就是插入前的尾节点
final Node<E> newNode = new Node<>(l, e, null);
// newNode变为尾节点（last）
last = newNode;
// 如果 l 为空，也就是插入前链表为空
if (l == null)
// newNode也是头结点
first = newNode;
else
// l的后继节点为newNode
l.next = newNode;
size++;
modCount++;
}add(E e)方法
public boolean add(E e) {
// 调用linkLast在末尾进行插入
linkLast(e);
return true;
}add(int index, E element)方法
public void add(int index, E element) {
// 检查index是否越界
checkPositionIndex(index);
// 如果 index == size，就在末尾进行插入
if (index == size)
linkLast(element);
else
// 否则就调用linkBefore()方法，在index处节点前进行插入
// 调用了node()方法，来获取指定索引出的元素
linkBefore(element, node(index));
}
Node<E> node(int index) {
// assert isElementIndex(index);
// 看index是在链表的前半段还是后半段
if (index < (size >> 1)) {
// 如果是前半段，就通过first节点从前向后扫描
Node<E> x = first;
// 找到index处的元素并返回。0->index-1
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 否则，就通过last从后往前找
Node<E> x = last;
// 找到index的元素并返回。size-1 -> index；
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// e: 待插入节点
// succ: index位置上的节点
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 用pred为插入位置节点的前驱结点
final Node<E> pred = succ.prev;
// 创建新节点，值为插入节点e，前驱结点为pred，后继为succ
final Node<E> newNode = new Node<>(pred, e, succ);
// succ的前驱改为newNode，不再是pred
succ.prev = newNode;
// 如果pred为空，就是插入位置为链表头结点
if (pred == null)
// newNode就是头结点
first = newNode;
else
// 否则，pred的后继为newNode
pred.next = newNode;
size++;
modCount++;
}addAll(Collection<? extends E> c)方法
public boolean addAll(Collection<? extends E> c) {
// 调用addAll(index, e)方法，也就是Collection构造函数时使用的那个方法
return addAll(size, c);
}addAll(int index, Collection<? extends E> c)方法
详见Collection构造函数调用 addAll()方法时的分析
3、移除方法
remove()方法
remove()方法就是调用的removeFirst()方法，实际上是对removeFirst()及unlinkFirst()的解析
public E remove() {
// 调用removeFirst()方法，移除链表首个元素
return removeFirst();
}
public E removeFirst() {
// 创建新节点f用于保存头结点
final Node<E> f = first;
// 如果头结点为空，也就是链表为空，抛出异常
if (f == null)
throw new NoSuchElementException();
// 调用unlinkFirst()方法，并返回结果
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 创建element保存头结点的值，用于最后的返回
final E element = f.item;
// next保存头结点后面的一个节点
final Node<E> next = f.next;
// 头结点的属性置空，方便回收
f.item = null;
f.next = null; // help GC
// 头指针first后移
first = next;
// 如果链表只有一个节点
if (next == null)
// 尾指针为空
last = null;
else
//否则，next的前驱结点为null（next现在是头结点）
next.prev = null;
size--;
modCount++;
// 返回被移除的节点的值
return element;
}removeFirst()方法
见remove()方法解析
removeLast()方法
public E removeLast() {
// 创建新节点l保存尾节点
final Node<E> l = last;
// 如果尾节点为空(链表为空)，就抛出异常
if (l == null)
throw new NoSuchElementException();
// 返回unlinkLast()方法的返回结果
return unlinkLast(l);
}
// 该方法和unlinkFirst方法类似，只不过是对尾节点进行删除操作
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}remove(Object o)方法
移除首个遇到的指定元素
public boolean remove(Object o) {
// 如果要删除的元素为null
if (o == null) {
// 从头开始遍历链表
for (Node<E> x = first; x != null; x = x.next) {
// 遇到节点值为null的，就调用unlink()方法执行删除操作
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
// 从头开始遍历链表
for (Node<E> x = first; x != null; x = x.next) {
// 如果是要删除的元素，就调用unlink()方法执行删除操作
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
// assert x != null;
// 保存被删除节点的值，用于返回
final E element = x.item;
// next节点用于保存被删除节点的后继节点
final Node<E> next = x.next;
// prev节点用于保存被删除节点的前驱结点
final Node<E> prev = x.prev;
// 如果前驱节点为null，即被删除的节点是头结点
if (prev == null) {
// 头指针指向被删除节点的下一个节点（next）
first = next;
} else {
// 否则，被删除节点的前驱结点指向其后继节点
prev.next = next;
// 被删除节点的前驱结点为null
x.prev = null;
}
// 如果没有后继节点，即被删除元素是链表的尾节点
if (next == null) {
// 尾指针指向被删除节点的前一个节点
last = prev;
} else {
// 否则，被删除节点的后继节点指向其前驱结点
next.prev = prev;
// 被删除节点的后继节点为null
x.next = null;
}
// 被删除节点的属性为null
x.item = null;
size--;
modCount++;
return element;
}可以看到，unlinkFirst()、unlinkLast()和unlink()方法非常类似，都用于让某个节点从链表中移除的操作。只不过unlinkFirst和unlinkLast删除的是头、尾节点，实现相对简单。而unlink则是一个更完整的实现，可以删除链表中的任一元素
remove(int index)方法
public E remove(int index) {
// 检查索引是否越界
checkElementIndex(index);
// 找到该位置的节点，调用unlink方法进行删除
return unlink(node(index));
}removeFirstOccurrence(Object o)方法
该方法用于移除链表中第一次出现该元素的节点
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}可以看出removeFirstOccurrence(Object o)方法其实就是调用的remove(Object o)方法，来进行链表首个指定元素的删除操作的
removeLastOccurrence(Object o)方法
该方法用于移除链表中最后一次出现该元素的节点
public boolean removeLastOccurrence(Object o) {
// 从链表尾部进行查询，找到指定元素，删除后返回
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}4、迭代器
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
// 构造方法，如果不传入index参数，则默认传入0
ListItr(int index) {
// assert isPositionIndex(index);
// 给next和nextIndex赋值
next = (index == size) ? null : node(index);
nextIndex = index;
}
// 是否还有下一个元素
public boolean hasNext() {
// 索引小于size则返回true
return nextIndex < size;
}
public E next() {
// 检查是否有并发问题，modeCount与expectedModCount是否相等
checkForComodification();
// 如果没有下一个元素了，就抛出异常
if (!hasNext())
throw new NoSuchElementException();
// 用于返回的元素
lastReturned = next;
// 后移一位
next = next.next;
// 索引+1
nextIndex++;
// 返回元素的值
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}注意：使用迭代器遍历时，如果要删除，请使用迭代器中的remove()方法，而不要使用LinkedList实现的remove()方法。和ArrayList相似
5、清空方法
clear()方法
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
// 从头节点开始遍历链表，将每个节点的每个属性都设置为null，以便于GC更彻底的清理
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}6、包含方法
contains(Object o)方法
从头遍历，遇到需要查找的元素就返回其索引，然后根据其索引来判断是否有该元素
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}区分node(), indexOf()和lastIndexOf()方法
相同点
- 这三个方法都用于查找
不同点
- node(index)方法是用来返回指定索引处的节点的
- indexOf(o)是用来返回第一次遇到o时，节点的索引（从前往后找）
- lastIndexOf(o)是用来返回最后一次遇到o时，节点的索引（从后往前找）
HashMap
一、哈希表简介
可以参考Java数据结构与算法——哈希表
- 核心是基于哈希值的桶和链表
- 一般用数组实现桶
- 发生哈希碰撞时，用链表来链接发生碰撞的元素
- O(1)的平均查找、插入、删除时间
- 致命缺点是哈希值的碰撞(collision)
- 哈希碰撞：元素通过哈希函数计算后，被映射到同一个桶中。例如上图中的桶1, 5中的元素就发生了哈希碰撞
二、继承关系
三、Java 7 HashMap
这里只针对 Java 7 中不足的地方做简单分析
1、构造方法
无参构造方法
// 默认初始化容量 2^4 = 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子 0.75，用于计算阈值，进行扩容操作。选择0.75是一种在时间和空间上的折中选择
// 如果当前哈希表中的元素个数 >= 容量 × 负载因子，就会进行扩容，否则可能就会发生严重的哈希碰撞
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 此处调用了含容量和负载因子的构造方法来进行初始化操作
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}含容量的构造方法
public HashMap(int initialCapacity) {
// 调用了含容量和负载因子的构造方法来进行初始化操作，其中容量为传入的容量，负载因子为默认负载因子0.75
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}含容量和负载因子的构造方法
public HashMap(int initialCapacity, float loadFactor) {
// 如果传入的初始化容量小于0，则抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 如果传入的容量大于最大容量，就初始化为最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 如果负载因子小于0，或者是非法的浮点数，抛出异常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// 根据传入的负载因子给负载因子赋值
this.loadFactor = loadFactor;
// int threshold
// 阈值，容量×负载因子。目前大小为initialCapacity（还未扩容）
// 超过阈值进行扩容操作
threshold = initialCapacity;
// 此处的init()方法是一个空方法，在向哈希表添加元素之前，不会真正地创建哈希表（以免占用过多的内存）
init();
}
// 空方法
void init() {
}可见，无论调用哪种构造函数来初始化HashMap，最终调用的都是含容量和负载因子的构造方法，并且都没有真正的开辟出需要的内存空间
2、添加方法
put()方法
// 空集合，用于判断表是否为空。Entry为hashMap的静态内部类
static final Entry<?,?>[] EMPTY_TABLE = {};
public V put(K key, V value) {
// 如果表是空的，就通过inflateTable()方法进行扩容
if (table == EMPTY_TABLE) {
// 等到真正向哈希表中添加元素时，才开辟内存空间
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
// 计算要插入元素的哈希值
int hash = hash(key);
// 根据哈希值来判断插入元素应该放在哪个桶中
// 该方法决定了为什么哈希表的容量是2的幂
int i = indexFor(hash, table.length);
// 遍历哈希表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 看待插入元素在哈希表中是否已近存在了，如果存在了，就进行覆盖操作
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 真正的添加操作，采用头插法，下面会单独来说
addEntry(hash, key, value, i);
return null;
}
// 哈希表扩容函数
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 让容量向上舍入变为2的幂。比如toSize = 10 就会变为 16。
int capacity = roundUpToPowerOf2(toSize);
// 阈值，向上取整后的容量×负载因子 或 最大容量+1，取其中的较小值
// 该变量在第一次放入操作时不会用到
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
// 根据capacity创建哈希表
table = new Entry[capacity];
// 创建了一个哈希种子，重构String的hash算法，在后面的潜在安全漏洞会谈到
initHashSeedAsNeeded(capacity);
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
// 如果容量大于最大容量，就返回最大容量。
// 否则调用Integer.highestOneBit()方法让其向上舍入为2的幂
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}
// 通过一系列移位操作与异或操作获得元素的哈希值。 JDK 8 中已不再使用该方法
final int hash(Object k) {
int h = hashSeed;
// 如果哈希种子存在，并且进行哈希的元素的String类型
if (0 != h && k instanceof String) {
// 就让String使用另一种hash算法
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}为什么哈希表大小一定是2的幂？
要回答这个问题，我们需要先看看哈希表中一个重要的方法：static int indexFor(int h, int length)，该方法会根据插入元素的哈希值决定该元素应该被放在桶中
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
// 将传入的哈希值与其长度-1进行按位与操作，并返回其结果
return h & (length-1);
}我们知道，哈希表的致命缺点是发生哈希碰撞，也就是多个哈希值相同的元素被放置到了同一个桶中
想要尽量避免发生哈希碰撞，分别分到不同的桶中，h & (length-1) 就是这样一个操作，根据元素的哈希值和哈希表的长度-1来按位与，并且与运算的速度快，效率高
当哈希表的大小为2的幂时，我们拿16来举例，它的二进制表示是 10000 ， 让其长度-1后就是 1111，全部都是1
我们知道，当一个二进制数与全为1的数进行按位与时，其结果就是该数本身并且小于等于桶的最大数量。这样一来，只要数不同，那么他们按位与下来的值也就不同了，所以我们需要哈希表的容量为2的幂
为什么使用位运算，而不是直接取模？
位运算(&)效率要比代替取模运算(%)高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。
addEntry()方法
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果哈希表中的元素个数超过了阈值，并且该元素应该放入的桶中已经有了元素
if ((size >= threshold) && (null != table[bucketIndex])) {
// 进行扩容，扩容大小为原大小的2倍，以保证扩容后容量仍为2的幂
// 并将扩容前哈希表中的元素全部重新计算哈希值，并放入到扩容后的桶中
resize(2 * table.length);
// 重新计算哈希值
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// 创建节点，采用头插法将其放在对应的桶中
createEntry(hash, key, value, bucketIndex);
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 扩容为新容量
Entry[] newTable = new Entry[newCapacity];
// 重新计算元素哈希值，再放入到扩容后的哈希表中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//重新计算阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
// 遍历原来哈希表中的元素
for (Entry<K,V> e : table) {
// 如果桶中元素不为空，就重新计算起哈希值，然后放入到扩容后的哈希表中
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
// 扩容转移时使用头插法
newTable[i] = e;
e = next;
}
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 将新节点放在桶的第一个位置，也就是采用头插法进行插入
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}3、存在的问题
容易发生死锁
因为HashMap本身是线程不安全的，所以在多线程环境下，可能会发生死锁问题
潜在的安全漏洞
哈希碰撞可能使哈希表退化为链表，链表的查询效率低，一旦退话，将会严重拖慢我们程序的性能
String的哈希算法很容易就能产生多个哈希值相同字符串
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}黑客可以在url中携带多个哈希值一样的字符串，来访问我们的服务器，此时因为所有字符串的哈希值相同，所以都会被放到同一个桶中，使得哈希表退化为链表，大幅度降低我们的性能。为了避免这种攻击，在 JDK 7 的哈希表中，重构了String类型计算哈希值的方法
四、Java 8 HashMap
1、红黑树TreeMap
基本介绍
一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树（由于是弱平衡，可以看到，在相同的节点情况下，AVL树的高度低于红黑树），相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，我们就用红黑树
性质
- 每个节点非红即黑
- 根节点（root）是黑的
- 不能有两个红色的节点连在一起（黑色可以）
- 每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的
- 如果一个节点是红的，那么它的两儿子都是黑的
- 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点
- 每条路径都包含相同的黑节点
为什么用到了红黑树
让我们来看看注释
/*
HashMap 底层是基于散列算法实现，散列算法分为散列再探测和拉链式。HashMap 则使用了拉链式的散列算法，并在 JDK 1.8 中引入了红黑树优化过长的链表
实现注意事项。
链表结构（这里叫 bin ，箱子）
Map通常充当一个binned（桶）的哈希表，但是当箱子变得太大时，它们就会被转换成TreeNodes的箱子，每个箱子的结构都类似于java.util.TreeMap。
大多数方法都尝试使用普通的垃圾箱，但是在适用的情况下（只要检查一个节点的实例）就可以传递到TreeNode方法。
可以像其他的一样遍历和使用TreeNodes，但是在过度填充的时候支持更快的查找
然而，由于大多数正常使用的箱子没有过多的填充，所以在表方法的过程中，检查树箱的存在可能会被延迟。
树箱(bins即所有的元素都是TreeNodes）主要是由hashCode来排序的，但是在特定的情况下，
如果两个元素是相同的“实现了Comparable接口”，那么使用它们的比较方法排序。
（我们通过反射来保守地检查泛型类型，以验证这一点——参见方法comparableClassFor）。
使用树带来的额外复杂，是非常有价值的，因为能提供了最坏只有O(log n)的时间复杂度当键有不同的散列或可排序。
因此,性能降低优雅地在意外或恶意使用hashCode()返回值的分布很差,以及许多key共享一个hashCode,只要他们是可比较的。
（如果这两种方法都不适用，同时不采取任何预防措施，我们可能会在时间和空间上浪费大约两倍的时间。
但是，唯一已知的案例源于糟糕的用户编程实践，这些实践已经非常缓慢，这几乎没有什么区别。）
因为TreeNodes大小大约是普通节点的两倍，所以只有当容器包含足够的节点来保证使用时才使用它们（见treeifythreshold）。
当它们变得太小（由于移除或调整大小），它们就会被转换回普通bins。
在使用良好的用户hashcode的用法中，很少使用树箱。
理想情况下，在随机的hashcode中，箱子中节点的频率遵循泊松分布（http://en.wikipedia.org/wiki/Poisson_distribution），
默认大小调整阈值为0.75，但由于调整粒度的大小有很大的差异。
忽略方差，list的长度 k=(exp(-0.5) * pow(0.5, k) / factorial(k))
第一个值是:
0:0.60653066
1:0.30326533
2:0.07581633
3:0.01263606
4:0.00157952
5:0.00015795
6:0.00001316
7:0.00000094
8:0.00000006
more: less than 1 in ten million 如果再多的话，概率就小于十万分之一了
树箱（tree bin很难翻译啊！）的根通常是它的第一个节点。
然而，有时（目前只在Iterator.remove）中，根可能在其他地方，但是可以通过父链接（方法TreeNode.root()）恢复。
所有适用的内部方法都接受散列码作为参数（通常由公共方法提供），允许它们在不重新计算用户hashcode的情况下调用彼此。
大多数内部方法也接受一个“标签”参数，通常是当前表，但在调整或转换时可能是新的或旧的。
当bin列表被树化、分割或取消时（ treeified, split, or untreeified），我们将它们保持在相同的相对存取/遍历顺序（例如
字段Node.next）为了更好地保存位置，并稍微简化对调用迭代器的拆分和traversals的处理(splits and traversals that invoke iterator.remove)。
当在插入中使用比较器时，为了在重新平衡中保持一个总排序（或者在这里需要的接近），我们将类和标识符码作为连接开关。
由于子类LinkedHashMap的存在，普通(plain)与树模型(tree modes)之间的使用和转换变得复杂起来。
请参阅下面的hook方法，这些方法在插入、删除和访问时被调用，允许LinkedHashMap内部结构保持独立于这些机制。
（这还要求将Map实例传递给一些可能创建新节点的实用方法。）
concurrent-programming-like SSA-based编码风格有助于避免在所有扭曲的指针操作中出现混叠错误。
*/之所以选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢
而红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树就是为了查找数据快O(log n)，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当桶中元素大于8并且桶的个数大于64的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢
链表转红黑树体现了空间换时间的思想
2、属性
// 初始容量 16 (2的4次方)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子，默认为0.75，用于和容量一起决定扩容的阈值
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 使用红黑树的阈值，当桶中的元素个数（链表长度）大于8时，才会使用红黑树进行存储
static final int TREEIFY_THRESHOLD = 8;
// 使用链表的阈值，当桶中的元素个数小于6个时，就会由红黑树转变为链表
static final int UNTREEIFY_THRESHOLD = 6;
// 最小的红黑树化的桶数，当桶的个数大于64个时，就会使用红黑树进行存储
static final int MIN_TREEIFY_CAPACITY = 64;
// Node数组，也就是桶
transient Node<K, V>[] table;
// 缓存entrySet
transient Set<Map.Entry<K,V>> entrySet;
// map中k-v键值对的个数
transient int size;
// 修改访问标记
transient int modCount;
// 扩容阈值，等于 容量 × 负载因子，初始化时值为向上取2的幂
int threshold;
// 负载因子
final float loadFactor;3、存储结构
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}4、构造方法
无参构造方法
public HashMap() {
// 初始化了负载因子
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}HashMap(int initialCapacity)构造方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}HashMap(int initialCapacity, float loadFactor)方法
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 阈值，初始化时为传入容量取幂后的值
this.threshold = tableSizeFor(initialCapacity);
}
// 容量向上取整为2的幂
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}5、添加方法
put(K, V)方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的
// 那么这种处理就可以有效避免类似情况下的哈希碰撞
static final int hash(Object key) {
int h;
// 如果key不为null，就让key的高16位和低16位取异或
// 和Java 7 相比，hash算法确实简单了不少
// 使用异或尽可能的减少碰撞
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 放入元素的操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab相当于哈希表
Node<K,V>[] tab;
Node<K,V> p;
// n保存了桶的个数
// i保存了应放在哪个桶中
int n, i;
// 如果还没初始化哈希表，就调用resize方法进行初始化操作
// resize()方法在后面分析
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 这里的 (n - 1) & hash 相当于 Java 7 中的indexFor()方法，用于确定元素应该放在哪个桶中
// (n - 1) & hash 有以下两个好处：1、放入的位置不会大于桶的个数（n-1全为1） 2、用到了hash值，确定其应放的对应的位置
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 {
// binCount用于计算桶中元素的个数
for (int binCount = 0; ; ++binCount) {
// 找到插入的位置（链表最后）
if ((e = p.next) == null) {
// 尾插法插入元素
p.next = newNode(hash, key, value, null);
// 如果桶中元素个数大于阈值，就会调用treeifyBin()方法将其结构改为红黑树(但不一定转换成功)
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;
// 如果size大于阈值，就进行扩容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}resize()扩容方法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 原容量大于0（已近执行了put操作以后的扩容）
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 原容量扩大一倍后小于最大容量，那么newCap就为原容量扩大一倍，同时新阈值为老阈值的一倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 调用了含参构造方法的扩容
// 原容量小于等于0，但是阈值大于0，那么新容量就位原来的阈值（阈值在调用构造函数时就会确定，但容量不会）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 调用了无参构造方法的扩容操作
else {
// zero initial threshold signifies using defaults
// 如果连阈值也为0，那就调用的是无参构造方法，就执行初始化操作
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新阈值为0，就初始化它
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 阈值改为新阈值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的表，将旧表中的元素进行重新放入
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 为空就直接放入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是树节点，就调用红黑树的插入方式
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 链表的插入操作
else { // preserve order
// lo 和 hi 分别为两个链表，保存了原来一个桶中元素被拆分后的两个链表
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;
}图解扩容对链表的重构
- 比如哈希表中桶的个数是4个，其中0、4、8、12因为低两位都是0，与 4-1=3(11) 进行按位与后，都被放在了第一个桶中
然后开始了扩容操作。将元素哈希值按位与旧容量（不是旧容量-1）为0的放在lo链表中，不为0的放在hi链表中
do { next = e.next; // 当前元素的hash值和容量进行按位与，决定被分配到哪个链表中 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);
- 遍历链表，将lo中的放在原来的桶中，hi中的放在增加的桶中
// 通过头指针直接将链表放入桶中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
总结：
- 先将原桶中的元素的hash值与旧容量进行按位与操作
- 如果结果为0，就放入lo链表中
- 如果结果不为0，就放入hi链表中
- lo链表中的元素继续放在新的哈希表中原来的位置
- hi链表中的元素放在新的哈希表中，扩容后相对于原来的位置上(j+oldCap)
- 两个桶之间的间隔数就为增加原来哈希表的容量
好处
- 顺序放入，减少了发生死锁的几率
- 使得元素相对均匀地存在于哈希表中
putAll()方法
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 获得待插入表的大小
int s = m.size();
// 如果待插入表中有元素
if (s > 0) {
// 如果当前哈希表为空
if (table == null) { // pre-size
// 容量调整过程，如果超过阈值，就调用tableSizeFor()方法扩容(直接扩容，因为此时哈希表为空)
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
// 超过阈值，就调用resize()方法扩容
else if (s > threshold)
resize();
// 把元素依次放入到哈希表中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}最后这里用到了hash()，那就更深入地研究一下吧！
6、移除方法
remove()方法
public V remove(Object key) {
Node<K,V> e;
// 调用removeNode()方法，返回其返回的结果
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 桶中有元素, p保存了桶中的首个元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 找到对应的元素，保存在node中
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
// 遍历链表，找到要删除的元素
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 该元素不为空
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果是树节点，就调用红黑树的删除方法
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 如果是第一个元素，桶的索引就保存其下一个元素
else if (node == p)
tab[index] = node.next;
// 否则就不在指向这个元素
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}7、查找方法
get(Object key)方法
public V get(Object key) {
Node<K,V> e;
// 通过key的哈希值和key来进行查找
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 哈希表不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果第一个元素就是要查找的元素，就返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果第一个元素不是，就继续往后找。找到就返回，没至找到就返回null
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}8、树化方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果当前哈希表中桶的数目，小于最小树化容量，就调用resize()方法进行扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// 当桶中元素个数大于8，且桶的个数大于64时，进行树化
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}链表变为红黑树的条件：元素个数大于8同时桶的个数大于64
- 当某个桶中的元素个数大于8时，会调用treeifyBin()方法，但并不一定就会变为红黑树
- 当哈希表中桶的个数大于64时，才会真正进行让其转化为红黑树
为什么桶中元素多于了8个，桶的个数小于64，调用resize()方法就可以进行调整？
- 因为调用resize()方法进行扩容时，会让同一个桶中的元素进行桶的重新分配。一部分会被放新哈希表中在原来的位置上，一部分会被放在扩容后的位置上
详见上面resize()方法的分析和图解
PriorityQueue
一、优先队列简介
1、概念
平时我们了解到的队列，是一种满足先进先出的线性数据结构。优先队列与其有相似之处，但是也有所不同。
当我们向优先队列中插入元素的时候，优先队列会根据一定的条件将该元素插入到合适的位置
2、演示
创建一个一般队列Queue和优先队列PriorityQueue，分别向队列中以 2、1、3的顺序放入元素，观察他们的遍历结果
public class Demo3 {
public static void main(String[] args) {
Queue<Integer> normalQueue = new LinkedList<>();
normalQueue.add(2);
normalQueue.add(1);
normalQueue.add(3);
System.out.println("一般队列元素顺序");
for (Integer num : normalQueue) {
System.out.print(num + " ");
}
System.out.println();
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(2);
priorityQueue.add(1);
priorityQueue.add(3);
System.out.println("优先队列元素顺序");
for (Integer num : priorityQueue) {
System.out.print(num + " ");
}
}
}运行结果
一般队列元素顺序
2 1 3
优先队列元素顺序
1 2 33、Comparator接口
当我们想根据对象中的某些特定属性，来对对象进行排序的话，需要实现Comparator中的compare方法
@Override
public int compare(Object o1, Object o2) {
// o1为待插入元素，o2为被比较元素
return o1.val - o2.val;
}4、 Comparable接口
基本类型的包装类、集合类与接口几乎都实现了这个接口
该接口中的compareTo(T o)一般用于比较包装类型的大小
public int compareTo(T o);如Integer类中的该方法
如果该值大于被比较的值，则返回1
相等则返回0，小于则返回-1
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}5、按对象中的特定值进行插入
如果我们想将对象放入PriorityQueue中，并按照指定的方式进行排序，可以这样做
创建优先队列是，传入Comparator对象，并重写其compare方法，则会按照我们设定的规定进行比较
public class Demo4 {
public static void main(String[] args) {
// 创建优先队列，传入Comparator对象，并重写其compare方法
PriorityQueue<Student> priorityQueue = new PriorityQueue<>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
// 其中o1为要插入的值，o2为比较的目标值
return o1.getAge() - o2.getAge();
}
});
Student st1 = new Student("A", 3);
Student st2 = new Student("B", 1);
Student st3 = new Student("C", 2);
priorityQueue.add(st1);
priorityQueue.add(st2);
priorityQueue.add(st3);
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.remove());
}
}
}
class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}二、大顶堆和小顶堆
1、基本介绍
大顶堆和小顶堆都是完全二叉树，并且具有以下性质
大顶堆
- 根节点的值都大于其所有孩子的值
小顶堆
- 根节点的值都小于其所有孩子的值
因为大顶堆小顶堆都是完全二叉树，所以大顶堆和小顶堆都可以用数组加以表示
如果一个数组，根节点的下标为index
- 那么它左孩子的下标为2*index+1，
- 右孩子的值为2*(index+1)
以小顶堆为例
2、如何构造
若我们要构建小顶堆，当叶子节点的值小于其父节点的值时，将其于其父节点的值进行交换，知道换在了合适的位置上。我们称这个过程为上浮
三、属性和存储结构
// 默认容量大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// Object数组，用于存放我们的元素,在操作过程中体现为堆
transient Object[] queue; // non-private to simplify nested class access
// 数组中元素的个数
private int size = 0;
// 比较器，其中的compare方法可用于比较插入元素的值
private final Comparator<? super E> comparator;
// 操作次数计数器
transient int modCount = 0四、构造方法
1、默认构造方法
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}2、带初始容量构造方法
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}3、带比较器的构造方法
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}4、带容量和比较器的构造方法
从上面的三个构造函数可以看出，最终调用的都是这个构造函数。如果没有指定容量，就是用默认容量，如果没有指定比较器，就是用默认比较器
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
// 初始化数组
this.queue = new Object[initialCapacity];
// 给比较器赋值
this.comparator = comparator;
}五、添加方法
1、add(E e)方法
public boolean add(E e) {
return offer(e);
}2、offer(E e)方法
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
// 保存当前元素的个数
int i = size;
// 如果元素大于了Object数组的长度，就进行扩容
if (i >= queue.length)
grow(i + 1);
// 否则元素个数+1
size = i + 1;
// 如果数组中还没有元素，就直接放入
if (i == 0)
queue[0] = e;
// 否则，进行调整操作
// 其中i为队列最后一个元素的下一个位置，e为待插入元素
else
siftUp(i, e);
return true;
}grow(int minCapacity)方法
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
// 如果队列容量小于64，就按照两倍扩容，否则就扩容50%
// 如 20 -> 42 100 -> 150
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 扩容后的复制操作
queue = Arrays.copyOf(queue, newCapacity);
}siftUp(int k, E x)函数
其中k为队列最后一个元素的下一个位置，x为待插入元素
private void siftUp(int k, E x) {
// 如果指定了比较器，就使用指定比较器的比较方法
if (comparator != null)
siftUpUsingComparator(k, x);
// 否则就使用默认的比较方法
else
siftUpComparable(k, x);
}指定了比较器的比较方法siftUpUsingComparator(int k, E x)
private void siftUpUsingComparator(int k, E x) {
// 如果要放入的位置不是根节点，就继续
while (k > 0) {
// 得到该元素的父节点
int parent = (k - 1) >>> 1;
// 保存其父节点
Object e = queue[parent];
// 如果父节点的值小于插入节点的值，就停止循环
if (comparator.compare(x, (E) e) >= 0)
break;
// 否则父节点下沉(插入元素上浮)
queue[k] = e;
// k保存其父节点的位置
k = parent;
}
// 将待插入元素放到对应的位置
queue[k] = x;
}图解
如果小顶堆中要插入元素3
此时k = 4，我们通过 parent = (k-1)/2，可以得到父节点的下标为1，也是就元素4所在的位置
3和4通过compare函数进行比较，结果小于0，待插入元素需要上浮，父节点元素需要下沉queue[k] = e
然后令 k = parrent
再次计算父节点的下标 parent = (k-1)/2 = 0，也就是元素1
1与3比较，3>1，结束循环
if (comparator.compare(x, (E) e) >= 0)
break;将待插入元素放到对应位置queue[k] = x
总结：可以看到，待插入元素一直在与其父节点进行比较，如果待插入元素的值小于父节点，则待父节点下沉，待插入元素上浮
默认比较方法siftUpComparable(int k, E x)
和指定了比较器的比较方法类似，只不过是通过Comparable来实现的
六、移除元素
1、remove()函数
调用父类AbstractQueue的remove()函数
public E remove() {
// 调用改类的poll函数
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}poll()函数
移除队首元素
public E poll() {
if (size == 0)
return null;
// s为新的元素个数
int s = --size;
modCount++;
// 队首元素
E result = (E) queue[0];
// 保存最后一个元素
E x = (E) queue[s];
queue[s] = null;
// 如果队列中还有元素
if (s != 0)
// 下沉
siftDown(0, x);
return result;
}siftDown(int k, E x)函数
k为移除元素的位置，x为队尾元素
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}指定了比较器的siftDownUsingComparator(int k, E x)函数
调整小顶堆，让其保持其特性
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
// 删除节点的左孩子的下标
int child = (k << 1) + 1;
// c保存了左孩子的值
Object c = queue[child];
// 删除节点的右孩子的下标
int right = child + 1;
// 如果右孩子小标小于size 并且 右孩子的值小于左孩子
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
// child保存右孩子小标，c保存右孩子
c = queue[child = right];
// 如果队尾元素小于c的值，就停止
if (comparator.compare(x, (E) c) <= 0)
break;
// 下沉
queue[k] = c;
k = child;
}
// 赋值
queue[k] = x;
}siftDownComparable(int k, E x)
和指定了比较器的比较方法类似，只不过是通过Comparable来实现的
2、remove(Object o)方法
public boolean remove(Object o) {
// 找到移除元素的下标
int i = indexOf(o);
if (i == -1)
return false;
else {
// 移除该元素
removeAt(i);
return true;
}
}indexOf()方法
private int indexOf(Object o) {
if (o != null) {
for (int i = 0; i < size; i++)
// 找到该对象并返回
if (o.equals(queue[i]))
return i;
}
return -1;
}removeAt(int i)方法
移除指定元素，保证移除后仍为小顶堆
private E removeAt(int i) {
// assert i >= 0 && i < size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}六、优先队列的应用
LeetCode–347. 前 K 个高频元素
public static int[] topKFrequent(int[] nums, int k) {
// 哈希表，用于存放数字出现的次数
// key：数字 value：出现次数
int length = nums.length;
HashMap<Integer, Integer> map = new HashMap<>(length);
// 遍历数组
for (int i = 0; i < length; i++) {
if (!map.containsKey(nums[i])) {
// 如果该数字是第一次出现，直接放入哈希表中
map.put(nums[i], 1);
} else {
// 否则，将其出现次数+1
map.put(nums[i], map.get(nums[i]) + 1);
}
}
// 创建优先队列，小顶堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// 插入元素与队尾元素的插值
return map.get(o1) - map.get(o2);
}
});
for (Integer key : map.keySet()) {
if (priorityQueue.size() < k) {
priorityQueue.add(key);
} else if (map.get(key) > map.get(priorityQueue.peek())) {
// 次数最少的元素在队首
priorityQueue.remove();
// 放入该数字
priorityQueue.add(key);
}
}
int size = priorityQueue.size();
int[] result = new int[size];
for (int i = size-1; i >= 0 ; i--) {
result[i] = priorityQueue.remove();
}
return result;
}本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！