java基础之集合概览

2023-11-27  本文已影响0人  墨线宝

有时候需要存储一组数据,之前使用数组,但是数组具有固定的容量,但是在写程序时并不知道需要多少对象,在java.util包下提供了一套完整的集合类,包含List、Set、Queue、Map。java集合类都可以自动地调整自己的大小。

在创建集合时,经常使用泛型,可以在编译期防止将错误的类型放入到集合中。

集合概念

集合分为两个基本接口

List

存储有序,可以重复的元素,相当于动态数组
集合中元素所在类要重写equals方法

两种类型的list

List特性

ArrayList和Vector的异同点

相同点

不同点

LinkedList链表

LinkedList添加了一些方法,使其可以被用作栈,队列和双向队列,方法差异

ArrayList和LinkedList的区别

迭代器Iterators

Iterator

Iterator接口提供了遍历任何Collection的接口,取代了java集合框架中的Enumeration,迭代器允许调用者在迭代过程中移除数据

iterator只能单向移动

Enumeration和iterator的区别

ListIterator

堆栈stack

堆栈是后进先出(LIFO),最后压入(push)栈的元素,第一个被弹出(pop)栈。

java1.0中有一个stack类,但是设计的不好,Java6添加了ArrayDeque,其中包含了直接实现堆栈功能的方法

Set

Set不保存重复的元素。查找是Set最重要的操作,选择HashSet实现,针对快速查找进行了优化。

存储无序,不可重复
添加Set集合中的元素所在类要重写equals和hashCode方法

无序性:指的是元素在底层存储的位置是无序的

Map

键值
key不可重复,一个key-value组成一个entry

map的分类

HashMap专为快速访问而设计,TreeMap保持键始终处于排序状态,没有HashMap快。LinkedHashMap按插入顺序保存其元素,但使用散列提供快速访问的能力。

HashMap工作情况

HashMap在Map.Entry静态内部类实现存储键值对,HashMap使用哈希算法,在put和get方法中,使用hashCode和equals方法,使用put方法时,使用key的hashcode和哈希算法来找出存储键值对的索引,Entry存储在LinkedList中,如果存在entry,使用equals检查传递的key是否存在,如果存在,会覆盖掉value,如果不存在,会创建一个新的entry然后保存。get的时候也是先通过hashcode找到数组中的索引,然后使用equals找到正确的Entry,在进行取值

HashMap默认初始容量是32,负载因子是0.75,阈值是容量乘以负载因子,当map的大小比阈值大时,HashMap会对map的内容进行重新哈希。

HashMap和HashTable的区别

队列

队列操作

队列是一个先进先出(FIFO)集合,LinkedList实现了Queue接口,并且提供了一些方法支持队列行为

PriorityQueue优先级队列

优先级队列声明下一个弹出的元素是最需要的元素。

BlockingQueue队列

是concurrent包下的类,在进行检索或移除一个元素的时候,会等待队列变成非空;当添加一个元素的时候,会等待队列中的可用空间。主要用于实现生产者-消费者模式

Collections工具类

unmodifiableCollection方法

Collections.unmodifiableCollection(list);Collections.unmodifiableList(list);使用该方法会创建一个只读集合,所有改变集合的操作都会抛出UnsupportedOperationException

public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c) {
        return new UnmodifiableCollection<>(c);
}

synchronizedCollection方法

Collections.synchronizedCollection(list)方法可以创建一个线程安全的集合

public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
    return new SynchronizedCollection<>(c);
}

问题

1、遍历时移除List中的元素

使用forEach和Iterator

在使用forEach遍历时,实际上是使用的Iterator,使用的核心方法是hasNext()和next(),但是使用的是list.remove,来看个例子

//源码
public class TestList {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("J");
        list.add("A");
        list.add("V");
        list.add("A");
        for (String s: list) {
            list.remove(s);
        }
    }
}

//编译之后
public class TestList {
    public TestList() {
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList();
        list.add("J");
        list.add("A");
        list.add("V");
        list.add("A");
        Iterator var2 = list.iterator();
        while(var2.hasNext()) {
            String s = (String)var2.next();
            list.remove(s);
        }
    }
}  

之前说过,Iterator在遍历时,不允许其他线程对该集合进行操作,看一下ArrayList的iterator是怎么实现的

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];
}

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

在每次获取下一个元素时,都会比较modCount 和 expectedModCount

然后在调用的list的remove方法会导致modCount增加(modCount表示被修改次数)

public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

此时iterator的next方法中两个变量就不一致了,就会抛出ConcurrentModificationException异常

再看一下如果使用iterator的remove方法

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

iterator在remove之后会将modCount的值赋给expectedModCount,就不会出现两个变量不等的情况了

不使用forEach遍历

使用普通for循环,有两种方式,第一种是使用正序遍历,但是进行remove操作之后要把遍历的索引进行修正减一,否则在移除下一个的时候就会出错,第二种就是使用倒序遍历

// 正序遍历
for (int i = 0; i < list.size(); i++) {
    String s = list.remove(i);
    i = i - 1;
    System.out.println(s);
}

//倒序遍历
for (int i = list.size() - 1; i >= 0; i--) {
    String s = list.remove(i);
    System.out.println(s);
}

2、fail-fast和fail-safe

java.util包中集合类被设计为fail-fast的,而java.util.concurrent中集合为fail-safe的。fail-fast迭代器抛出ConcurrentModificationException,而fail-safe迭代器从不抛出ConcurrentModificationException,Iterator的安全失败是基于对底层集合做拷贝,不受源集合上修改的影响

fail-fast

fail-fast迭代器抛出ConcurrentModificationException,通过modCount来进行实现,在进行迭代时,每次对于元素的修改都会修改该值,一旦该值被修改了,就会抛出异常

// 当Itr被实例化的时候,记录一下迭代器被实例化时ArrayList的修改次数(在用ArrayList进行add/remove操作时modCount每次都加一)
int expectedModCount = modCount;

// 检查是否被修改了
    final void checkForComodification() {
          // 当修改次数与Itr被实例化时的修改次数不一致时,说明在进行迭代操作的时候其他线程进行了ArrrayList的add/remove操作,此时抛出ConcurrentModificationException,即为fast-fail快速失败机制
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

3、Arrays.asList

这个方法返回的是一个ArrayList,不过这个ArrayList是Arrays类的内部类,在调用add方法的时候会直接报错

UnsupportedOperationException这是运行时异常

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

https://zhhll.icu/2020/java基础/集合/1.java基础之集合/

本文由mdnice多平台发布

上一篇下一篇

猜你喜欢

热点阅读