《Java修炼指南:高频源码解析》阅读笔记一Java数据结构的实现集合类

一、Arrays工具类

来自java.util.Arrays,用来处理数组的各种方法。

1.1 List asList(T… a)

用来返回由自定数组支持的固定大小列表,虽然这里返回了一个List,但是这个是Arrays中的一个内部类,这里边主要的方法有:
《Java修炼指南:高频源码解析》阅读笔记一Java数据结构的实现集合类

并没有add和remove方法,因此它是不支持add和remove方法的,是一个定长列表,不支持添加和删除,但是可以修改

注:因为参数是泛型的,所以是不能使用基础数据类型作为参数的,但是基本数据类型的数组是可以的。

1.2 void sort(int[] a)

它有一系列重载方法,包括各种基本数据类型和Object类型(实现了Comparable接口)的重载方法

1.3 int binarySearch(int[] a, int key)

binarySearch只可以在有序数组中进行查找,找到元素返回数组下标,没有则返回负数。

1.4 int[] copyOf(int[] original, int newLength)

调用System._arraycopy_实现数组copy,将原数组copy成新数组,数组长度为设置长度。

1.5 boolean equals(int[] a, int[] a2)

对比两个数组中对应位置的每个元素是否相等。

1.6 boolean deepEquals(Object[] a1, Object[] a2)

用来对比两个数组元素是否相等,主要是对比多维数组,而且任意层次嵌套数组。

1.7 void fill(int[] a, int val)

用来给数组赋值,有多种类型的重载方法

二、ArrayList类

ArrayList就是动态数组,由数组实现,支持随机访问,元素有序并且可以重复。
《Java修炼指南:高频源码解析》阅读笔记一Java数据结构的实现集合类

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倍。

2.1 boolean add(E e)

重载方法还有void add(int index, E element)
通过Arrays.cooy()进行动态数组的扩容,首先会通过ensureCapacityInternal判断确定集合大小。其中逻辑中就有上面提到的DEFAULTCAPACITY_EMPTY_ELEMENTDATA对于它的特殊判断。每次修改都会使modCount加1,这个是为了确保ArrayList迭代器使用,在并发操作中如果被修改,那么可以快速失败(类似乐观锁)
只有数组元素超过了当前长度时才会进行扩容,扩容最大可以扩容0x7fffffff,int的最大值。
可以添加null值。
修改modCount

2.2 E remove(int index)

重载方法有:boolean remove(Object o)移除**第一个查询**到的元素boolean removeAll(Collection<?> c)移除所有集合中相关的元素(并非第一个)boolean removeIf(Predicate<? super E> filter)移除符合条件的元素

在remove方法中主要是应用System._arraycopy_进行元素的移除。
修改modCount

2.3 E set(int index, E element)

设置某个元素的元素。不会修改modCount。

2.4 E get(int index)

返回该位置的元素

2.5 int indexOf(Object o)

返回第一次出现该元素的下标位置,不存在返回_-1_
int lastIndexOf(Object o)从后至前,第一次出现的下标位置。

2.6 Iterator iterator()

返回一个Itr内部类,属于Iterator接口的实现类,在内部通过checkForComodification()方法对expectedModCountmodCount进行检查,实现乐观锁机制。

ArrayList内部还提供了一种方式,就是ListIterator<E> listIterator(),用来生成ListItr内部类,它是Itr的子类,它相较于Itr内部类,提供了向前遍历的previous方法以及add方法。

2.7 遍历方式

除了上面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进行的遍历。

2.8 List subList(int fromIndex, int toIndex)

用来生成一个SubList类,它是一个内部类,可以看成是原集合的视图,如果对subList类进行修改和新增操作的话,那么原数组也会进行相应的操作。

2.9 int size()

返回集合的数量,并不是数组的数量。

2.10 void trimToSize()

该方法用来回收多余的内存,即一旦确定集合不再添加多余的元素后,调用该方法将数组大小刚好调整成集合元素大小。

三、LinkedList类

通过双链表实现的集合类。因为LinkedList实现Deque的原因,所以可以直接使用LinkedList作为DequeQueue的一种声明方式,而ArrayList就不可以,只能使用ArrayDeque
《Java修炼指南:高频源码解析》阅读笔记一Java数据结构的实现集合类

重要属性:

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

链表无需预先初始化集合的长度。

3.1 boolean add(E e)

重载方法有: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)在指定位置插入该集合

插入元素

3.2 E remove()

重载方法有: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)
移除元素

3.3 E set(int index, E element)

替换指定位置的元素

3.4 E get(int index)

重载方法:E getFirst()E getLast()
获取元素

