容器框架学习

作者: 楚木巽 | 来源:发表于2021-09-01 13:33 被阅读0次

在JDK8中rt.jar文件中，java.util.*包中的容器主要包括List、Set、Queue和Map四大类，其中List、Set、Queue是和Collection接口相关的容器，而Map是单独列出来的容器。

类图.png

Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Element）。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类JavaSDK提供的类都是继承自Collection的子接口，如List和Set。
所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于构建一个空的Collection，有一个Collection的参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。
如何遍历Collection中的每一个元素？
- 不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个对象，使用该迭代对象即可逐一访问Collection中每一个元素。典型用法如下：

Iterator it = collection.iterator();//获得一个迭代对象
    while(it.hasNext()){
Object obj = it.next();//得到下一个对象
}

具体

Set集合
- Set集合是最简单的集合，集合中的对象不按照特定的方式排序。主要有：HashSet()和TreeSet().
HashSet
- HashSet类按照哈希算法来存取集合中的对象，具有很好的存取性能。当HashSet向集合中加入一个对象时，会调用对象的HashCode()方法获取哈希码，然后根据这个哈希码进一步计算出对象在集合中的存放位置。
TreeSet实现了SortedSet接口可以对集合中的元素排序。

List集合

List继承自Collection接口。List是一种有序集合，List中的元素可以根据索引（顺序号：元素在集合中处于的位置信息）进行取得/删除/插入操作。
跟Set集合不同的是，List允许有重复元素。对于满足e1.equals(e2)条件的e1与e2对象元素，可以同时存在于List集合中。当然，也有List的实现类不允许重复元素的存在。同时，List还提供一个listIterator()方法，返回一个ListIterator接口对象，和Iterator接口相比，ListIterator添加元素的添加，删除，和设定等方法，还能向前或向后遍历，具体的方法往下看。List接口的实现类主要有ArrayList，LinkedList，Vector，Stack等。

List算法

Explanation	Name
使用合并排序算法排序List，默认为升序排列	sort
使用随机源对指定列表进行置换	shuffle
反转指定列表中元素的顺序	reverse
根据指定的距离轮换指定列表中的元素	rotate
交换指定位置上的元素	swap
使用一个值替换列表中出现的所有某一指定值	replaceAll
使用指定元素替换列表中的所有元素	fill
将所有元素从一个列表复制到另一个列表	copy
使用二分搜索指定列表，以获得指定对象	binarySearch
返回指定列表中第一次出现指定目标列表的起始位置；如果没有这样的目标则返回-1.	indexOfSubList
返回指定列表中最后一次出现指定目标列表的起始位置；如果没有这样的目标则返回-1	lastIndexOfSubList

ArrayList

ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。size、isEmpty、get、set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。

每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
主要方法：

Function	Explanation
public boolean add(E e)	添加元素
Public void add(int index,E element)	在指定位置添加元素
public Iterator<E> iterator()	取得Iterator对象便于遍历所有元素
public E get(int index)	根据索引获取指定位置的元素
public E set(int index,E element)	替换掉指定位置的元素

排序方法

Functiom	Explanation
Collections.sort(java.util.List<T>)	对List的元素进行自然排序
Collections.sort(java.util.List<T>,java.util.Comparator<? super T>)	对List中的元素进行自定义排序

LinkedList

LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：

List list = Collections.synchronizedList(new LinkedList(...));

Map.jpg

Map

Map是一种把键对象和值对象进行映射的集合，它的每一个元素都包含一堆键对象和值对象；
向Map添加元素时，必须提供键对象和值对象；
从Map中检索元素时，只要给出键对象，就可以返回对应的值对象；
键对象不能重复，但值对象可以重复；
Map有两种常见的实现类：HashMap和TreeMap。

Function	Explanation
V put(K key,V value)	插入元素
V get(Object key)	根据键对象获取值对象
Set<K> KeySet()	取得所有键对象集合
Collection<V> values()	取得所有值对象集合
Set<Map.Entity<K,V>> entrySet()	取得Map.Entry代表一个Map中的元素

HashMap

HashMap按照哈希算法来存取键对象，有很好的存取性能。和HashSet一样，要求当两个键对象通过equals()方法比较为true时，这两个键对象的hashCode()方法返回的哈希码也一样。

HashCode:

HashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap，等，HashCode经藏用语确定对象的存储地址

如果两个对象相同，equals方法一定返回true，并且这两个对象的HashCode一定相同

两个对象的HashCode相同，并不一定表示两个对象就相同，即equals()不一定为true，只能说明这两个对象在一个散列存储结构中

如果对象的equals()方法被重写，那么对象的HashCode也尽量重写

作用：

从Object的角度看，JVM每new一个Object，它都会将这个Object怼到一个Hash表中去，这样的话，下次做Object的比较或者取这个对象的时候（读取过程），它会根据对象的HashCode再从Hash表中取这个对象。这样做的目的是 $\color{red}{提高对象的效率}$ 。若HashCode相同再去调用equal。

TreeMap

TreeMap实现了SortedMap接口，能对键对象进行排序。同TreeSet一样，TreeMap也支持自然排序和客户化排序两种方式。

如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

$\color{red}{LinkedList}$

Interface Iterable<T>

The functions forEach() and spliterator() both use a keword “default” which means we could provide the default implement in an abstruct class，breaking the previous rule in JAVA.

JDK8 Functional interface

Function	Explanation
Function<T,R>	accept a parameter and return a result
Consumer<T>	accept a parameter without result returned
Predicate<T>	accept a parameter and return a boolean result
Supplier<T>	without parameter and one result returned

