- 浏览: 249404 次
- 性别:
- 来自: 北京
博客专栏
-
Java并发包源码解析
浏览量:98110
最新评论
-
746238836:
整个RingBuffer内部做了大量的缓存行填充,前后各填充了 ...
disruptor-3.3.2源码解析(2)-队列 -
xiangshouxiyang:
群加不了。。。
Jdk1.7 ForkJoin框架源码解析汇总 -
有贝无患:
acquire方法里面为什么tryAcquire会被调用多次 ...
Jdk1.6 JUC源码解析(6)-locks-AbstractQueuedSynchronizer -
zwy_qz:
library_call.cpp 里面的内联操作 inline ...
Jdk1.6 JUC源码解析(1)-atomic-AtomicXXX -
sunwang810812:
您好,正在学习您的文章,中间有一段,一直没明白:“privat ...
Jdk1.6 JUC源码解析(6)-locks-AbstractQueuedSynchronizer
表、栈和队列是三种基本的数据结构,前面总结的ArrayList和LinkedList可以作为任意一种数据结构来使用,当然由于实现方式的不同,操作的效率也会不同。
这篇要看一下java.util.ArrayDeque。从命名上看,它是一个由数组实现的双端队列。还是先看一下它实现了哪些接口。
先读了一下类注释,大概是说,java.util.ArrayDeque是Deque接口的动态数组实现,容量会按需扩展,线程不安全。作为栈使用比java.util.Stack快,作为队列使用比java.util.LinkedList快。大多数的操作消耗常数时间。主要特性就是这些。
在读源码之前,还是先想一下,如果自己实现会怎么做。首先一定是有一个内部数组用来保存数据;既然是队列,那内部应该有2个指针分别指向首尾,对队列两端的操作可以通过首尾指针的移动来快速进行,可以通过首位指针的位置来算出队列的元素个数等等,大概想法是这样,当然一些细节问题还没考虑。有了大体上的思路,来看下java.util.ArrayDeque的源码吧。
可以看到,基本上是这样。最后一个常量表示初始化的最小容量,注释说明这个值必须是2的幂,这是为什么??先记住这个问题,继续往下看。
一共有3个构造方法。无参的构造方法会创建长度为16的内部数组。接受一个集合的构造方法不用多说了,看一下接受“元素数量”的构造方法,里面会调一个分配内部数组空间的方法。
这个方法是根据给定numElements来进行内部数组空间的分配。这里有一个前提,容量必须是2的幂,尽管现在还不知道为什么必须是2的幂,但先往下看。可以看到如果numElements小于最小容量8的话,就会按最小容量来分配数组空间。如果大于等于8,会到一个条件语句中做一些操作,看下这些操作是干嘛的。我们知道如果一个2进制数是2的幂,那么它的特点就是只有一位是1。
观察代码里有个initialCapacity++,我们可以想到如果一个二进制数+1得到的数是2的幂,如果这个数不是0,那么它的所有位一定都是1。
所以看下前面的操作,numElements和numElements逻辑右移1位后的数进行或操作,然后赋给numElements。如果把numElements用二进制来表示,相当于把numElements中是1的最高位右边的一位变成1;接下来和numElements逻辑右移2位后的数进行与操作,相当于把最初numElements后面的第三位第四位变成1。。。依次类推,最终会将最高位1右边的31位都变成1(如果有这么多位的话)。
总之上面的操作是要得到大于numElements的最小的2的幂。当然要考虑溢出情况,所以当处理后的numElements小于0时(其实只有一种情况就是10000000000000000000000000000000),将numElements逻辑右移1位,变成2的30次方。
接下来看下操作方法。
看一下最上面的注释,看来只要重点瞅瞅addFirst,addLast, pollFirst, pollLast这几个方法就行了。
先看看addFirst方法,这方法里最怪异就是head = (head - 1) & (elements.length - 1)这句了。仔细分析一下,既然head相当于一个指针,那么不管head向那个方向移动,它总会移动到内部数组的一端,那么下一次移动它应该绕回到另一端,形成一个回环。幸运的是,当插入第一个值的时候,正好是“绕回”的逻辑。因为这时head默认值是0,head-1就是-1,看到-1我们马上回想到一大串1吧(除非你不知道Java是用补码的。。),-1和一个数做“与”操作结果就是那个数喽,所以这里的结果就是elements.length - 1。
看到这里会发现,head指针是从后往前的。继续,假设elements.length等于8,elements.length - 1就是7,插入第二个元素的时候,head是7了。再算一下刚才那个表达式,(7-1)&7=6,果然是这样,head又从后往前行进一位。考虑一下为什么要这样写,因为head要从后往前移动,所以每次减1。设想一下,如果head大于1,那么head-1%elements.length也能完成上面的工作。再想一下,如果elements.length是2的幂,那么elements.length-1的二进制形式不就是一串0就加上一串1么,head-1再和这个数做&操作不正好就是head-1(当head>1时)。其实当a是2的幂的时候,b%a可以写成b&(a-1),而且&操作要比%操作性能好一点点。况且,这样写也正好能使得当head=0时移动到数组尾部。
好了,再看看addLast方法。
addLast先赋值,后移动指针。这点和addFirst不一样。具体的移动方式类似。可以想象,head是从后往前移动,tail从前往后移动。当他们相遇的时候,说明内部数组里已经放满了元素。这时候该扩容啦。
基本上就是内部数组的容量扩充到之前的2倍,还能保证长度是2的幂。然后是数组的拷贝及指针的重定位。
有了前面addFirst和addLast的分析,pollFirst和pollLast也很容易看懂了,只是逆过程而已。
ok,代码分析到这里,其他部分也应该很容易看懂。看来程序中如果有用到简单的栈或者队列的地方,可以考虑下这个类喽!
这篇要看一下java.util.ArrayDeque。从命名上看,它是一个由数组实现的双端队列。还是先看一下它实现了哪些接口。
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable {
先读了一下类注释,大概是说,java.util.ArrayDeque是Deque接口的动态数组实现,容量会按需扩展,线程不安全。作为栈使用比java.util.Stack快,作为队列使用比java.util.LinkedList快。大多数的操作消耗常数时间。主要特性就是这些。
在读源码之前,还是先想一下,如果自己实现会怎么做。首先一定是有一个内部数组用来保存数据;既然是队列,那内部应该有2个指针分别指向首尾,对队列两端的操作可以通过首尾指针的移动来快速进行,可以通过首位指针的位置来算出队列的元素个数等等,大概想法是这样,当然一些细节问题还没考虑。有了大体上的思路,来看下java.util.ArrayDeque的源码吧。
/** * 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. */ private transient E[] elements; /** * 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. */ private 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)). */ private transient int tail; /** * The minimum capacity that we'll use for a newly created deque. * Must be a power of 2. */ private static final int MIN_INITIAL_CAPACITY = 8;
可以看到,基本上是这样。最后一个常量表示初始化的最小容量,注释说明这个值必须是2的幂,这是为什么??先记住这个问题,继续往下看。
/** * Constructs an empty array deque with an initial capacity * sufficient to hold 16 elements. */ public ArrayDeque() { elements = (E[]) 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 <i>front</i> 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<? extends E> c) { allocateElements(c.size()); addAll(c); }
一共有3个构造方法。无参的构造方法会创建长度为16的内部数组。接受一个集合的构造方法不用多说了,看一下接受“元素数量”的构造方法,里面会调一个分配内部数组空间的方法。
/** * Allocate empty array to hold the given number of elements. * * @param numElements the number of elements to hold */ private void allocateElements(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; // Find the best power of two to hold elements. // Tests "<=" because arrays aren't kept full. if (numElements >= initialCapacity) { initialCapacity = numElements; initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements } elements = (E[]) new Object[initialCapacity]; }
这个方法是根据给定numElements来进行内部数组空间的分配。这里有一个前提,容量必须是2的幂,尽管现在还不知道为什么必须是2的幂,但先往下看。可以看到如果numElements小于最小容量8的话,就会按最小容量来分配数组空间。如果大于等于8,会到一个条件语句中做一些操作,看下这些操作是干嘛的。我们知道如果一个2进制数是2的幂,那么它的特点就是只有一位是1。
2^0 = 1 2^1 = 10 2^n = 10000...(n个0)
观察代码里有个initialCapacity++,我们可以想到如果一个二进制数+1得到的数是2的幂,如果这个数不是0,那么它的所有位一定都是1。
2^1 = 1 + 1 2^3 = 111 + 1 2^n = 111...(n个1) + 1
所以看下前面的操作,numElements和numElements逻辑右移1位后的数进行或操作,然后赋给numElements。如果把numElements用二进制来表示,相当于把numElements中是1的最高位右边的一位变成1;接下来和numElements逻辑右移2位后的数进行与操作,相当于把最初numElements后面的第三位第四位变成1。。。依次类推,最终会将最高位1右边的31位都变成1(如果有这么多位的话)。
10000000000000000000000000000000 经过上面操作变成 11111111111111111111111111111111
总之上面的操作是要得到大于numElements的最小的2的幂。当然要考虑溢出情况,所以当处理后的numElements小于0时(其实只有一种情况就是10000000000000000000000000000000),将numElements逻辑右移1位,变成2的30次方。
接下来看下操作方法。
// The main insertion and extraction methods are addFirst, // addLast, pollFirst, pollLast. The other methods are defined in // terms of these. /** * 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(); }
看一下最上面的注释,看来只要重点瞅瞅addFirst,addLast, pollFirst, pollLast这几个方法就行了。
先看看addFirst方法,这方法里最怪异就是head = (head - 1) & (elements.length - 1)这句了。仔细分析一下,既然head相当于一个指针,那么不管head向那个方向移动,它总会移动到内部数组的一端,那么下一次移动它应该绕回到另一端,形成一个回环。幸运的是,当插入第一个值的时候,正好是“绕回”的逻辑。因为这时head默认值是0,head-1就是-1,看到-1我们马上回想到一大串1吧(除非你不知道Java是用补码的。。),-1和一个数做“与”操作结果就是那个数喽,所以这里的结果就是elements.length - 1。
看到这里会发现,head指针是从后往前的。继续,假设elements.length等于8,elements.length - 1就是7,插入第二个元素的时候,head是7了。再算一下刚才那个表达式,(7-1)&7=6,果然是这样,head又从后往前行进一位。考虑一下为什么要这样写,因为head要从后往前移动,所以每次减1。设想一下,如果head大于1,那么head-1%elements.length也能完成上面的工作。再想一下,如果elements.length是2的幂,那么elements.length-1的二进制形式不就是一串0就加上一串1么,head-1再和这个数做&操作不正好就是head-1(当head>1时)。其实当a是2的幂的时候,b%a可以写成b&(a-1),而且&操作要比%操作性能好一点点。况且,这样写也正好能使得当head=0时移动到数组尾部。
好了,再看看addLast方法。
/** * Inserts the specified element at the end of this deque. * * <p>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(); }
addLast先赋值,后移动指针。这点和addFirst不一样。具体的移动方式类似。可以想象,head是从后往前移动,tail从前往后移动。当他们相遇的时候,说明内部数组里已经放满了元素。这时候该扩容啦。
/** * Double 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 = (E[])a; head = 0; tail = n; }
基本上就是内部数组的容量扩充到之前的2倍,还能保证长度是2的幂。然后是数组的拷贝及指针的重定位。
有了前面addFirst和addLast的分析,pollFirst和pollLast也很容易看懂了,只是逆过程而已。
ok,代码分析到这里,其他部分也应该很容易看懂。看来程序中如果有用到简单的栈或者队列的地方,可以考虑下这个类喽!
发表评论
-
Jdk1.6 Collections Framework源码解析(12)-TreeMap、TreeSet
2016-01-03 16:06 2098Jdk1.6 Collections Framework ... -
Jdk1.6 Collections Framework源码解析(11)-EnumSet
2015-12-29 18:25 1775Jdk1.6 Collections Framework源 ... -
Jdk1.6 JUC源码解析(26)-ConcurrentSkipListMap、ConcurrentSkipListSet
2015-11-03 03:08 5267Jdk1.6 JUC源码解析(26)-Concurrent ... -
Jdk1.6 JUC源码解析(25)-ConcurrentHashMap
2015-10-30 19:02 2484Jdk1.6 JUC源码解析(25)-Co ... -
Jdk1.6 集合框架源码解析汇总
2015-10-29 22:05 3385Jdk1.6 集合框架源码解析汇总 非并发: ... -
Jdk1.6 JUC源码解析(24)-ConcurrentLinkedQueue
2015-10-29 19:02 1839Jdk1.6 JUC源码解析(24)-ConcurrentL ... -
Jdk1.6 JUC源码解析(23)-CopyOnWriteArrayList、CopyOnWriteArraySet
2015-10-29 18:55 1747Jdk1.6 JUC源码解析(23)-Cop ... -
Jdk1.6 JUC源码解析(22)-LinkedBlockingDeque
2015-10-29 18:47 1541Jdk1.6 JUC源码解析(22)-LinkedBloc ... -
Jdk1.6 JUC源码解析(18)-DelayQueue
2015-10-27 19:25 2301Jdk1.6 JUC源码解析(18)-DelayQueue ... -
Jdk1.6 JUC源码解析(15)-SynchronousQueue
2015-10-26 19:19 2500Jdk1.6 JUC源码解析(15)-Synchronou ... -
Jdk1.6 JUC源码解析(14)-PriorityBlockingQueue
2015-10-25 03:22 2243Jdk1.6 JUC源码解析(14)-Pr ... -
Jdk1.6 JUC源码解析(13)-LinkedBlockingQueue
2015-10-24 22:28 1781Jdk1.6 JUC源码解析(13)-LinkedBloc ... -
Jdk1.6 JUC源码解析(12)-ArrayBlockingQueue
2015-10-23 20:03 2124Jdk1.6 JUC源码解析(12)-Ar ... -
Jdk1.6 Collections Framework源码解析(10)-EnumMap
2013-09-09 14:55 1436看这个类之前,先看一下Java的枚举——Enu ... -
Jdk1.6 Collections Framework源码解析(9)-PriorityQueue
2013-09-03 20:37 2032开发中有时会遇到这样的情况。要求某个调度器去调 ... -
Jdk1.6 Collections Framework源码解析(8)-WeakHashMap
2013-09-02 11:43 2024总结这个类之前,首先看一下Java引用的相关知 ... -
Jdk1.6 Collections Framework源码解析(7)-HashSet、LinkedHashSet
2013-08-28 11:34 1613本篇总结一 ... -
Jdk1.6 Collections Framework源码解析(6)-IdentityHashMap
2013-08-27 14:10 1562这篇总结一下java.util.Identit ... -
Jdk1.6 Collections Framework源码解析(5)-LinkedHashMap
2013-08-20 14:28 1742前面总结了java.util.HashMap, ... -
Jdk1.6 Collections Framework源码解析(4)-HashMap
2013-08-19 13:59 1939开发中常常 ...
相关推荐
NULL 博文链接:https://brokendreams.iteye.com/blog/1916061
aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-15.8.0-jdk1.6aspose-words-...
1.okhttp3.8源码使用jdk1.6重新编译,已集成了okio,在javaweb项目中使用,未在安卓项目中使用 2.okhttp3.8源码使用jdk1.6重新编译_okhttp3.8.0-jdk1.6.jar
JDK 1.6 64位(jdk-6u45-windows-x64(1.6 64))
2部分: jdk-1.6-windows-64-01 jdk-1.6-windows-64-02
java环境搭建 jdk6(包含jre)64位 jdk-6u45-windows-x64
三部分: jdk-1.6-linux-64-1 jdk-1.6-linux-64-2 jdk-1.6-linux-64-3
JDK-1.6-Windows-32位 纯官方安装版 JDK-1.6-Windows-32位 纯官方安装版
三部分: jdk-1.6-linux-64-1 jdk-1.6-linux-64-2 jdk-1.6-linux-64-3
jdk1.6-jdk-6u43-windows32-i586
三部分: jdk-1.6-linux-64-1 jdk-1.6-linux-64-2 jdk-1.6-linux-64-3
logback-cfca-jdk1.6-3.1.0.0.jar
1、okhttp3.8源码使用jdk1.6重新编译,已集成了okio,仅在javaweb项目中使用。 2、另附json-20160810.jar
jdk1.6 源码
jdk-1.6-linux-32-1 jdk-1.6-linux-32-2 jdk-1.6-linux-32-3
解决JDK1.6下的Base64报错问题,资源文件里有jar包,及替换方法
适用平台:windows x64 jdk版本:1.6 安装方式:双击安装即可
三部分: jdk-1.6-windows-32-1 jdk-1.6-windows-32-2 jdk-1.6-windows-32-3
jdk1.6,jdk1.7,jdk1.8以及jre1.6,jre1.7,jre1.8
jdk-1.6-linux-32-1 jdk-1.6-linux-32-2 jdk-1.6-linux-32-3