【JavaSE】Java集合框架总结-Collection部分

文章目录

• 1.集合框架概述图(集合接口与实现分离的优势)
• 2.Iterator和Iterable的区别
• • (1)Iterable源码：
  • (2)Iterator源码：
  • (3)分析：
  • (4)为什么不是集合不直接实现iterator接口：
• 3.Iterator和子接口ListIterator
• • (1)Collection和List部分源码(如何获取迭代器)
  • (2)Iterator迭代器和其他类库中的迭代器在概念上区别
  • (3)子接口ListIterator函数功能(java core有详解)
• 4.迭代一个集合的三种方法
• 4.Collection接口
• 5.list系列
• • (1)list接口
  • (2)linkedList类
  • • a.双链表
    • b.Collection和ListIterator的两种add()方法
    • c.ListIterator的set()方法和索引函数
    • d.不同步的实现
    • e.linkedList的两种访问元素方式
    • • (1)正常利用迭代器迭代
      • (2)get方法(虚假的随机访问)
  • (3)ArrayList类
  • (4)Vector类
• 6.set系列
• • (1)set接口
  • (2)HashSet类
  • • a.介绍
    • b.函数功能
  • (3)linkedHashSet类
  • (4)TreeSet类
  • • a.介绍
    • b.和Hash的重要区别
• 7.Queue系列
• • (1)Queue接口
  • (2)Deque接口
  • (3)ArrayDeque类
  • (4)PriorityQueue类

1.集合框架概述图(集合接口与实现分离的优势)

2.Iterator和Iterable的区别 (1)Iterable源码：

package java.lang;

import java.util.Iterator;
import java.util.Objects;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;

public interface Iterable {

    Iterator iterator();

	default void forEach(Consumer action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

  	default Spliterator spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

(2)Iterator源码：

package java.util;

import java.util.function.Consumer;

public interface Iterator {
   
    boolean hasNext();

   	E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

   
    default void forEachRemaining(Consumer action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

(3)分析：

其实两个接口为依赖的关系，因为Iterator作为Iterable其中一个函数的返回值
1.Iterator是迭代器接口
2.Iterable两个功能
-----(1)只要实现该接口就可以使用foreach进行迭代
-----(2)封装了Iterator接口，只要实现了Iterable接口的类，就可以使用Iterator迭代器了

(4)为什么不是集合不直接实现iterator接口：

1.Iterator中核心的方法next()、hasnext()、remove()都是依赖当前位置
2.如果这些集合直接实现Iterator，则必须包括当前迭代位置的指针。当集合在方法间进行传递的时候，由于当前位置不可知，所以next()之后的值，也不可知
3.而实现Iterable则不然，每次调用都返回一个从头开始的迭代器，各个迭代器之间互不影响。

3.Iterator和子接口ListIterator (1)Collection和List部分源码(如何获取迭代器)

public interface Collection extends Iterable {
	Iterator iterator();
}

public interface List extends Collection {
	Iterator iterator();
	ListIterator listIterator();
    ListIterator listIterator(int index);
}

(2)Iterator迭代器和其他类库中的迭代器在概念上区别

(3)子接口ListIterator函数功能(java core有详解)

4.迭代一个集合的三种方法

1.直接返回迭代器，通过反复调用next()方法
2.for each
3.iterator.forEachRemaining()

4.Collection接口

集合层次结构中的根接口。 集合表示一组对象，称为其元素 。 有些集合允许重复元素而其他集合则不允许。 有些是订购的，有些是无序的。

5.list系列 (1)list接口

list元素有序，可重复，两种方式访问元素

public interface List extends Collection {
}

(2)linkedList类 a.双链表

双链表实现了List和Deque接口。 实现所有可选列表操作，并允许所有元素（包括null ）。
对于双向链表，所有操作都可以预期。 索引到列表中的操作将从开头或结尾遍历列表，以较接近指定索引为准。

public class linkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
{
	public ListIterator listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }
	
	public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    public E set(int index, E element) {
        checkElementIndex(index);
        Node x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    private static class Node {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

b.Collection和ListIterator的两种add()方法

1.第一种是LindkedList类从Collection继承下来的add()方法直接添加到链表尾部，但是常常需要将元素添加到链表中间，所以这个add()方法不是很实用
2.由于迭代器描述了集合中的位置，所以这种add就交给迭代器来做，LIstIterator只要是list的实现类都可以直接获取，并且这种add方法，n个元素有n+1个插入位置

c.ListIterator的set()方法和索引函数

d.不同步的实现

1.如果多个线程同时访问链表，并且至少有一个线程在结构上修改了列表，则必须在外部进行同步。 （结构修改是添加或删除一个或多个元素的任何操作;仅设置元素的值不是结构修改。
2.以下是java core中的内容，这还没详细介绍同步解决方案

e.linkedList的两种访问元素方式 (1)正常利用迭代器迭代 (2)get方法(虚假的随机访问)

上面源码中体现了get方法，这个方法看上去是随机访问，其实效率很低，每次都是遍历找元素

(3)ArrayList类

(4)Vector类

6.set系列 (1)set接口

set去重，判断两个元素使用equals，而不是==

public interface Set extends Collection {
	Iterator iterator();
}

(2)HashSet类 a.介绍

public class HashSet
    extends AbstractSet
    implements Set, Cloneable, java.io.Serializable
{
	static final long serialVersionUID = -5024744406713321676L;
	private transient HashMap map;
	private static final Object PRESENT = new Object();
	
	public Iterator iterator() {
        return map.keySet().iterator();
    }
}

b.函数功能

(3)linkedHashSet类

1.Hash表和Set接口的链表实现，具有可预测的迭代顺序。
2.此实现与HashSet不同之处在于它维护了一个贯穿其所有条目的双向链表。 此链接列表定义迭代排序，即元素插入集合（ 插入顺序 ） 的顺序
3.请注意，如果将元素重新插入到集合中，则不会影响插入顺序。 （如果s.add(e)在调用之前立即返回true则调用s.contains(e)将元素e重新插入到集s )

package java.util;

public class linkedHashSet
    extends HashSet
    implements Set, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

    public linkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

  
    public linkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    public linkedHashSet() {
        super(16, .75f, true);
    }

    public linkedHashSet(Collection c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

   
    @Override
    public Spliterator spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }
}

(4)TreeSet类 a.介绍

public class TreeSet extends AbstractSet
    implements NavigableSet, Cloneable, java.io.Serializable
{
}

b.和Hash的重要区别

1.有序集，红黑树实现
2.添加慢，比较查找快
3.散列只需要适当的打乱，而TreeSet需要具体定义比较两个对象的差异

7.Queue系列 (1)Queue接口

package java.util;

public interface Queue extends Collection {
    boolean add(E e);
	boolean offer(E e);
    E remove();
    E poll();
    E element();
    E peek();
}

(2)Deque接口

public interface Deque extends Queue {
}

(3)ArrayDeque类

public class ArrayDeque extends AbstractCollection
                           implements Deque, Cloneable, Serializable
{
}

(4)PriorityQueue类

public class PriorityQueue extends AbstractQueue
    implements java.io.Serializable {
	
}