3.5 遍历方式

ArrayList具备的遍历方式,Linked也同样具备,但是因为它的内部数据结果所决定的,如果使用普通for循环,那么将会导致更多时间消耗,因为它的get时间复杂度是O(N)。
可以使用迭代器,它记录的是上一个Node节点,这样访问下一个节点时,无需从头遍历。
其他和ArrayList差不多。
·

四、HashMap类

HashMap是采用链地址法来解决hash冲突,在JDK1.7中,HashMap是由数组+链表构成的,但是在JDK1.8中,HashMap是由数组+链表+红黑树构成。
《Java修炼指南:高频源码解析》阅读笔记一Java数据结构的实现集合类

	// 默认最小容量为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);
    }

4.1 V put(K key, V value)

类似方法: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中有相应的处理。

4.2 Node<K,V>[] resize()

在该方法中进行扩容,扩容指的是对于属性table数组的大小调整,类似于ArrayList的动态扩容,但是多了一些对于链表和红黑树的操作,这里扩容时的阈值属性是threshold
在Map中最大可扩容的数量依然是0x7fffffff,当然这个不是指size最大是该值,而是值桶最多只有这么多。
在JDK1.8中,每次扩容都是直接扩容2倍,所以原来的元素要么在原位置,要么在原位置+原数组长度。

4.3 V remove(Object key)

类似方法:boolean remove(Object key, Object value) key-value同时相等时,移除
Map移除元素,一般先找到桶的位置(通过hash),然后判断。如果是链表,则进行链表的遍历,找到需要删除的元素后删除,如果是红黑树,遍历树,找到元素后删除调整平衡,并且当红黑树小于阈值UNTREEIFY_THRESHOLD时,则转化成链表。
对于afterNodeRemoval(Node<K,V> p),同样是LinkedHashMap进行处理

4.4 V get(Object key)

类似方法:V getOrDefault(Object key, V defaultValue)boolean containsKey(Object key)boolean containsValue(Object value)通过遍历查找每一个value,O(N)的时间复杂度
根据key查找元素,查看桶的第一个节点,如果是则返回,如果不是,则遍历链表或者红黑树。不存在返回null。

4.5 遍历方法

可以通过Set<K> keySet()Collection<V> values()分别获取到key或者value的集合。
不推荐使用keySet获取到key的集合后,get每一个value。
可以使用Set<Map.Entry<K,V>> entrySet()来直接获取到key和value 的集合。
上面三种获取集合的方式,都是可以使用迭代器的。
注意:modCount的变化

五、LinkedHashMap类

LinkedHashMap是基于HashMap实现的一种集合,具有HashMap集合的所有特性,除了HashMap是无序的,LinkedHashMap是有序的,这个是因为LinkedHashMapHashMap基础上单独维护一个具有所有数据的双向链表,该链表保存了元素迭代的顺序。
《Java修炼指南:高频源码解析》阅读笔记一Java数据结构的实现集合类

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的属性外,单独维护一个双向链表,这些都是双向链表必要的属性和数据结构。

5.1 添加函数

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)方法。

5.2 删除元素

LinkedHashMap直接调用HashMapremove方法。只是在其中重写了afterNodeRemoval方法,
在该方法中增加了移除双链表中某个元素的功能。比较简单

5.3 遍历元素

LinkedHashMap是根据双链表进行遍历的,这样就是有序的,其中方法entrySet返回的是LinkedEntrySet内部类。

六、TreeMap类

TreeMap是有TreeMap集合有关的,由红黑树作为底层实现的有序k-v集合
它不但继承了AbstractMap,而且实现了接口NavigableMap,表示它支持一系列获取指定集合的导航方法,比如获取小于指定key的集合。
《Java修炼指南:高频源码解析》阅读笔记一Java数据结构的实现集合类

因为是有序集合,所以在可以在构造方法中直接传入构造器,如public TreeMap(Comparator<? super K> comparator),当然也可以在key的类中实现比较器Comparable
这里的有序是根据key对元素进行排序,上面LinkedHashMap只是保证了一个插入/访问的顺序,并不是根据key有序的。

6.1 V put(K key, V value)

类似方法:void putAll(Map<? extends K, ? extends V> map)V putIfAbsent(K key, V value)
如果没有实现comparator方法,则key不允许为null值

6.2 V remove(Object key)

类似方法:boolean remove(Object key, Object value)
移除元素

注:本文为《Java修炼指南:高频源码解析》阅读笔记

上一篇:第十二届蓝桥杯 砝码称重


下一篇:(148)FPGA面试题-Verilog利用减法实现除法