来自java.util.Arrays,用来处理数组的各种方法。
用来返回由自定数组支持的固定大小列表,虽然这里返回了一个List,但是这个是Arrays中的一个内部类,这里边主要的方法有:
并没有add和remove方法,因此它是不支持add和remove方法的,是一个定长列表,不支持添加和删除,但是可以修改
注:因为参数是泛型的,所以是不能使用基础数据类型作为参数的,但是基本数据类型的数组是可以的。
它有一系列重载方法,包括各种基本数据类型和Object类型(实现了Comparable接口)的重载方法
binarySearch只可以在有序数组中进行查找,找到元素返回数组下标,没有则返回负数。
调用System._arraycopy_
实现数组copy,将原数组copy成新数组,数组长度为设置长度。
对比两个数组中对应位置的每个元素是否相等。
用来对比两个数组元素是否相等,主要是对比多维数组,而且任意层次嵌套数组。
用来给数组赋值,有多种类型的重载方法
ArrayList就是动态数组,由数组实现,支持随机访问,元素有序并且可以重复。
RandomAccess
接口是一个标记接口,此接口一般用于List实现,以表示他们支持快速(O(1))的随机访问。
重要属性:
/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance used for empty instances. */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. 用于第一次添加元素时是否扩展成DEFAULT_CAPACITY */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // non-private to simplify nested class access /** * The size of the ArrayList (the number of elements it contains). * * @serial */ private int size; /** * The number of times this list has been <i>structurally modified</i>. * Structural modifications are those that change the size of the * list, or otherwise perturb it in such a fashion that iterations in * progress may yield incorrect results. * * <p>This field is used by the iterator and list iterator implementation * returned by the {@code iterator} and {@code listIterator} methods. * If the value of this field changes unexpectedly, the iterator (or list * iterator) will throw a {@code ConcurrentModificationException} in * response to the {@code next}, {@code remove}, {@code previous}, * {@code set} or {@code add} operations. This provides * <i>fail-fast</i> behavior, rather than non-deterministic behavior in * the face of concurrent modification during iteration. * * <p><b>Use of this field by subclasses is optional.</b> If a subclass * wishes to provide fail-fast iterators (and list iterators), then it * merely has to increment this field in its {@code add(int, E)} and * {@code remove(int)} methods (and any other methods that it overrides * that result in structural modifications to the list). A single call to * {@code add(int, E)} or {@code remove(int)} must add no more than * one to this field, or the iterators (and list iterators) will throw * bogus {@code ConcurrentModificationExceptions}. If an implementation * does not wish to provide fail-fast iterators, this field may be * ignored. 提供快速失败方式 */ protected transient int modCount = 0;
ArrayList默认初始容量是0,而不是10,10是第一次添加元素时,如果是默认集合,也就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
,那么第一次会增加到10。如果是EMPTY_ELEMENTDATA
,那么每次在原基础上扩大1.5倍。
重载方法还有void add(int index, E element)
通过Arrays.cooy()
进行动态数组的扩容,首先会通过ensureCapacityInternal
判断确定集合大小。其中逻辑中就有上面提到的DEFAULTCAPACITY_EMPTY_ELEMENTDATA
对于它的特殊判断。每次修改都会使modCount
加1,这个是为了确保ArrayList
迭代器使用,在并发操作中如果被修改,那么可以快速失败(类似乐观锁)
只有数组元素超过了当前长度时才会进行扩容,扩容最大可以扩容0x7fffffff
,int的最大值。
可以添加null值。
修改modCount
重载方法有:boolean remove(Object o)移除**第一个查询**到的元素
、boolean removeAll(Collection<?> c)移除所有集合中相关的元素(并非第一个)
、boolean removeIf(Predicate<? super E> filter)移除符合条件的元素
。
在remove方法中主要是应用System._arraycopy_
进行元素的移除。
修改modCount
设置某个元素的元素。不会修改modCount。
返回该位置的元素
返回第一次出现该元素的下标位置,不存在返回_-1_
int lastIndexOf(Object o)
从后至前,第一次出现的下标位置。
返回一个Itr
内部类,属于Iterator
接口的实现类,在内部通过checkForComodification()
方法对expectedModCount
和modCount
进行检查,实现乐观锁机制。
ArrayList内部还提供了一种方式,就是ListIterator<E> listIterator()
,用来生成ListItr
内部类,它是Itr
的子类,它相较于Itr
内部类,提供了向前遍历的previous
方法以及add
方法。
除了上面Iterator以外,还有三种遍历方式,分别是
for (int i = 0; i < a.size(); i++) { a.get(i); }
这种直接for的,不会检验modCount
void forEach(Consumer<? super E> action)
通过lamda表达式进行,这种也会检验modCount
for (Integer s : a) { System._out_.println(s); }
这种属于JDK的一种语法糖,如果通过反编译的话,依然是使用Iterator进行的遍历。
用来生成一个SubList
类,它是一个内部类,可以看成是原集合的视图,如果对subList类进行修改和新增操作的话,那么原数组也会进行相应的操作。
返回集合的数量,并不是数组的数量。
该方法用来回收多余的内存,即一旦确定集合不再添加多余的元素后,调用该方法将数组大小刚好调整成集合元素大小。
通过双链表实现的集合类。因为LinkedList
实现Deque
的原因,所以可以直接使用LinkedList
作为Deque
和Queue
的一种声明方式,而ArrayList
就不可以,只能使用ArrayDeque
。
重要属性:
transient int size = 0; /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ 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; } }
链表无需预先初始化集合的长度。
重载方法有:void addLast(E e)和add一致
、void addFirst(E e)
、void add(int index, E element)
、boolean addAll(Collection<? extends E> c)
、boolean addAll(int index, Collection<? extends E> c)在指定位置插入该集合
插入元素
重载方法有:E removeFirst()与默认一致
、E remove(int index)
、boolean remove(Object o)
、boolean removeFirstOccurrence(Object o)与前面remove(Object o)一致
、E removeLast()
、boolean removeLastOccurrence(Object o)
、boolean removeAll(Collection<?> c)
、boolean removeIf(Predicate<? super E> filter)
移除元素
替换指定位置的元素
重载方法:E getFirst()
、E getLast()
获取元素
ArrayList
具备的遍历方式,Linked也同样具备,但是因为它的内部数据结果所决定的,如果使用普通for循环,那么将会导致更多时间消耗,因为它的get时间复杂度是O(N)。
可以使用迭代器,它记录的是上一个Node
节点,这样访问下一个节点时,无需从头遍历。
其他和ArrayList
差不多。
·
HashMap
是采用链地址法来解决hash冲突,在JDK1.7中,HashMap
是由数组+链表构成的,但是在JDK1.8中,HashMap
是由数组+链表+红黑树构成。
// 默认最小容量为16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. 默认最大的容量 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. 负载因子 */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. 当桶bucket上节点大于这个值时转换成红黑树 */ static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. 当桶Bucket节点数小于这个值时转换成链表 */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. 当集合中元素小于该值时,即使上面桶中数量超过了阈值,也不会转换成树,而是进行扩容。 */ static final int MIN_TREEIFY_CAPACITY = 64; /** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some operations to allow * bootstrapping mechanics that are currently not needed.) 保存实际的数据 */ transient Node<K,V>[] table; /** * Holds cached entrySet(). Note that AbstractMap fields are used * for keySet() and values(). */ transient Set<Map.Entry<K,V>> entrySet; /** * The number of key-value mappings contained in this map. */ transient int size; /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */ transient int modCount; /** * The next size value at which to resize (capacity * load factor). * * @serial */ // (The javadoc description is true upon serialization. // Additionally, if the table array has not been allocated, this // field holds the initial array capacity, or zero signifying // DEFAULT_INITIAL_CAPACITY.) // 扩容的阈值,一般值为capacity * load factor,每次扩容总是之前的两倍,即2的幂数 int threshold; /** * The load factor for the hash table. * 负载因子,默认值0.75,该值可以大于1,这是因为链接表的原因 * @serial */ final float loadFactor;
hash:
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
类似方法:void putAll(Map<? extends K, ? extends V> m)
、V putIfAbsent(K key, V value)
在该方法中,如果size
大于threshold
,则进行扩容,调用resize()
方法,其他的逻辑是根据hash值所在的桶是否有值,如果没有,则直接添加到该节点;如果有,则判断该位置应该为链表还是红黑树,进行对应的添加操作。
注意:如果是链表,当数量大于等于阈值_TREEIFY_THRESHOLD_
,则转换成为红黑树;红黑树中也有相应的转为链表操作。
对于方法afterNodeAccess(Node<K,V> p)
、afterNodeInsertion(boolean evict)
,在HashMap
中并没有具体实现,在LinkedHashMap
中有相应的处理。
在该方法中进行扩容,扩容指的是对于属性table
数组的大小调整,类似于ArrayList的动态扩容,但是多了一些对于链表和红黑树的操作,这里扩容时的阈值属性是threshold
。
在Map中最大可扩容的数量依然是0x7fffffff
,当然这个不是指size
最大是该值,而是值桶最多只有这么多。
在JDK1.8中,每次扩容都是直接扩容2倍,所以原来的元素要么在原位置,要么在原位置+原数组长度。
类似方法:boolean remove(Object key, Object value) key-value同时相等时,移除
Map移除元素,一般先找到桶的位置(通过hash),然后判断。如果是链表,则进行链表的遍历,找到需要删除的元素后删除,如果是红黑树,遍历树,找到元素后删除调整平衡,并且当红黑树小于阈值UNTREEIFY_THRESHOLD
时,则转化成链表。
对于afterNodeRemoval(Node<K,V> p)
,同样是LinkedHashMap
进行处理
类似方法:V getOrDefault(Object key, V defaultValue)
、boolean containsKey(Object key)
、boolean containsValue(Object value)通过遍历查找每一个value,O(N)的时间复杂度
根据key查找元素,查看桶的第一个节点,如果是则返回,如果不是,则遍历链表或者红黑树。不存在返回null。
可以通过Set<K> keySet()
、Collection<V> values()
分别获取到key或者value的集合。
不推荐使用keySet
获取到key的集合后,get每一个value。
可以使用Set<Map.Entry<K,V>> entrySet()
来直接获取到key和value 的集合。
上面三种获取集合的方式,都是可以使用迭代器的。
注意:modCount的变化
LinkedHashMap
是基于HashMap
实现的一种集合,具有HashMap集合的所有特性,除了HashMap
是无序的,LinkedHashMap
是有序的,这个是因为LinkedHashMap
在HashMap
基础上单独维护一个具有所有数据的双向链表,该链表保存了元素迭代的顺序。
Entry节点:
/** * HashMap.Node subclass for normal LinkedHashMap entries. */ static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }
它是一个双向链表。
属性:
/** * The head (eldest) of the doubly linked list. */ transient LinkedHashMap.Entry<K,V> head; /** * The tail (youngest) of the doubly linked list. */ transient LinkedHashMap.Entry<K,V> tail; /** * The iteration ordering method for this linked hash map: <tt>true</tt> * for access-order, <tt>false</tt> for insertion-order. * * @serial */ final boolean accessOrder;
除继承自HashMap
的属性外,单独维护一个双向链表,这些都是双向链表必要的属性和数据结构。
LinkedHashMap
中没有put方法,而是直接调用HashMap
的put方法,只是重写了afterNodeAccess(Node<K,V> p)
、afterNodeInsertion(boolean evict)
方法。
当然在添加新元素时,也将新元素添加到了链表的末尾。通过方法linkNodeLast()
afterNodeAccess
主要是在accessOrder
为true时(并且当前节点不为尾结点)生效,也就是根据访问顺序排序。在具体实现中,将该节点从其他位置移动到尾部。
afterNodeInsertion
主要是处理添加后是否要移除首节点的元素,可以利用这个特性来实现LRU算法,其中需要重写boolean removeEldestEntry(Map.Entry<K,V> eldest)
方法。
LinkedHashMap
直接调用HashMap
的remove
方法。只是在其中重写了afterNodeRemoval
方法,
在该方法中增加了移除双链表中某个元素的功能。比较简单
LinkedHashMap
是根据双链表进行遍历的,这样就是有序的,其中方法entrySet
返回的是LinkedEntrySet
内部类。
TreeMap
是有Tree
和Map
集合有关的,由红黑树作为底层实现的有序k-v集合
它不但继承了AbstractMap
,而且实现了接口NavigableMap
,表示它支持一系列获取指定集合的导航方法,比如获取小于指定key的集合。
因为是有序集合,所以在可以在构造方法中直接传入构造器,如public TreeMap(Comparator<? super K> comparator)
,当然也可以在key的类中实现比较器Comparable
这里的有序是根据key对元素进行排序,上面LinkedHashMap只是保证了一个插入/访问的顺序,并不是根据key有序的。
类似方法:void putAll(Map<? extends K, ? extends V> map)
、V putIfAbsent(K key, V value)
如果没有实现comparator方法,则key不允许为null值
类似方法:boolean remove(Object key, Object value)
移除元素
注:本文为《Java修炼指南:高频源码解析》阅读笔记