JDK8-Java集合框架
1、集合框架图
什么是集合：对象的容器，定义了对多个对象进行操作的常用方法，可实现数组的功能
说明：对于以上的框架图有如下几点说明
1、所有集合类都位于java.util.*包下。Java 的集合类主要由两个接口派生而出：Collection 和 Map，Collection 和 Map 是 Java 集合框架的根接口，这两个接口又包含了一些子接口或实现类。
java.util包下UML类图：collection.svg
2.Set、List 和 Map 可以看作集合的三大类：
- List 集合是有序集合，集合中的元素可以重复，访问集合中的元素可以根据元素的索引来访问。
- Set 集合是无序集合，集合中的元素不可以重复，访问集合中的元素只能根据元素本身来访问（也是集合里元素不允许重复的原因）。
- Map 集合中保存 Key-value 对形式的元素，访问时只能根据每项元素的 key 来访问其 value。
3.集合与数组:
* 1.集合、数组都是对多个数据进行存储操作的结构，简称Java容器。
* 说明 : 此时的存储，主要指的是内存层面的存储，不涉及到持久化的存储(. txt,.jpg,.avi,数据库中)
* 2.1数组在存储多个数据方面的特点: .
* > 一旦初始化以后，其长度就确定了。
* >数组一旦定义好，其元素的类型也就确定了。我们也就只能操作指定类型的数据了。
* 比如: String[] arr ; int[] arr1 ; Object[] arr2;
* 2.2 数组在存储多个数据方面的缺点 :
* >一旦初始化以后，其长度就不可修改。
* >数组中提供的方法非常有限，对于添加、删除、插入数据等操作，非常不便，同时效率不高。
* >获取数组中实际元素的个数的需求，数组没有现成的属性或方法可用
* >数组存储数据的特点 : 有序、可重复，对于无序、不可重复的需求，不能满足。2、总体分析
大致说明：先抓住它的主干，即 Collection 和 Map。
1、Collection 是一个接口，是高度抽象出来的集合，它包含了集合的基本操作和属性。Collection 包含了 List 和 Set 两大分支。
- List 是一个有序、可重复的队列，“动态数组”，每一个元素都有它的索引。第一个元素的索引值是 0。List 的实现类有 LinkedList, ArrayList, Vector, Stack。
- Set 是一个不允许有重复元素的集合。Set 的实现类有 HastSet 和 TreeSet。HashSet 依赖于 HashMap，它实际上是通过 HashMap 实现的；TreeSet 依赖于 TreeMap，它实际上是通过 TreeMap 实现的。
[wppay]
2、Map 是一个映射接口，即 key-value 键值对。Map 中的每一个元素包含 “一个 key” 和“key 对应的 value”。AbstractMap 是个抽象类，它实现了 Map 接口中的大部分 API。而 HashMap，TreeMap，WeakHashMap 都是继承于 AbstractMap。Hashtable 虽然继承于 Dictionary，但它实现了 Map 接口。
3、接下来，再看 Iterator。它是遍历集合的工具，即我们通常通过 Iterator 迭代器来遍历集合。我们说 Collection 依赖于 Iterator，是因为 Collection 的实现类都要实现 iterator() 函数，返回一个 Iterator 对象。ListIterator 是专门为遍历 List 而存在的。
4、再看 Enumeration，它是 JDK 1.0 引入的抽象类。作用和 Iterator 一样，也是遍历集合；但是 Enumeration 的功能要比 Iterator 少。在上面的框图中，Enumeration 只能在 Hashtable, Vector, Stack 中使用。
5、最后，看 Arrays 和 Collections。它们是操作数组、集合的两个工具类。
3、Collection 接口
Collection 接口是处理对象集合的根接口，其中定义了很多对元素进行操作的方法。Collection 接口有两个主要的子接口 List 和 Set，注意 Map 不是 Collection 的子接口，这个要牢记。
有些可以重复，有些不可以重复；有些有序，有些无序
方法：
- 添加： boolean add(E e)
- 删除： boolean remove(Object o)
- 清空： void clear()
- 遍历：
- 增强for循环
- 遍历引用类型内部调用了送代器
- 不能使用集合删除方法删除元素.
- 迭代器Iterator
- 方法
- hasnext() 判断下一个元素是否非空
- next()
- remove()
- 注意
- next()不能调用多次
- 不能使用集合删除方法删除元素，否则出现并发修改异常ConcurrentModificationException，可以使用迭代器的删除方法。
- 实现原理：见下文。
- 方法
- 增强for循环
- 判断：
- 判断是否为空 boolean isEmpty()
- 判断是否存在 boolean contains(Object o)
- 元素个数：
- int size()
3.1 Collection 接口中的方法
class Person {
private String name;//姓名
private Integer age;//年龄
private String gender;//性别
getter与setter.......
}//Collection接口中的方法的使用
public class CollectionTest {
@Test
public void test1() {
Collection col = new ArrayList();
//add(object e): 将元素e添加到集合colL中
col.add("AA");
col.add(123);//自动装箱
col.add(new Date());
//size():获取添加的元素的个数
System.out.println(col.size());
//addALl(Collection coll1): 将coLl1集合中的元素添加到当前的集合中
Collection col1 = new ArrayList();
col1.add("AA");
col1.add(123);
col.addAll(col1);
System.out.println(col.size());
System.out.println(col);
//clear():清空集合元素
col.clear();
System.out.println(col);
///isEmpty():判断当前集合是否为空
System.out.println(col.isEmpty());
//contains(object obj):判断当前集合中是否包含obj 返回boolean
System.out.println(col.contains(123));
//containsAll(Collection coll1): 判断形参coll2中的所有元素是否都存在于当前集合中
Collection col2 = Arrays.asList(123, 4567);
System.out.println(col.containsAll(col2));
//remove(Oject object) 返回boolean
col.remove(123);
System.out.println(col);
//removeALl(Collection coll1):从当前集合中移除col1中所有的元素
Collection col3 = new ArrayList();
col3.add("AA");
col3.add(1233434);
col3.add(new Date());
col.removeAll(col3);
System.out.println(col);
//removeIf(Predicate<? super E> filter):删除满足给定谓词的这个集合的所有元素。
/* default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}*/
Person person = new Person();
person.setAge(20);
person.setGender("N");
person.setName("test");
col.add(person);
col.removeIf(new Predicate() {
@Override
public boolean test(Object o) {
return person.getAge()==20;
}
});
}
@Test
public void test4() {
Collection col = new ArrayList();
col.add("AA");
col.add(123);
col.add(new Date());
//retainAll(Collection object) 交集:获取当前集合和colL1集合的交集，并返回给当前集合
Collection col1 = new ArrayList();
col1.add("AA");
col1.add(123);
col.retainAll(col1);
System.out.println(col);
//equals(Object object) 要想返回true,需要当前集合和形参集合的元素都相同。
Collection col2 = new ArrayList();
col2.add("AA");
col2.add(123);
col2.add(new Date());
System.out.println(col.equals(col2));
}
@Test
public void test5() {
Collection col = new ArrayList();
col.add("AA");
col.add(123);
col.add(new Date());
//hashCode();返回当前对象的哈希值
System.out.println(col.hashCode());
//集合--->数组: toArray()
Object[] arr = col.toArray();
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
//数组--->集合: : 调用Arrays类的静态方法aslist()
List<String> strings = Arrays.asList(new String[] {"sad", "123"});
System.out.println(strings);
List<int[]> ints = Arrays.asList(new int[] {123, 134});
System.out.println(ints);//[[I@722c41f4]
System.out.println(ints.size());//1
List ints1 = Arrays.asList(123, 134);
System.out.println(ints1);//[123, 134]
System.out.println(ints1.size());//2
//iterator():返回Iterator接口的实例，用于遍历集合元素。见下：
}
}3.2 Iterator遍历集合元素
迭代器实现原理：两个指针，一个指向-1的位置，一个指向0的位置。 以0位置的指针进行元素位数的比较，下一位存在则加1。将原先0位置下标赋值给指向-1位置的指针。
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}源码：
public Iterator<E> iterator() {
return new Itr();
} private class Itr implements Iterator<E> {
int cursor; // index of next element to return
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();
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];
}
}以上文章也包含迭代器。
3.3 foreach遍历集合、数组
public class ForTest {
@Test
public void test() {
Collection col = new ArrayList();
col.add("AA");
col.add(123);
col.add(new Date());
//for(集合元素的类型局部变量:集合对象)
//内部仍然调用了送代器。
for (Object object : col) {
System.out.println(object);
}
int[] arr = new int[] {1, 2, 3, 4, 5};
for (int a : arr) {
System.out.println(a);
}
}
@Test
public void test2() {
String[] arr = new String[] {"AA", "AA", "AA"};
/*方式一 ：普通的for循环
for (int i = 0; i < arr.length; i++) {
arr[i] = "GG";
}*/
//方式二 ：普通的for循环
for (String s : arr) {
s = "GG";
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}toString()方法(为什么能用？)
ArrayList的父类AbstractCollection.class重写了toString方法，ArrayList继承了这个方法，在多态情况下Collection c = new ArrayList();，子类重写方法优先调用。
Java 动态绑定机制；Collection c = new ArrayList(); 这里编译时c 是Collection 类型，但在运行时会动态绑定到ArrayList 类型上所以c.toString() 调用的是AbstractCollection.class 重写的方法；但注意的是访问c的域值时，系统会试图访问c编译时类型所定义的域，而非运行时类型的
4. List 接口
有序、有下标、元素可重复。实现 List 接口的集合主要有：ArrayList、LinkedList、Vector、Stack。
方法：
- 添加 boolean add(E e)
- 删除 boolean remove(Object o)
- list.remove(new Person("l", 1));
- 没有重写equals比较的是地址,不能删除
- 重写后可以删除比较的是值
- 多个相同只删除查找到的第一个
- 删除数字要将数字转换为包装类,但是直接写也可以删除，原因是：自动装箱。
- list1.remove((Integer)10);
- list1.remove(new Integer(10));
- list.remove(new Person("l", 1));
测试删除：
public class Demo1 {
public static void main(String[] args) {
Collection<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
System.out.println(list.remove(3));
for (Integer o : list) {
System.out.println(o);
}
}
}对应的字节码文件
public class Demo1
{
public static void main(String args[])
{
Collection list = new ArrayList();
list.add(Integer.valueOf(1));
list.add(Integer.valueOf(2));
list.add(Integer.valueOf(3));
list.add(Integer.valueOf(4));
System.out.println(list.remove(Integer.valueOf(3)));
Integer o;
for (Iterator iterator = list.iterator(); iterator.hasNext(); System.out.println(o))
o = (Integer)iterator.next();
}
}- 清空 void clear()
- 遍历
- for循环(因为有下标了)
- 增强for(foreach)
- 迭代器(Itorater)
- 列表迭代器(listItorater) 比迭代器的功能强大 ，从前往后、从后往前
- 判断
- 判断是否为空 isEmpty()
- 判断是否存在 contains()
- 获取位置 get()
- 下标从0开始
public class ListDemo1 {
public static void main(String[] args) {
List list = new ArrayList();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
list.add(3);
//list.remove(new Integer(3));
//list.clear();
System.out.println(list.toString());
//列表迭代器
ListIterator iterator = list.listIterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
while (iterator.hasPrevious()) {
System.out.print(iterator.previous() + " ");
}
}
}public class ListDemo2 {
public static void main(String[] args) {
Person person = new Person("l", 1);
Person person1 = new Person("i", 2);
Person person2 = new Person("u", 3);
ArrayList list = new ArrayList();
//add
list.add(person);
list.add(person1);
list.add(person2);
//remove (默认使用比较equals，可以重写)
//不能删除，没有重写比较的是地址
//重写后可以删除比较的是值
list.remove(new Person("l", 1));
System.out.println("------------------");
//遍历(4种)
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
for (Object p : list
) {
System.out.print(p.toString() + " ");
}
System.out.println();
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
ListIterator listIterator = list.listIterator();
while (listIterator.hasNext()) {
System.out.print(listIterator.next() + " ");
}
System.out.println();
while (listIterator.hasPrevious()) {
System.out.print(listIterator.previous() + " ");
}
//判断
System.out.println(list.isEmpty());
//重写了equals true
System.out.println(list.contains(new Person("i", 2)));
System.out.println(list.indexOf(new Person("i", 2)));
//删除数字：数字转换为包装类
ArrayList list1 = new ArrayList();
list1.add(10);
list1.add(20);
//list1.remove((Integer)10);
list1.remove(new Integer(10));
System.out.println(list1.toString());
}
}
class Person {
private String name;
private int age;
public Person() {
}
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Person person = (Person) o;
return age == person.age && Objects.equals(name, person.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}4.1 ArrayList
ArrayList 作为List接口的主要实现类：ArrayList类图：ArrayList.svg
- 存储结构：数组。查询快、增删慢。
- JDK1.2，运行效率快，线程不安全。
扩容原理：
- 调用无参构造方法创建ArrayList对象后，数组的长度是0，节省空间
- 添加第一个元素时，空间扩容为10
- 每次扩容都是原来大小的1.5倍
方法：
- 添加 add
- 删除 remove
- 遍历
- for
- 增强for
- 迭代器
- 列表迭代器
- 判断
- isEmpty
- contains
- 同样equals默认比较的是地址，看需求是否重写
- 获取位置
- int indexOf(Object o)
- int lastIndexOf(Object o)
- 获取范围字符
- List subList(int fromIndex, int toIndex)
- 左闭右开
测试
public class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public Student() {
}
//getter setter
@Override
public boolean equals(Object obj) {
//1 判断是否为空
if(obj==null){
return false;
}
//2判断是否是同一个
if(this==obj){
return true;
}
//3判断是否是同一个类型
if(obj instanceof Student){
//4向下转型
Student s=(Student) obj;
//5比较
if(this.name.equals(s.name)&&this.age==s.age){
return true;
}
}
return false;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}public class ArrayListDemo {
public static void main(String[] args) {
//存储结构：数组。优点：查询快，缺点：增删慢
ArrayList list=new ArrayList();
Student s1=new Student("灿灿",20);
Student s2=new Student("龙哥",18);
Student s3=new Student("赵吉", 21);
//(1)添加元素
list.add(s1);
list.add(s2);
list.add(s3);
System.out.println("元素："+list.size());
System.out.println(list.toString());
//(2)删除
list.remove(new Student("灿灿",20));
//(3)遍历
//3.1 for
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
//3.2 增强for
//3.3 迭代器 ctrl+alt
Iterator it = list.iterator();
//3.4 列表迭代器
ListIterator lit= list.listIterator();
while(lit.hasNext()){
System.out.println(lit.next());
}
//4 判断
System.out.println(list.isEmpty());
System.out.println(list.contains(new Student("赵吉", 21)));
//5 获取位置
System.out.println(list.indexOf(new Student("赵吉", 21)));
}
}1.构造器与add()
构造器与add()操作方法图：ArrayList_add.svg
注：流程是按调试的步骤走的。
JDK1.7和JDK1.8下ArrayList()底层数组的默认长度不同，JDK1.7下ArrayList()初始化后的默认长度是10，源码如下：
//无参构造方法
public ArrayList() {
this(10);
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}2.add(int index, E element)
将指定的元素插入此列表中的指定位置。 将当前在该位置的元素（如果有）和任何后续元素右移（将其索引加一）。
add(int index, E element)操作方法图：ArrayList_add(x,x).svg
3.addAll(Collection<? extends E> c)
追加指定集合的所有元素到这个列表的末尾，按他们的指定集合的迭代器返回。
public boolean addAll(Collection<? extends E> c) {
//将传入的Collection转换为数组
Object[] a = c.toArray();
int numNew = a.length;
//原有效元素+添加集合元素？集合长度->扩容
ensureCapacityInternal(size + numNew); // Increments modCount
//将传入的集合元素添加到末尾
System.arraycopy(a, 0, elementData, size, numNew);
//有效元素个数增加
size += numNew;
return numNew != 0;
}4.addAll(int index, Collection<? extends E> c)
将指定集合中的所有元素插入到该列表中，从指定位置开始。
public boolean addAll(int index, Collection<? extends E> c) {
//判断index是否越界
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
//需要移动元素的个数
int numMoved = size - index;
//移动index后元素numNew个位置
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//添加元素
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}5.clear()
从这个列表中移除所有的元素。
public void clear() {
//修改加1
modCount++;
//置空
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
//有效元素个数为0
size = 0;
}4.clone()
返回该 ArrayList实例浅拷贝。
public Object clone() {
//返回此ArrayList实例的浅拷贝（值类型复制一份值、引用类型执行第一份的地址）
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
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);
}
}5.contains(Object o)
如果这个列表包含指定元素返回 true。
public boolean contains(Object o) {
return indexOf(o) >= 0;
}public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i] == null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}6.get(int index)
- 返回此列表中指定位置的元素。
public E get(int index) {
//检查index是否越界
rangeCheck(index);
return elementData(index);
}7.indexOf(Object o)
- 返回此列表中指定元素的第一个出现的索引，如果此列表不包含元素返回- 1。
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i] == null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}8.isEmpty()
- 如果此列表不包含元素返回true。
public boolean isEmpty() {
return size == 0;
}9.lastIndexOf(Object o)
- 返回此列表中指定元素的最后一个发生的索引，如果此列表不包含元素返回- 1。
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size - 1; i >= 0; i--)
if (elementData[i] == null)
return i;
} else {
for (int i = size - 1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}10.remove(int index)
- 移除此列表中指定位置的元素
public E remove(int index) {
//检查index是否越界
rangeCheck(index);
//修改 +1
modCount++;
//获取旧值
E oldValue = elementData(index);
//计算index之后需要移动的元素，index是从0开始的
int numMoved = size - index - 1;
if (numMoved > 0)
//将index之后的元素前移1位
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}11.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;
}private void fastRemove(int index) {
modCount++;
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
}12.removeAll(Collection c)
- 从这个列表中移除包含在指定集合中的所有元素。
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}private boolean batchRemove(Collection<?> c, boolean complement) {
//complement = false
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
//删除时：
//循环判断集合中是否包含传入的要删除的元素
//循环完成后：原集合排除要删除的集合元素后放入elementData
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
//删除时：
//如果原集合包含要删除的元素，size在for循环之后减少 r：原有效元素的数量
//将原有效元素的数量r、（size - r）现有效元素数量-原有效元素的数量 负数
if (r != size) {
//重新赋值到elementData、填补缺失
System.arraycopy(elementData, r, elementData, w, size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}13.removeIf(Predicate filter)
- 删除满足给定谓词的这个集合的所有元素。
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
//使用了BitSet用来记录被删除的元素的下标
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
//这个循环把符合条件的待删除的元素的下标设置到BitSet中，即BitSet中对应的下标设为true
for (int i = 0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked") final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
//检测是否有其他线程并发修改这个ArrayList
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
//将剩余的生存元素移到已删除元素剩余的空间上
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i = 0, j = 0; (i < size) && (j < newSize); i++, j++) {
//nextClearBit返回第一个位出现或之后指定的起始索引被设置为false的索引。
//将不需要被删除的值从下标为0开始进行覆盖
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k = newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}14.replaceAll(UnaryOperator operator)
- 用将运算符应用到该元素的结果替换此列表中的每个元素。
list.replaceAll(e -> e * 2);public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i = 0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}15.retainAll(Collection c)
- 仅保留包含在指定集合中的列表中的元素。
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}private boolean batchRemove(Collection<?> c, boolean complement) {
//complement = false / true
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
//删除时：
//循环判断集合中是否包含传入的要删除的元素
//循环完成后：原集合排除要删除的集合元素后放入elementData
//保留时：
//循环判断集合中是否包含传入的要保留的元素
//循环完成后：将要保留的元素放入elementData
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
//如果原集合包含要删除或保留的元素，size在for循环之后减少 r：原有效元素的数量
//将原有效元素的数量r、（size - r）现有效元素数量-原有效元素的数量 负数
if (r != size) {
//重新赋值到elementData、填补缺失
System.arraycopy(elementData, r, elementData, w, size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}16.set(int index, E element)
- 用指定元素替换此列表中指定位置的元素。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}17.size()
- 返回此列表中有效元素的数目。
public int size() {
return size;
}18.sort(Comparator c)
- 分类列表使用提供的
Comparator比较元素
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}19.toArray()
- 返回一个数组，包含在这个列表中的所有元素在适当的顺序（从第一个到最后一个元素）。
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}20.toArray(T[] a)
- 返回一个数组，包含在这个列表中的所有元素在适当的顺序（从第一到最后一个元素）；返回数组的运行时类型是指定的数组的运行时类型。
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}21.trimToSize()
- 装饰这 ArrayList实例是列表的当前容量。
public void trimToSize() {
//将elementData的数组设置为ArrayList实际的容量，动态增长的多余容量被删除了。
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}4.2 LinkedList
ArrayList 是一个动态数组，而 LinkedList 是一个双向链表。双向链表实现，增删快，查询慢。类图：LinkedList
由于实现的方式不同，LinkedList 不能随机访问，但是可以使用for循环，虽然链表没有下标但是LinkedList维护一个数组存放下标。
在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。这样做的好处就是可以通过较低的代价在 List 中进行插入和删除操作。
线性表与链表的区别和优劣
-顺序表
-从栈中开辟一片连续的存储单元对数据进行存储，存储结构和数据逻辑相同；
-空间大小固定，管理方便，自由度小；
-通过下标获取元素，存储密度为1；
-查找元素快，平均时间复杂度为O(1)；
-增删元素慢，增删的平均时间复杂度为O(n)；
-链表
-从堆中动态开辟出的不连续存储单元，通过指针在计算机存储单元上对数据逻辑进行链接
-空间大小不固定，申请管理麻烦，自由度大；
-通过结构体next数据项中存储的指针寻找并获取元素；
-查找元素慢，查找平均时间复杂度为O(n)；
-增删元素快，增删的平均时间复杂度为O(1)；
综上，在查找操作频繁时候考虑采用顺序表，在增删操作频繁时候考虑采用链表。方法
- 添加 add
- 删除 remove
- 遍历
- for 链表没有角标，但是LinkedList造了,数组维护
- 增强for
- 迭代器
- 列表迭代器
- 判断
- isEmpty
- contains
- 同样equals默认比较的是地址，看需求是否重写
- 获取位置
- E get(int index)
- 下标从0开始
测试代码
public class LinkedListDemo1 {
//LinkedList源码分析:
//(1) LinkedList中包含三个属性 first第一个节点、last最后一个节点、size个数
//(2) LinkedList中每个元素都是Node类型，Node中有三个属性 item 存储数据，next下一个节点 prev前一个节点
//LinkedList:存储结构是双向链表。优点增删快，缺点查询慢
public static void main(String[] args) {
//创建集合
LinkedList list = new LinkedList();
//1.添加
list.add(new Student("1"));
list.add(new Student("2"));
list.add(new Student("3"));
list.add(new Student("4"));
System.out.println(list.toString());
//2.删除
list.remove("1");
//不能删除，需要重写equals()
//list.remove(new Student("1"));
System.out.println(list.toString());
//3.遍历
//for 链表没有角标，但是LinkedList造了,数组维护
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
//foreach
for (Object o : list) {
System.out.print(o.toString() + " ");
}
System.out.println();
//迭代器
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
//列表迭代器
ListIterator listIterator = list.listIterator();
while (listIterator.hasNext()) {
System.out.print(listIterator.next() + " ");
}
System.out.println();
while (listIterator.hasPrevious()) {
System.out.print(listIterator.previous() + " ");
}
//判断
System.out.println();
System.out.println(list.contains(new Student("3")));
System.out.println(list.isEmpty());
//获取位置
System.out.println(list.get(0));
}
}
class Student {
private String name;
public Student() {
}
public Student(String name) {
this.name = name;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Student student = (Student) o;
return Objects.equals(name, student.name);
}
}源码分析
常量
//有效元素的个数
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;
}
}1.无参构造方法
/**
* Constructs an empty list
*/
public LinkedList() {
}2.add(E 3.e)
public boolean add(E e) {
linkLast(e);
return true;
} //添加一个元素 ！！
void linkLast(E e) {
//开始first = last = null, l = null
final Node<E> l = last;
//创建一个新的结点newNode 前、元素、后
// Node(Node<E> prev, E element, Node<E> next)
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
}
3.remove(Object o)
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 {
//从添加我们就可以看到first始终指向第一个结点！！
for (Node<E> x = first; x != null; x = x.next) {
//比较规则看你有没有重写
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
} E unlink(Node<E> x) {
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;
}
//内存溢出：内存不够用 Memory Out
//内存泄露，分配的内存无法回收 Memory Leak
x.item = null;
return element;
}4.get(int index)
public E get(int index) {
return node(index).item;
} Node<E> node(int 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.listIterator(int index)
public ListIterator<E> listIterator(int index) {
return new ListItr(index);
} private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
}4.3 Vector
数组实现，查询快，增删慢、JDK1.0、运行效率慢，线程安全。
Vector vector = new Vector();
- vector.add("1");
- 遍历 4+1种(枚举器)
主要实现类为：Stack
public class VectorDemo {
public static void main(String[] args) {
//创建Vector (向量集合)：存储结构 数组
Vector vector=new Vector();
//1 添加元素
vector.add("北京");
vector.add("上海");
vector.add("南京");
//2遍历
//2.1for
//2.2增强for
//2.3迭代器
//2.4列表迭代器
//2.5枚举器
Enumeration en=vector.elements();
while(en.hasMoreElements()){
System.out.println(en.nextElement());
}
}
}4.4 Stack(栈)
Vector的子类，存储数组。Stack stack = new Stack();
- 是一种先进后出的数据结构
- Stack类，继承Vector类
- push进栈，pop出栈，peek栈顶元素
- LinkedList也实现了栈结构，LinkedList stack = new LinkedList<>(); 受限的集合
public class StackDemo {
public static void main(String[] args) {
//创建集合 受限制的集合
//1.Stack stack = new Stack();
//2.LinkedList实现了Stack功能
LinkedList<String> stack = new LinkedList<>();
//入栈 ->添加
stack.push("1");
stack.push("2");
stack.push("3");
System.out.println(stack.peek());
//出栈 ->删除
int size = stack.size();
//for (int i = 0; i < stack.size(); i++) 错误,会变
for (int i = 0; i < size; i++) {
System.out.println(stack.pop());
}
System.out.println("元素个数" + stack.size());
}
}补充Queue队列
- 是一种先进先出的数据结构
- Queue接口：继承Collection接口
- offer入队、poll出队，peek队头元素
- LinkedList实现Queue接口,Queue list = new LinkedList();
public class QueueDemo {
//Queue：先进先出的结构，受限的集合
public static void main(String[] args) {
Queue queue=new LinkedList();
//入队(添加)
queue.offer("北京");
queue.offer("上海");
queue.offer("广州");
System.out.println("peek:"+queue.peek());
System.out.println("peek:"+queue.peek());
//出队(删除)
int count=queue.size();
for(int i=0;i<count;i++){
System.out.println(queue.poll());
}
}
}5. Set接口
无序、无下标、元素不可重复。方法全部继承自Collection中的方法。
public class SetDemo1 {
public static void main(String[] args) {
//无序、无下标、不可重复
Set<String> set = new HashSet<>();
//1.添加
set.add("1");
set.add("2");
set.add("3");
System.out.println(set.toString());
//2.删除
set.remove("2");
System.out.println(set.toString());
//3.遍历 只能用增强for、迭代器
for (String s : set) {
System.out.print(s + " ");
}
System.out.println();
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
//4.判断
System.out.println(set.contains("2"));
System.out.println(set.isEmpty());
}
}5.1 HashSet
HashSet hashSet = new HashSet<>();
存储结构用哈希表：数组+链表 ； jdk1.8之后 数组+链表+红黑树
方法：
- 1.添加
- hashSet.add(new Student("1"));
- System.out.println(hashSet.toString());
- 重写equals和hashCode方法保证元素不重复
- 2.删除
- hashSet.remove(new Student("3"));
- 若没重写equals与hashCode方法没法删除，实例化了一个新的对象，地址不同
- 3.遍历
- 增强for
- 迭代器
- 4.判断
- contains()
- hashSet.contains(new Student("3"))
- 若没重写equals与hashCode方法则不存在
- isEmpty()
- contains()
存储过程：
先根据hashCode()计算一个位置：
- 该位置没有元素，直接添加进来，引用类型存放的是地址
- 该位置有元素，先比较HashCode值(HashCode值不一样计算出来的位置可能一样)
- 如果hash值不一样，加进来形成链表
- 如果hash值一样，再比较equals()
- 为false，不一样。形成链表
- 为true,重复元素，丢弃
底层实现HashMap,有关源码看HashMap
public class HashSetDemo1 {
public static void main(String[] args) {
HashSet<Student> hashSet = new HashSet<>();
//1.添加
hashSet.add(new Student("1"));
hashSet.add(new Student("2"));
hashSet.add(new Student("3"));
hashSet.add(new Student("3"));
System.out.println(hashSet.toString());
//2.删除 若没重写equals与hashCode方法没法删除
//hashSet.remove(new Student("3"));
//3.遍历 增强for 、 迭代器
//4.判断 contains()、isEmpty()
//若没重写equals与hashCode方法不存在
//System.out.println(hashSet.contains(new Student("3")));
//System.out.println(hashSet.isEmpty());
}
}
class Student {
String name;
public Student() {
}
public Student(String name) {
this.name = name;
}
@Override
public boolean equals(Object o) {
System.out.println("比较了：" + this.toString() + "----" + o.toString());
if (o == null) {
return false;
}
if (this == o) {
return true;
}
if (o instanceof Student) {
Student student = (Student) o;
return this.name.equals(student.name);
}
return false;
}
@Override
public int hashCode() {
//根据名字计算hashCode
return name.hashCode();
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
'}';
}
}5.2 LinkedHashSet
哈希表(数组+链表+红黑树)，存储元素的插入顺序，保证有序
包含一个双向链表，保证顺序。
public class HashSetDemo1 {
public static void main(String[] args) {
HashSet<Student> hashSet = new LinkedHashSet<>();
hashSet.add(new Student("1"));
hashSet.add(new Student("2"));
hashSet.add(new Student("3"));
hashSet.add(new Student("4"));
System.out.println(hashSet.toString());
}
}
class Student {
String name;
public Student() {
}
public Student(String name) {
this.name = name;
}
@Override
public boolean equals(Object o) {
System.out.println("比较了：" + this.toString() + "----" + o.toString());
if (o == null) {
return false;
}
if (this == o) {
return true;
}
if (o instanceof Student) {
Student student = (Student) o;
return this.name.equals(student.name);
}
return false;
}
@Override
public int hashCode() {
//根据名字计算hashCode
return name.hashCode();
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
'}';
}
}5.3 TreeSet
红黑树(自平衡的二叉搜索树)
- 基于排序实现元素的不重复
- 左孩子比根结点小，右孩子比根结点大
实现SortedSet接口，对元素自动排序
对象元素添加要求,定义排序规则
- 1.元素对象必须实现Comparable接口
- 定制比较
- 通过compareTo方法确定是否为重复元素
compareTo str1.compareTo(str2);
如果参数字符串等于此字符串，则返回值 0；
如果此字符串小于字符串参数，则返回一个小于 0 的值；
如果此字符串大于字符串参数，则返回一个大于 0 的值。
- 2.提供比较器Comparator
- 匿名内部类 new Comparator
- 自然比较
- 自然比较优先级高于定制比较
方法：
- 1.添加
- TreeSet list = new TreeSet<>();
- list.add(new Student("1"));
- 2.删除
- 看比较规则能不能删除
- 3.遍历
- 增强for
- 迭代器
- 4.判断
- contains()
- isEmpty()
/**
* @author GoodTime0313
* @version 1.0
* @Description TreeSet 存储结构：红黑树
* @date 2021/3/19 9:44
*/
public class Demo1 {
public static void main(String[] args) {
TreeSet<String> treeSet = new TreeSet<>();
//1.添加
treeSet.add("1");
treeSet.add("2");
treeSet.add("3");
System.out.println(treeSet.toString());
//2.删除
treeSet.remove("3");
System.out.println(treeSet.toString());
//3.遍历 增强for 迭代器
for (String s : treeSet) {
System.out.print(s + " ");
}
Iterator<String> iterator = treeSet.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
//4.判断
System.out.println(treeSet.contains("1"));
System.out.println(treeSet.isEmpty());
}
}public class Demo2 {
public static void main(String[] args) {
//比较规则
//1.对象实现Comparable接口
//2.提供比较器
//比较器的优先级高于元素的自然排序
//TreeSet<Student> list = new TreeSet<>();
TreeSet<Student> list = new TreeSet<>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o1.getName().compareTo(o2.getName());
}
});
//添加
list.add(new Student("1"));
list.add(new Student("2"));
list.add(new Student("3"));
list.add(new Student("4"));
System.out.println(list.toString());
//删除 看比较规则能不能删除
//遍历 增强for 迭代器
//判断
}
}
class Student implements Comparable<Student> {
private String name;
public Student() {
}
public Student(String name) {
this.name = name;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
'}';
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
/* compareTo str1.compareTo(str2);
如果参数字符串等于此字符串，则返回值 0；
如果此字符串小于字符串参数，则返回一个小于 0 的值；
如果此字符串大于字符串参数，则返回一个大于 0 的值。*/
@Override
public int compareTo(Student o) {
return this.name.compareTo(o.name);
}
}6. Map接口
HashMap map = new HashMap<>();
特点:
- 存储键值对(Key-Value)
- 键，不可以重复
- 值，可以重复
- 无序，无下标
方法：
- 1.添加
- map.put("cn", "中国");
- 如果集合中已经存在键，用新的value替换旧的value,返回旧值
- 2.删除
- map.remove("usa");
- 3.清空
- map.clear();
- 4.遍历
- 4.1 entrySet
- 返回时所有的映射对的Set集合 效率高
- 内部接口 Entry 一个 entry对应一个映射对
- Set> set = map.entrySet();
- 4.2 keySet
- 所有的键的Set集合
- 4.1 entrySet
Set<String> keySet = map.keySet();
for (String s : keySet) {
System.out.println(s + " " + map.get(s));
}- 输出
- 迭代器
- 增强for
for (Map.Entry<String, String> entry : set) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
简化：for (Map.Entry<String, String> entry : map.entrySet()) - 5.判断
System.out.println(map.containsValue("中国"));
System.out.println(map.containsKey("cn"));
System.out.println(map.isEmpty());public class MapDemo {
//特点：（1）存储键值对, 键不能重复，值可以重复 （2）无序，无下标
public static void main(String[] args) {
//创建集合
Map<String,String> map=new HashMap<>();
//1添加元素
System.out.println(map.put("cn", "中国"));
System.out.println(map.put("uk", "英国"));
System.out.println(map.put("usa", "美国"));
System.out.println(map.put("kor", "中国"));
System.out.println(map.put("tha", "泰国"));
//如果集合中已经存在键，用新的value替换掉旧的value.返回旧的value
System.out.println(map.put("usa", "美利坚共和国"));
System.out.println(map.size());
System.out.println(map.toString());
//2删除
//2.1删除一个元素
// map.remove("tha");
// System.out.println(map.toString());
//2.2清空
// map.clear();
//3遍历（重点）
//3.1使用entrySet方法，返回是所有的映射对的Set集合 （entrySet效率高于keySet）
//一个Entry就对应一个映射对
System.out.println("---------entrySet方法---------");
Set<Map.Entry<String,String>> entries=map.entrySet();
for (Map.Entry<String, String> entry : entries) {
System.out.println(entry.getKey()+"====="+entry.getValue());
}
//3.2使用keySet方法，返回是所有的键的Set集合
System.out.println("---------使用keySet方法---------");
Set<String> keySet=map.keySet();
for (String key : keySet) {
System.out.println(key+"...."+map.get(key));
}
//4判断
System.out.println(map.containsKey("usa"));
System.out.println(map.containsValue("泰国"));
}
}
6.1 HashMap
JDK1.2，线程不安全，运行效率快
存储结构：哈希表(数组+链表 )，JDK1.8之后还有红黑树
HashMap hashMap = new HashMap<>();
存储过程：
- 先根据Key计算hash值,再计算位置
- 该位置没有元素，直接添加进来，引用类型存放的是地址
- 该位置有元素，先比较hash值(hash值不一样计算出来的位置可能一样)
- 如果hash值不一样，加进来形成链表
- 如果hash值一样，再比较equals()
- 为false，不一样。形成链表
- 为true,重复元素，丢弃
方法
- 1.添加
- hashMap.put(new Student("刘志1", 20), 20);
//没有重写equals和hashCode方法则可以添加
hashMap.put(new Student("刘志1", 40), 40);- 2.删除
- hashMap.remove("刘志1");
- 3.清空
- 4.遍历
- entrySet
- keySet
- 5.判断
public class HashMapDemo {
public static void main(String[] args) {
//存储结构: 哈希表(数组+链表+红黑树);
HashMap<Student,String> students=new HashMap<>();
//LinkedHashMap students=new LinkedHashMap();
Student s1=new Student("周瑜", 20);
Student s2=new Student("刘备", 18);
Student s3=new Student("曹操", 22);
//1添加元素
students.put(s1, "北京");
students.put(s2, "上海");
students.put(s3,"上海");
students.put(new Student("曹操", 22) ,"杭州");
System.out.println("元素个数:"+students.size());
System.out.println(students.toString());
//2删除
// students.remove(new Student("曹操", 22));
// System.out.println(students.toString());
//3遍历
//3.1 使用entrySet
Set<Map.Entry<Student,String>> entries=students.entrySet();
for (Map.Entry<Student, String> entry : entries) {
System.out.println(entry.getKey()+"............."+entry.getValue());
}
System.out.println("------------");
//3.1 使用keySet
Set<Student> keySet=students.keySet();
for (Student s : keySet) {
System.out.println(s+"............."+students.get(s));
}
//4判断
System.out.println(students.containsKey(new Student("曹操", 22)));
System.out.println(students.containsValue("杭州"));
}
}HashMap的源码分析
- 1 调用HashMap的无参构造方法，加载因子loadFactor赋值0.75，table数组是空。
- 2 当添加第一个元素时，创建长度16的数组，threshold=12。
- 当元素个数大于阈值（16*0.75=12）时候，会进行扩容，扩容后大小为原来的2倍。目的是减少调整元素的个数
- 3 JDK1.8当每个链表长度大于8，并且数组元素个数大于等于64时候，会调整为红黑树，目的是提高效率
- 4 JDK1.8当链表长度小于等于6时，调整成链表
- 5. JDK１.８以前，链表是头插入，JDK1.8以后是尾插入
结点
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
//单向链表
Node<K, V> next;
//省略不影响理解的代码
}定义的常量
//默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//红黑树的阈值 当链表的长度大于8时调整成红黑树
static final int TREEIFY_THRESHOLD = 8;
//当链表的长度小于6时调整会链表
static final int UNTREEIFY_THRESHOLD = 6;
//数组的最小值为64，满足这个和链表长度大于8且数组长度大于64时才会调整
static final int MIN_TREEIFY_CAPACITY = 64;
//初始为空，节省空间
transient Node<K, V>[] table;
// The number of key-value mappings contained in this map.
transient int size;
//阈值 12 16*0.75
int threshold;
final float loadFactor;1.无参构造方法
public HashMap() {
//加载因子的赋值 0.75 容器到达百分之75的时候进行扩容
//为什么是0.75 大的话散列冲突比较高 小的话浪费空间
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}2.put(K , V )
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} static final int hash(Object key) {
int h;
//原哈希值异或无符号右移16为的原哈希值 前16位不变后16位进行异或
//好处:减少hash碰撞，散列更加均匀，提高效率
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//在HashMap里面存储的元素是Node 创建了一个数组
Node<K, V>[] tab;
//单结点
Node<K, V> p;
int n, i;
//table初始为空
if ((tab = table) == null || (n = tab.length) == 0)
//resize():创建一个数组，返回长度16的数组
n = (tab = resize()).length;
//(n - 1) & hash 取低四位 0-15 对应数组的角标范围 数组的长度16
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K, V> e;
K k;
//数组位置上有元素，比较hash值，
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);
//如果binCount大于等于7，数组中有8个元素，再加第九个元素时把链表调整成树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//在添加链表时哈希值可能一样，equals一样，就是重复元素
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;
//13(当添加了12个元素+1) > 12
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} final Node<K, V>[] resize() {
Node<K, V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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
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;
}6.2 LinkedHashMap
有顺序的HashMap，继承了HashMap
哈希表(数组+链表+红黑树) 内有双链表
6.3 TreeMap
实现SortedMap接口（Map的接口），可以对key 自动排序，Key需实现Comparable接口
不允许插入为Null的key，可以插入值为Null的Value
存储结构红黑树
public class TreeMapDemo {
public static void main(String[] args) {
TreeMap<Student2, Integer> treeMap = new TreeMap<>(new Comparator<Student2>() {
@Override
public int compare(Student2 o1, Student2 o2) {
return o1.getAge()-o2.getAge();
}
});
treeMap.put(new Student2("刘志1", 20), 20);
treeMap.put(new Student2("刘志2", 40), 40);
System.out.println(treeMap.size());
System.out.println(treeMap.toString());
// ----------------------------
//遍历
//entrySet
Set<Map.Entry<Student2, Integer>> entrySet = treeMap.entrySet();
for (Map.Entry<Student2, Integer> entry : entrySet) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println();
//keySet
Set<Student2> keySet = treeMap.keySet();
for (Student2 student2 : keySet) {
System.out.println(student2.toString() + " "+ treeMap.get(student2));
}
System.out.println(treeMap.containsKey(new Student2("刘志1", 20)));
System.out.println(treeMap.containsValue(20));
}
}
class Student2 {
private String name;
private int age;
public Student2() {
}
public Student2(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 boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
Student2 student = (Student2) o;
return age == student.age && Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(name, age);
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
'}';
}
}6.4 Hashtable
JDK1.0版本，线程安全，运行效率慢；不允许null作为key或者vlaue
6.5 Properties
Hashtable 的子类，要求Key 和value 都是String ，通常用于配置文件的读取
- 属性名和属性值都是字符串
- 没有泛型
- 和流有关
方法：
- Properties properties = new Properties();
- properties.setProperty("name", "灿灿");
- 遍历
- entrySet
- keySet
- stringPropertyNames
Set<String> strings = properties.stringPropertyNames();
for (String s : strings) {
System.out.println(s + " " + properties.getProperty(s));
}public class PropertiesDemo {
public static void main(String[] args) {
//创建Properties属性集合
// 1属性名和属性值都是字符串
// 2没有泛型
// 3和流有关
Properties properties=new Properties();
//添加元素
properties.setProperty("name", "灿灿");
properties.setProperty("age", "20");
properties.setProperty("address", "徐州");
System.out.println(properties.toString());
//遍历
//1 entrySet
//2 keySet
//3 stringPropertyNames 获取所有的属性名
Set<String> pros= properties.stringPropertyNames();
for (String pro : pros) {
System.out.println(pro+":"+properties.getProperty(pro));
}
}
}7.Collections工具类
- 排序 sort
- 二分查找 binarySearch
- 复制 copy 有bug，目标集合的size的大小必须要大于等于源的size，赋默认值
- 返回元素出现的次数 frequency
- 随机打乱集合 shuffle
public class CollectionsDemo {
public static void main(String[] args) {
//Collections工具类的使用
//(1)sort();排序
System.out.println("-------sort-------");
List<Integer> list=new ArrayList<>();
list.add(20);
list.add(12);
list.add(9);
list.add(26);
list.add(30);
Collections.sort(list);
System.out.println(list.toString());
//(2)binarySearch();二分查找
System.out.println("-------binarySearch();------");
int pos= Collections.binarySearch(list, 20);
System.out.println(pos);
//(3)copy复制(目标集合的size必须要大于或等于源集合的size)
System.out.println("------copy--------");
List<Integer> list2=new ArrayList<>();//size=0
for (int i = 0; i < list.size(); i++) {
list2.add(0);
}
Collections.copy(list2, list);
System.out.println(list2.toString());
//(4)frequency 返回元素出现的次数
System.out.println("------frequency-----");
System.out.println(Collections.frequency(list, 20));
//(5)shuffle(List<?> list) 随机打乱集合元素
Collections.shuffle(list);
System.out.println("------shuffle-----");
System.out.println(list.toString());
//数组和集合的转换
//数组转成集合
System.out.println("------数组转成集合-----");
String[] arr={"beijing","shanghai","hangzhou"};
//受限的集合（不能添加和删除）
List<String> list3=Arrays.asList(arr);
//list3.remove("beijing");
System.out.println(list3.toString());
System.out.println("------集合转成数组-----");
//如果长度小于等于集合的长度，返回数组长度和集合长度一样
//如果长度大于集合的长度，返回的数组的长度和设置长度一样
Integer[] integers = list.toArray(new Integer[10]);
System.out.println(Arrays.toString(integers));
}
}[/wppay]