源码 1.Java集合类综述2


我非常热衷于源码研究,也非常愿意分享我对源码的研究经验。如果读者也想研究源码,可以关注我的分享文章。在分析源码的过程中,我们会选择paw ding解牛的分析,将每一行核心代码都分析清楚,让读者真正理解透彻,以便在以后的访谈中或者独立开发中间件,会有很大的帮助。很大的好处。

前言

本节以上帝视角剖析整个Java容器类,让读者从宏观上把握,一目了然。对于本节涉及的位操作,如果觉得基础不够,可以查看作者专门分析容器类的位操作文章。,从数据结构入手,从假溢出——缺乏顺序队列存储结构过渡到有选择的数据结构,循环队列。通过以图文形式对核心代码进行详尽解析,同时开启容器源码阅读技巧之门,让源码阅读从晦涩到赏心悦目。研究Java容器类的源代码将获得很多好处。1. Java容器类经常出现在面试中,会让你在面试中脱颖而出,把面试官打胖。2. 为你学习数据结构和算法打下坚实的基础。3、让你写出高效性能、更好的代码容错性的高质量代码,考虑问题更全面。

一、Java集合类概述

源码 1.Java集合类综述2

2.研究经历

整体来说说Java集合源码的研究心得吧。读者要想能够顺利的阅读源码,必须具备两个技能。

1). 位运算能力(位运算性能非常好,有些功能用位运算很容易实现,比如用哈希表容量求2的整数次方)

2). 数据结构能力

Java集合类的每个实现类都基于特定的数据结构。这也是作者在前面3节介绍位操作和树结构的初衷。希望读者能够非常清楚的掌握相应的数据结构。如果这两个能力还不够扎实。关注作者,了解之前的内容。只要具备这两个能力,阅读源码就非常轻松。

对于任何一个容器类,你只需要关注构造函数、添加操作、删除操作、修改操作,以及如何调整这些容器。

我会详细分析,,,这4个核心容器类,把每一行核心代码都用图文的形式解释清楚,因为在我看来,这4个类是整个Java集合类中最有技术含量的,所以有必要解释清楚,读者只要能看懂这4个类的源码,再研究其他容器的源码就很容易了。

3.涉及数据结构和算法

在容器类中,我们看到应用了如下数据结构:

动态数组:内部是动态数组,内部链表数组也是动态扩展的,内部也是动态扩展的数组。链表:它是用双向链表实现的。映射到同一个链表数组的键值对通过单向链表链接起来,其中的每个元素也加入到一个双向链表中,以维护插入或访问顺序。哈希表:是用哈希表实现的,基于它,当然内部也是哈希表。排序二叉树:用红黑树实现(基于排序二叉树)。它在内部使用。当然,它也是一棵红黑树。红黑树可以保持元素的有序性,综合性能高。堆:它是用堆实现的。堆在逻辑上是一棵树,在物理上是一个动态数组。堆可以高效地解决一些其他数据结构难以解决的问题。循环数组:由循环数组实现,通过维护头尾变量实现高效的队列操作。位向量:由位向量来实现。对于只有两种状态,需要集合运算的数据,用位向量表示,用位运算处理,精简高效。

每个数据结构往往包含一定的算法策略,这往往是一种妥协,如:

动态扩容算法:动态数组的扩容策略一般是指数扩容,在两个方面进行平衡。一方面希望减少内存消耗,另一方面希望减少内存分配、移动和复制的开销。哈希算法:将哈希表中的键映射到链表数组的索引的算法。算法要快,同时要尽可能随机均匀。二叉树排序的平衡算法:二叉树排序的平衡很重要。红黑树是一种平衡算法,AVL树是另一种。一方面,平衡算法必须保证尽可能多的平衡,另一方面,它必须最小化整体开销。

4.数据结构分析

1、假溢出——顺序队列存储结构不足

队列是一种特殊的线性表,它的特殊之处在于它只允许在表的前端(front)进行删除操作,在表的后端(rear)进行插入操作。队列是一个有限操作的线性表。插入操作结束的称为队尾,删除操作结束的称为队头。

源码 1.Java集合类综述2

假设是一个长度为5的数组,初始状态,空队列如图,前后指针都指向下标为0的位置。

然后入队a1,a2,a3,a4,前指针仍然指向下标0的位置,后指针指向下标4的位置

源码 1.Java集合类综述2

当a1和a2出队时,front指针指向下标2的位置,rear保持不变,如下图,然后进入a5。此时前指针不变,后指针移出数组。

源码 1.Java集合类综述2

假设这个队列的总数不超过5,但是如果当前继续加入队列,因为数组尾部的元素已经被占用,如果后面再加入,数组越界会发生错误,但实际上,我们的队列是下标的,因为 0 和 1 仍然是空闲的。假溢出

2.优化-循环队列

有一个问题:连续出队时,队头左边的空间没有被充分利用,导致队列容量越来越小。