remark1:

Three methods

1.1 The only abstract method

1.2 use default to define general methods, invoking through an instance.

1.3 use static define static methods, invoking through interface name.
a new annotation

if some interface is functional interface ,then making it has only one abstract method when defining.So there is a new annonation:

@FunctionInterface

remark2(lambda expression):

use anonymous inner class to impement an interface:

Function<Integer,String> fun = new Function<Integer,String>(){
  @Override
  public String apply(Integer t){
        return String.valueOf(t);
  }
}

use lambda expression to implement:

Function<Integer,string> -> (t){String.valueOf(t);}

Collection<E> extends Iterable<E>

$\color{blue}{Int size()}$
- if the collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE, otherwise return the number of elements in it.
$\color{blue}{boolean isEmpty()}$ ;
- if the collection empty, return true;
boolean contains(Object o)
- return ture if the collection contain the specified element.
$\color{blue}{Iterator<E> iterator()}$
- return an iterator over the elements in the collection, unless provide a guarantee itself, there are no guarantee concerning the order in which the elements are returned.
$\color{blue}{Object[] toArray();}$
- returns am array containing all of the elements in this collection.
$\color{blue}{<T> T[] toArray(T[] a);}$
- Params:
 - a: the array into which the elements of this collection are to stored,if it is big enough; otherwise. a new array of the same runtime type is allocated for this purpose.If the collecition fits in the specified array with room to spare, the element in the array immediately following the end of the collection is set to null.
- Returns:
 - an array containing all of the elements in this collection.
$\color{blue}{boolean add(E e);}$
- return true if operation successful;
boolean remove(Object o)
boolean containsAll(Collection<?> c);
- return true if this collection contains all of the elements in the specified collection.
boolean addAll(Collection<? extends E> c);
boolean removeAll(Collection<?> c);
default boolean removeIf(Predicate<? super E> filter){...}
- Removes all of the elements of this collection that satisfy the given predicate.
- true if any elements were removed.
boolean retainAll(Collection<?> c);
- Removes from this collection all of its elements that are not contained in the specified collection.
void clear();
- Removes all of the elements from this collection.The collection will be empty after this methods returns.
boolean equals(Object o);
- Attention: if implements the Controller interface ”directly“ ， must exercise care if if they choose to override the Object.equals.(When need compare the value instead of inference)
- returns true if the specified object is equals to this collection.
int hashCode();
- Attention:if override the method Object.equals then must override Object.hashCode()（because of hashcode contract）
- Returns the hashcode of the collection
default Spliterator<E> spliterator(){...}
- Creates a Spliterator over the elements in this collection.
 - Spliterator: always used with steam to traverse and divide sequential.
default Stream<E> stream() {...}
- Returns a sequential Stream with this collection as its source.
default Stream<E> parallelStream() {...}
- Returns a possibly parallel Stream with this collection as its source. It is allowable for this method to return a sequential stream.

List<E> extends Collection<E>

boolean addAll(int index,Collection<? extends E> c);
- Inserts all of the elements in the specified collection into this list at the specified position.
boolean retainAll(Collection<?> c)
- Retains only the elements in this list that are contained in the specified collection.
default void replaceAll(UnaryOperator<E> operator){...}
- Replaces each element of the list with the result of applying the operator to that element.
default void sort(Comparator<? super E> c){...}
- sorts this list according to the order induced by the specified Comparator.
E set(int index, E element);
- replace the element at the specified position in this list with the specified element.
- returns the element previously at the specified position.
E get(int index)
- reurns the element at the specified position.
int indexOf(Object o);
- Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
int lastIndexOf(Object o);
- Returns the index of the last occurrence of the specified element in this list , or -1 if there is no such index.
ListIterator<E> listIterator();
- returns a list iterator over the elements in this list(in proper sequence).
ListIterator<E> listIterator(int index);
- Returns a list iterator over the elements in this list, starting at the specified position in the list.
List<E> subList(int fromIndex,int toIndex);
- returns a view of portion of this list between the specified fromIndex, inclusive,and toIndex, exclusive.(If fromIndex and toIndex are equal, the returned list is empty).

AbstractList<E> extends AbstractCollection<E> implements list<E>

Transient: the key word to avoid serializable;

checkForComodification();

used to realize fail-fast mechanism.

There are two threads, one is for traversing the list and another is for modifying the list.Sometimes thread A is traversing the list(at this moment expectedModCount=modCount=N), meanwhile thread B adds an element leading to the value of modCount modified(modCount+1=N+1). Method checkForComodification find that expectedModCunt=N, while modCount=N+1 which means two values are not equal, so the ConcurrentModificationException are throwed out and fail-fast mechanism happened.

cursor:the index of next element

lastRet:the index of last element

public List<E> subList(int fromIndex, int toIndex)

public List<E> subList(int fromIndex,int toIndex) {
  return (this instance of RandomAccess? new RandomAccessSubList<>(this,fromIndex, toIndex):new SubList<>(this, fromIndex, toIndex));
}

public interface RandomAccess{}

RandomAccess is an empty interface to identify some class backing random access or not. A class that backing random access aparently could use a more efficient arithmetic.

classes realized random access：
- ArrayList
- AttributeList
- CopyOnWriteArrayList
- Vector
- Stack
- Etc...

容器框架学习

具体

List集合

List算法

ArrayList

LinkedList

Map

HashMap

TreeMap

$\color{red}{LinkedList}$

Interface Iterable<T>

Collection<E> extends Iterable<E>

List<E> extends Collection<E>

AbstractList<E> extends AbstractCollection<E> implements list<E>

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读