Java集合学习笔记
Java集合学习笔记
文章目录
1.集合简述
1.1集合基本概念
集合本身就是容器，用于存储元素（实际上存储的是引用）。不同的集合实体类的底层数据结构是不一样的，如ArrayList的底层数据结构是数组，LinkedList的底层数据结构是双向链表，HashMap的底层数据结构是哈希表。常见的集合接口是Collection和Map。两者明显的区别在于，前者存储的值是单一的，可以遍历，后者存储的值是键值对的方式，不可遍历。如下图：
这里需要再次强调的是，不同的集合底层依赖的数据结构是不一样的，也就是说元素的组织方式不一样，要根据具体的情况，选择适当的集合。（PS：加强数据结构的学习和复习）
1.2主要集合继承图谱
Collection
Map
2.Collection
2.0引言
Collection接口继承了Iterable接口，该接口保证了Collection任意的实现类都拥有一种能力–可迭代（遍历），最明显的体现就是 foreach 循环可以实现Collection的任意实现类的遍历。
List<String> arr = new ArrayList<>();
arr.add("1");
arr.add("2");
arr.add("3");
for(String s:arr){
System.out.println(s);
}
结果
1
2
3
事实上，foreach循环适用于数组以及任何实现了Iterable接口的类，以ArrayList为例，上面的foreach循环等价于
Iterator<String> iterator = arr.iterator();
while (iterator.hasNext()){
String s = iterator.next();
System.out.println(s);
}
其中hasNext()和next()都是接口Iterator的重要方法，下面讲述Iterable和Iterator接口。
2.1Iterable和Iterator
Iterable的字面意思是可迭代的，可遍历的，表示一种能力，任何集合如果想能被遍历，那么就必须实现这个接口。
public interface Iterable<T> {
// main method
Iterator<T> iterator();
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
而里面核心的方法 Iterator<T> iterator();必须被实现。该方法会返回一个Iterator，即迭代器，所以如果要让自定义的集合能被遍历，除了重写Iterable接口以外，还需要重写Iterator接口。
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
Iterator迭代器接口可以按照下面的图理解
-
hasNext方法用于查看该集合是否还有剩余元素，如果有就返回true，没有就返回false。
-
next方法指向下一个元素，并返回上一个元素。这个方法唯一的问题就是可能并没有下一个元素，当并没有下一个元素时，该方法将抛出
NoSuchElementException.所以为了保证每一次next都没有问题，那么应该预先用hasNext（）方法判断是否有剩余元素。 -
remove用于删除上一个元素，这个方法依赖于next方法，调用一次next方法后，才能使用remove方法，否则就会抛出
IllegalStateException。因为最开始并不存在上一个元素，所以必须调用next方法，其次当调用一次remove方法后，上一个元素已经被删掉了，不存在上一个元素，所以必须调用next方法。 -
还需注意的是，获取迭代器之后，如果修改集合的结构（比如添加元素，删除元素等,当然除了迭代器的remove方法除外），然后再使用迭代器遍历，则会出现
java.util.ConcurrentModificationExceptionList<String> arr = new ArrayList<>(); arr.add("1"); arr.add("2"); arr.add("3"); Iterator<String> iterator = arr.iterator(); // arr.remove(2); wrong code // arr.add("4"); wrong code while (iterator.hasNext()){ System.out.println(iterator.next()); }这也是为什么不能在foreach循环中轻易修改集合结构的原因。
2.2自定义ArrayList
自己定义可遍历的集合的话，比如自定义ArrayList，必须实现Iterable接口和需要一个Iterator的实现类。这里需要知道的是上面提到三个异常``NoSuchElementException,IllegalStateException,ConcurrentModificationException`都是非受检异常，你自己处理不处理其实无所谓，为了规范还是自己处理一下。
下面的代码仿照ArrayList来写的，主要方法如下所示
MyArrayList
package com.lordbao.iterator.MyArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.function.Consumer;
/**
* @Author Lord_Bao
* @Date 2020/9/3 8:40
* @Version 1.0
*/
public class MyArrayList<T> implements Iterable<T> {
//表示数组的元素个数 也代表下一个默认待插入的位置的下标
private int size;
//默认容量为10
private static final int DEFAULT_CAPACITY = 10;
//空数组，无参构造函数调用，或是初始化容量为0时，将是下面这个数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//MyArrayList 的 底层数据结构 数组
private Object[] elementData;
public MyArrayList() {
elementData = EMPTY_ELEMENTDATA;
}
public MyArrayList(int initialCapacity) {
if (initialCapacity == 0) elementData = EMPTY_ELEMENTDATA;
else if (initialCapacity > 0) elementData = new Object[initialCapacity];
else
throw new IllegalArgumentException("InitialCapacity " + initialCapacity + " can't be below 0");
}
public boolean add(T t) {
return add(size, t);
}
public boolean add(int index, T t) {
addIndexCheck(index);
ensureCapacity();
//刚好在size处插入元素 也满足
for (int j = size - 1; j >= index; j--) {
elementData[j + 1] = elementData[j];
}
elementData[index] = t;
size++;
return true;
}
public T getLast() {
return get(size - 1);
}
public T get(int index) {
getOrRemoveIndexCheck(index);
return (T) elementData[index];
}
public T remove(int index) {
getOrRemoveIndexCheck(index);
T result = (T) elementData[index];
for (int i = index + 1; i <= size - 1; i++) {
elementData[i - 1] = elementData[i];
}
elementData[size - 1] = null;
size--;
return result;
}
public T removeLast() {
return remove(size - 1);
}
public boolean isEmpty(){
return size==0;
}
public int size(){
return size;
}
private void getOrRemoveIndexCheck(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("Index " + index + " out of bounds");
}
private void addIndexCheck(int index) {
if (index < 0 || index > size)
throw new IllegalArgumentException("Index " + index + " out of bounds");
}
private void ensureCapacity() {
//如果是空数组,就扩容
if (elementData == EMPTY_ELEMENTDATA) {
elementData = new Object[DEFAULT_CAPACITY];
} else {
//检查容量是否充足
ensureCapacity(size);
}
}
private void ensureCapacity(int size) {
//如果数组存储的元素达到数组容量则进行扩容
if (size >= elementData.length)
expandCapacity();
}
private void expandCapacity() {
//扩容2倍
int newCapacity = elementData.length << 2;
elementData = Arrays.copyOf(elementData, newCapacity);
}
@Override
public Iterator<T> iterator() {
return new Itr();
}
private class Itr implements Iterator<T> {
int pointer;
int lastRet=-1;//上一个被返回的元素坐标，如果没有就是-1
@Override
public boolean hasNext() {
return pointer < size;
}
@Override
public T next() {
if (pointer>=size)
throw new NoSuchElementException();
//记录最近一次返回的元素坐标
lastRet = pointer;
return (T) elementData[pointer++];
}
@Override
public void remove() {
if (lastRet <0)
throw new IllegalStateException();
MyArrayList.this.remove(lastRet);
pointer = lastRet; //这样的目的是下一次next以后，pointer仍然指向正确
lastRet = -1;//一次删除之后，必须next，这样才能修改lastRet来继续删除下一个元素
}
@Override
public void forEachRemaining(Consumer<? super T> action) {
//暂时不写
}
}
}
测试代码
package com.lordbao.iterator.MyArrayList;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* @Author Lord_Bao
* @Date 2020/9/3 8:41
* @Version 1.0
*/
public class Main {
public static void main(String[] args) {
MyArrayList<String> arr = new MyArrayList<>(1);
arr.add("h");
arr.add("i");
Iterator<String> iterator = arr.iterator();
while (iterator.hasNext()) {
String next = iterator.next();
System.out.println(next);
}
//增强for循环 等价于上面的while
for (String s : arr) {
System.out.println(s);
}
}
}
结果
h
i
h
i
2.3Collection常见方法
测试上面部分方法
package com.lordbao.collection;
/**
* @Author Lord_Bao
* @Date 2020/9/1 10:50
* @Version 1.0
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.Objects;
/**
* 用于测试Collection接口常见的方法
*
* boolean add(E e)
* boolean remove(Object o)
* boolean contains(Object o)
* void clear()
* int size()
* boolean isEmpty()
* Object[] toArray()
* iterator<E> iterator()
*/
public class Main1 {
public static void main(String[] args) {
Collection<Man> arr = new ArrayList<>();
//add
arr.add(new Man("jack"));
arr.add(new Man("rose"));
arr.add(new Man("loki"));
arr.add(new Man("jenny"));
//remove 底层会调用equals
arr.remove(new Man("loki"));
//iterator
Iterator<Man> iterator = arr.iterator();
while (iterator.hasNext()){
Man man = iterator.next();
System.out.println(man);
}
//contains 底层会调用equals
System.out.println(arr.contains(new Man("jack")));
//toArray
Object[] objects = arr.toArray();
System.out.println(objects[0]);
//clear size isEmpty
arr.clear();
System.out.println(arr.size());
System.out.println(arr.isEmpty());
}
}
class Man{
private String name;
public Man() {
}
public Man(String name) {
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Man man = (Man) o;
return Objects.equals(name, man.name);
}
@Override
public String toString() {
return "Man{" +
"name='" + name + '\'' +
'}';
}
}
这里需要主要的是contains和remove底层会调用equals方法,怎么判断元素是否相等需要自己去拿捏。
测试结果
Man{name=‘jack’}
Man{name=‘rose’}
Man{name=‘jenny’}
true
Man{name=‘jack’}
0
true
2.4List
List继承自Collection，它的元素的最大特点是有序可重复，即存储的顺序和遍历的顺序是相同的，重复指的是相同的元素可以重复存储。
List最常见的实现类是ArrayList和LinkedList以及Vector。ArrayList和Vector的底层都是数组，前者不是线程安全的，后者是线程安全的，但是Vector效率比较低下，并且已经有新的方式保证线程安全，所以ArrayList应用更加广泛。
2.4.1List常见的方法
测试代码
package com.lordbao.list;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* @Author Lord_Bao
* @Date 2020/9/1 16:18
* @Version 1.0
*/
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
// add(int index , E e)
list.add(0,"world");
list.add(0,"the");
list.add(0,"hello");
//打印
list.forEach(System.out::println);
System.out.println("---------------------------------");
//set(int index,E e)
list.set(0,"hi");
list.forEach(System.out::println);
System.out.println("---------------------------------");
//E get(int index)
System.out.println(list.get(0));
// E remove(int index)
System.out.println(list.remove(0));
// indexOf lastIndexOf
System.out.println(list.indexOf("the"));
System.out.println(list.lastIndexOf("the"));
}
}
结果
hello
theworld
hi
theworld
hi
hi
0
0
2.4.2ArrayList
ArrayList的底层是数组，数组的特点就是随机访问快，增删效率较低（涉及移动大量元素），而且数组分配的空间是连续的，当数组大到一定程度的时候，就要考虑存储问题。
ArrayList的底层是数组，但元素增加的时候，就要考虑扩容问题，而扩容就会涉及移动元素，所以怎么扩容也是一个很重要的问题。
2.4.3LinkedList
LinkedList底层是双向链表，双向链表的特单是增删新的节点效率高，但是访问元素的效率就要低一点。在空间存储上，双向链表的节点不是连续的。
2.4.4Vector
Vector底层也是数组，它是线程安全的，但是效率比较低，事实上，可以通过Collections工具类，让ArrayList变得线程安全.List<String> list = Collections.synchronizedList(new LinkedList<>());。
2.5Set
Set没有特别的方法，这里不讲。
2.5.1HashSet
HashSet底层采用的是HashMap。参见HashMap
2.5.2TreeSet
TreeSet底层采用的是TreeMap。参见TreeMap
3.Map
Map以键值对的形式存储数据，它的键部分就是Set，无序不可重复。
3.1Map常见的方法
常见的方法测试如下
package com.lordbao.map;
import java.util.*;
/**
* @Author Lord_Bao
* @Date 2020/9/2 8:09
* @Version 1.0
*/
/**
* 测试常见的方法
*/
public class Main {
public static void main(String[] args) {
Map<Integer,String> map =new HashMap<>();
//存
map.put(1,"hello");
map.put(2,"jsjsis");
map.put(3,"the");
map.put(4,"world");
//取
System.out.println(map.get(1));
//删
System.out.println(map.remove(2));
//检查是否包含 key 和 value
System.out.println(map.containsKey(1));
System.out.println(map.containsValue("hello"));
//获得Key部分 并遍历
Set<Integer> integerSet = map.keySet();
for (Integer integer : integerSet) {
System.out.println(integer);
}
//获得values部分 并遍历
Collection<String> values = map.values();
for (String s:values){
System.out.println(s);
}
// k 和 v封装成一个集合
Set<Map.Entry<Integer, String>> set = map.entrySet();
for (Map.Entry<Integer,String> node:set){
System.out.println("key="+node.getKey()+",value="+node.getValue());
}
//清空 查看map元素个数 查看map是否为空
map.clear();
System.out.println(map.size());
System.out.println(map.isEmpty());
}
}
3.2HashMap
HashMap的底层数据结构是哈希表，哈希表是数组和链表的产物。下面重点说HashMap的两个方法
get（Object key） ，put（K key，V value）
为什么HashMap的Key是不可重复的呢？
因为每次调用put方法的时候，底层会调用Key的hashcode方法，然后计算出hash值，最后再通过哈希算法获得数组的下标，如果下标的元素是null，那么证明没有值存储，那么Key 和Value封装成头结点放在这个下标处。如果下标的元素不是null，那么就会遍历该下标下的链表，调用equals方法，如果都为false，则将Key 和Value封装成结点放在链表末尾，否则证明有重复Key存在，不执行put操作。
get方法的原理是类似的，计算出数组下标，如果下标处的元素为null，说明没有值，返回null，否则沿着链表一次调用Key的equals方法进行判断，如果都为false，则返回null。
综上所述，HashMap的不可重复的原因是底层调用了equals方法，保证Key不存在重复，而下标的计算实际是过滤了很多不满足条件的节点。
为什么说HashMap的Key是无序的呢？
其实存储Key的过程是比较复杂的，要经过运算，这个存储的过程是无序的，而取值是有一定顺序的，比如从每个数组元素的的链表进行遍历。存储无序，取值有序，就会照成存储值的时候是一种顺序，取值的时候是另一种顺序。
终上所述，如果要让HashMap发挥作用，那么Key部分就必须要合理重写equals和hashcode方法。
3.3Properties
Properties继承自HashTable，Hashtable的底层是哈希表，类似于ArrayList和Vector的关系，HashTable是线程安全的，而HashMap不是线程安全的，不过可以通过下面的方法，使得HashMap是线程安全的。
Map<String,String> map= new HashMap<>();
map = Collections.synchronizedMap(map);
Proerties的Key和Value都是存储String，该类常用来读取以键值对存储的配置文件。
3.4TreeMap
TreeMap的底层是二叉树，这部分数据结构不熟悉，有时间去学习和复习。TreeMap的Key部分是TreeSet，这个集合也是无序不可重复，不可重复的原因不清楚，猜测是进行了equals判断，无序是因为存储数据的时候依赖的是二叉树，取出数据的时候是大小有序的。
使用TreeMap，就需要保证Key部分实现了Comparable接口，或者是new TreeMap集合的时候，传入一个实现了Comparator接口的实现类。
下面以TreeSet为例，按照Worker工资由高到低，同工资按照姓氏升序进行排序。
package com.lordbao.map;
import java.util.*;
/**
* @Author Lord_Bao
* @Date 2020/9/2 14:06
* @Version 1.0
*/
public class TestTreeSet {
public static void main(String[] args) {
//方法1
Set<Worker> set = new TreeSet<>();
set.add(new Worker("Adams",1000));
set.add(new Worker("Athens",1000));
set.add(new Worker("Bob",1200));
for (Worker worker : set){
System.out.println(worker);
}
System.out.println("");
//方法2(可以使用Lambda表达式)
Set<Worker> set1 = new TreeSet<>(new Comparator<Worker>() {
@Override
public int compare(Worker o1, Worker o2) {
if (o1 == o2) return 0;
if (o1 == null) return -1;
if (o2==null) return 1;
if (o1.getSalary() == o2.getSalary()) return o1.getName().compareTo(o2.getName());
return o2.getSalary() -o1.getSalary();
}
});
set1.add(new Worker("Adams",1000));
set1.add(new Worker("Athens",1000));
set1.add(new Worker("Bob",1200));
for (Worker worker : set1){
System.out.println(worker);
}
}
}
class Worker implements Comparable<Worker>{
private String name="";
private int salary=0;
@Override
public String toString() {
return "Worker{" +
"name='" + name + '\'' +
", salary=" + salary +
'}';
}
public Worker() {
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getSalary() {
return salary;
}
public void setSalary(int salary) {
this.salary = salary;
}
public Worker(String name, int salary) {
this.name = name;
this.salary = salary;
}
//按照工资降序排列，工资相同，名字升序排列
@Override
public int compareTo(Worker o) {
if (o==null) return 1;
if (salary == o.salary) return name.compareTo(o.name);
return o.salary-salary;
}
}
结果
Worker{name=‘Bob’, salary=1200}
Worker{name=‘Adams’, salary=1000}
Worker{name=‘Athens’, salary=1000}Worker{name=‘Bob’, salary=1200}
Worker{name=‘Adams’, salary=1000}
Worker{name=‘Athens’, salary=1000}
4.总结
集合这一部分，大概分为Collection和Map，根据实际情况去选用合适的集合。这部分的数据结构有些不熟悉，有些熟悉的也模棱两可的，所以数据结构还需要加强。
上一篇： java学习笔记总结，持续更新中