解题:通过数组实现循环队列,充分利用空间(取模:%)。当记录队列尾部的变量达到数组长度时,检查记录队列头部的变量是否在数组的开头。如果不是,则队列尾部从数组起始位置开始存值,并向后移动。

循环队列的实现方式:

添加一个属性size,记录当前元素个数。目的是在head=rear时通过size=0或者size=array 来区分队列是空的还是队列满的。数组中只存入数组大小-1个元素,保证绕一圈后rear不会等于head,即队列满时rear+1=head,且只有一个空元素在中间。

使用方法:

第二种方式是牺牲一个元素空间来区分空码和满码。

1.对front变量的含义做一个调整:front直接指向数组queue的第一个元素front = 0

2、对rear变量的含义做一个调整:rear指向队列最后一个元素之后的位置,因为希望空出一个空间,约定rear = 0

3.当队列满时,条件为rear+1 % == front [full]

4.当队列为空时,rear == front [empty]

5、我们这样分析的时候,队列中有效数据的个数(rear+-front)%

注意:这5个属性一定要牢牢记住源码,深刻理解。源码就是在这些结论的基础上实现的。从源码分析中,你会切实感受到位操作和数据结构的重要性。

源码 1.Java集合类综述2

特别是在明源代码中,front = tail = 0 开头。如果将一个元素front添加到队列的头部并逆时针旋转,则将元素tail添加到队列的末尾并顺时针旋转。当front == tail时,表示队列已满,需要扩容。

源码 1.Java集合类综述2

5.具体代码分析

5.1 实例变量

/**
 * The array in which the elements of the deque are stored.
 * The capacity of the deque is the length of this array, which is
 * always a power of two. The array is never allowed to become
 * full, except transiently within an addX method where it is
 * resized (see doubleCapacity) immediately upon becoming full,
 * thus avoiding head and tail wrapping around to equal each

* other. We also guarantee that all array cells not holding * deque elements are always null. */ transient Object[] elements; // non-private to simplify nested class access /** * The index of the element at the head of the deque (which is the * element that would be removed by remove() or pop()); or an * arbitrary number equal to tail if the deque is empty. */ transient int head; /** * The index at which the next element would be added to the tail * of the deque (via addLast(E), add(E), or push(E)). */ transient int tail;

5.2 岩心钻头运行分析

private void allocateElements(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;
        if (initialCapacity >>= 1;// Good luck allocating 2 ^ 30 elements
    }
    elements = new Object[initialCapacity];
}

1、结论:求出大于上述函数左右的2的第一个整数次方的个数

如果 = 6;最后8。

= 10; 终于16了

注 = 8; 最终也是16岁。

我们这样定义位索引顺序,0-15位

如果n = 0 微信:0011 从左到右,第一个出现1的索引位是11,对应0-10上面位上0和1的排列,经过下面的操作,

一直把n改成0 微信:1111

n |= (n >>>  1);
n |= (n >>>  2);
n |= (n >>>  4);
n |= (n >>>  8);

n |= (n >>> 16);

重点分析n |= (n >>> 1); n |= (n >>> 1) ==>> n = (n >>> 1) | 名词;

n >>> 1是将n原来的第11个索引位置设置为0,第10个索引位置为1,|的结果 与n的运算赋值给n,使得n的第11-10个索引位置都为1,即n=0 微信:0011

同样,n |= (n >>> 2); 使得索引位11-8全为1,即n = 0 微信:0011

同样,n |= (n >>> 4); 使得索引位11-4全为1,即n = 0 微信:1011

同样,n |= (n >>> 8); 使得索引位11-0全为1,即n = 0 微信:1111

同样,n |= (n >>> 16); 使得索引位11-0全为1,即n = 0 微信:1111

n+1的结果是0 微信:0000变成2的整数次方

2. 什么时候。是 2 的整数次幂:

(tail-head)&(.-1) 等于 (tail – head)%(.-1)

如果不是2的整数次方,则结论不成立。

如果 m = 8;n = 7, n % m = 7; n = 15, n % m = 7; n = 23, n % m = 7;

根据%值的定义,我们只需要关注从最高位1到最后的m

对于8 ==>> 0微信:1000,即只需要关注1000的4位上位值。

这里有一个严格的证明:

如果n=0微信:1101;mask = 0 微信:1111

证明 n % mask = n & mask

根据%的定义,我们只需要关注右端12的值即可。由于mask的右端有12个1,根据&的定义,1与任意数(0或1)的运算都可以保持原值不变。所以经过n&mask操作后,右边12位对应的值仍然可以正确保持,所以

n % 掩码 = n & 掩码

下面证明如果掩码不是0微信:1111的形式,比如0微信:1111,右端第5个索引的值为0,对该索引位进行&操作。即使那个位的值为1,最后运算后也为0,改变了原来的值,所以只有mask不是2的幂-1的整数源码,n % mask = n & mask才会成立,否则不会成立的,为什么,数组的大小应该做成2的整数次方,正好利用这个特性,要知道,位运算效率很高。

以上两个属性在 中也用到了,请读者牢记。

5.3 构造器

/**
 * Constructs an empty array deque with an initial capacity
 * sufficient to hold 16 elements.
 */
public ArrayDeque() {
    elements = new Object[16];
}
/**
 * Constructs an empty array deque with an initial capacity
 * sufficient to hold the specified number of elements.
 *
 * @param numElements  lower bound on initial capacity of the deque
 */
public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
/**
 * Constructs a deque containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.  (The first element returned by the collection's
 * iterator becomes the first element, or front of the
 * deque.)
 *
 * @param c the collection whose elements are to be placed into the deque
 * @throws NullPointerException if the specified collection is null

*/ public ArrayDeque(Collection c) { allocateElements(c.size()); addAll(c); }

上面已经详细分析了这个函数的作用,所以整个构造函数应该很容易理解。

5.4 加尾

/**
 * Inserts the specified element at the end of this deque.
 *
 * 

This method is equivalent to {@link #addLast}. * * @param e the element to add * @return {@code true} (as specified by {@link Collection#add}) * @throws NullPointerException if the specified element is null */ public boolean add(E e) { addLast(e); return true; } /** * Inserts the specified element at the end of this deque. * *

This method is equivalent to {@link #add}. * * @param e the element to add * @throws NullPointerException if the specified element is null */ public void addLast(E e) { if (e == null) throw new NullPointerException(); elements[tail] = e; if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); } /** * Doubles the capacity of this deque. Call only when full, i.e., * when head and tail have wrapped around to become equal. */ private void doubleCapacity() { assert head == tail; int p = head; int n = elements.length; int r = n - p; // number of elements to the right of p int newCapacity = n << 1; if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big");

Object[] a = new Object[newCapacity]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements = a; head = 0; tail = n; }

[尾巴] = e;

就是把当前元素添加到队列的尾部位置,当然需要让尾部指向下一个位置

分析这段(tail = (tail + 1) & (. – 1)) == head

tail = (tail + 1) & (. – 1) 是让tail指向循环队列的下一个位置

(tail + 1) & (. – 1) == head 表示队列已满,需要扩容。

下面重点分析一下扩展的过程。下图形象地表达了这4行代码的意图。

int r = n - p; // number of elements to the right of p
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);

让我们看一个例子。假设原来的长度是8,头尾都是4,现在开始扩充数组,扩充后的长度是16,具体结构如下图所示:

5.5 头部添加

/**
 * Inserts the specified element at the front of this deque.
 *
 * @param e the element to add
 * @throws NullPointerException if the specified element is null
 */
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

在head处添加,让head指向之前的位置,给head的位置赋值。head 的前一个位置是 (head – 1) & (. – 1)。开始时,head 为 0,如果 . 是 8,那么 (head – 1) & (. – 1) 将得到 7。

例如执行以下代码

Deque queue = new ArrayDeque(7);
queue.addFirst("a");
queue.addFirst("b");

执行后的结果如下图所示

5.6 头部删除

/**
 * @throws NoSuchElementException {@inheritDoc}
 */
public E removeFirst() {
    E x = pollFirst();
    if (x == null)
        throw new NoSuchElementException();
    return x;
}

public E pollFirst() { int h = head; @SuppressWarnings("unchecked") E result = (E) elements[h]; // Element is null if deque empty if (result == null) return null; elements[h] = null; // Must null out slot head = (h + 1) & (elements.length - 1); return result; }

比较简单,就是让原来的head置为null,让head指向下一个位置,下一个位置就是

(h + 1) & (. – 1);

就是让头部顺时针旋转。为避免读者混淆,特贴出此图

5.7 视长

/**
 * Returns the number of elements in this deque.
 *
 * @return the number of elements in this deque
 */
public int size() {
    return (tail - head) & (elements.length - 1);
}

经过前面的分析,很明显

5.8 检查给定元素是否存在

/**
 * Returns {@code true} if this deque contains the specified element.
 * More formally, returns {@code true} if and only if this deque contains
 * at least one element {@code e} such that {@code o.equals(e)}.
 *
 * @param o object to be checked for containment in this deque
 * @return {@code true} if this deque contains the specified element
 */
public boolean contains(Object o) {
    if (o == null)
        return false;
    int mask = elements.length - 1;
    int i = head;
    Object x;
    while ( (x = elements[i]) != null) {
        if (o.equals(x))
            return true;
        i = (i + 1) & mask;
    }
    return false;
}

 int mask = elements.length - 1;
 int i = head;
 i = (i + 1) & mask;

上面3行代码是从头到尾遍历比较,当元素为null时,遍历结束,因为中间的元素不能为null。我 = (i + 1) & 面具; 就是让我指向下一个位置。


© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容