odoo源码分析,redis源码分析

JAVA Queue

第一篇博客，希望以后每天坚持
目录：
1.Queue接口
2.Java中Queue接口方法
3.Queue的子类PriorityQueue分析
4.总结

1.Queue接口
数据结构中的队列，先进先出式的数据结构。
主要注意的时，Java中的Queue是比数据结构中理解的Queue更加灵活。这表现在：
a.数据结构中的Queue是按时间顺序的先进先出，即你先插入的元素总是先出的。但是JAVA中的Queue确实运行你实现自己的策略，确定什么元素是“优先”的，如它的value值模拟“它的达到时间”，value越大，则优先级越高，越排在前面。当前你也可以按照自然的常理的时间顺序。（注意：你确定了你的策略之后，就不可变了，不能一会说按照时间顺序，一会按照value倒叙）
b.比通常的queue多了一个方法peek，你可以查看却不删除，根据当前的值，觉得你的操作。

2.Java中Queue接口方法
六个：
a:add(E e):添加一个元素
b:remove():删除一个元素
c:offer(E e):添加一个元素
d:poll(E e):删除一个元素
f: element() ：查看最上一个元素
h:peek():查看最上一个元素
上面六个函数总体上分为两类：安全的会进行容量检查的（add,remove,element）,如果队列没有值，则取元素会抛出IlleaglStatementException异常。不安全的不进行容量控制的(offer,poll,peek )。

既然是这样，为什么要有两条语句相同的一个安全、不个不安全的呢？只提供一套安全的不久可以了么？

我的理解：有时候需要通过抛出异常来判断是容器中包涵null还是没有值。Queue通常不允许插入null值元素。但是有的实现却是允许插入null值的，如LinkedList.
另外，这里的分类不是严格的，并不是说所有queue的子类的add方法都会进行容量检查，然后抛出异常。这是要看容器的特性的，如Priorityqueue是无界的，add方法是直接的调用的offer方法。

3.Queue的子类PriorityQueue分析
3.1主要的方法成员
private static final int DEFAULT_INITIAL_CAPACITY = 11;
transient Object[] queue; // non-private to simplify nested class access

/** * The number of elements in the priority queue. */private int size = 0;/** * The comparator, or null if priority queue uses elements' * natural ordering. */private final Comparator<? super E> comparator;/** * The number of times this priority queue has been * <i>structurally modified</i>. See AbstractList for gory details. */transient int modCount = 0; // non-private to simplify nested class access

说明：PriorityQueue使用数组存储数据，基于数组形式的小根堆来做的。

3.2主要方法分析
a.构造方法

public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) { // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); //数组的大小，直接看用户指定的initialCapacity，没有指定就是默认值11 //区别于Map类型的，是2^n次方。 this.queue = new Object[initialCapacity]; this.comparator = comparator;}

注意：PriorityQueue是在构造函数调用阶段就已经申请了底层数组，而有的容器如HashMap是采用的懒加载机制，在实际的使用的时候，才会真正的去申请底层的数据空间（可能原因：hashmap是一个比较费空间的，因为来避免碰撞，获得较好的性能，则一般需要申请较大的底层数组，所以这种开销大的动作能推迟就推迟，而Queue在默认的没有指定初始容量的时候，只申请了长度为11的数组，开销较小。不过ArrayList在没有指定初始化容量的时候，也是采用的类似懒加载机制，指向一个长度为0的空数组，真正使用的时候才创建底层数组的空间，关于ArrayList其他的容器在以后再说）

b.添加元素
add方法：直接调用offer(E)方法
offer方法：
比较简单，因为priorityQueue是无界队列，所以，添加元素不会抛出illegalStateException异常。如果当前数组已满，则会直接扩容。
过程：
a：安全性检查，不运行插入null元素
b：容量检查，如果容量不够，则扩容。扩容原则：如果当前基层数组较小，则扩容时，每次扩展一倍。之后每次扩容时，每次扩展0.5倍
c.如果当前队列为空，则直接插入到queue[0]位置，不需要调整。否则，将元素直接“放到”一个有效位置上，然后调整，不断上浮。

public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else siftUp(i, e); return true;}

上浮函数：不断的为新节点找位置，最后找到位置后，才赋值一次。

private void siftUpComparable(int k, E x) {//父亲节点N,孩子节点2*N+1,2(N+1),则孩子节点编号k,父亲节点为(k - 1) >>> 1。0位置//也是存数据的 Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = key;}

c.删除元素
remove函数：主要还是调用的poll函数，只是增加了异常处理（属于装饰器模式么？）

public E remove() { E x = poll(); if (x != null) return x; else throw new NoSuchElementException();}

poll函数：
主要步骤：
a.容量检查
b.size标志减一，同时保存堆顶元素。
c.将最后一个元暂时提到堆顶位置，然后将堆顶元素调整，下移。

public E poll() { if (size == 0) return null; int s = --size; modCount++; E result = (E) queue[0]; E x = (E) queue[s]; queue[s] = null; if (s != 0) siftDown(0, x); return result;} private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>)x; int half = size >>> 1; // loop while a non-leaf while (k < half) { int child = (k << 1) + 1; // assume left child is least Object c = queue[child]; int right = child + 1; //C为左右孩子中最小的 if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; //如果key小于孩子，则不用调整的，否则，需要下移，孩子上移 if (key.compareTo((E) c) <= 0) break; //孩子上移 queue[k] = c; k = child; } queue[k] = key;}

d.清除元素
特别要注意的地方：要清楚引用，不能只是将size置位0，这样的话会造成内存泄漏

public void clear() { modCount++; //清楚引用，不能只是将size置位0，这样的话会造成内存泄漏 for (int i = 0; i < size; i++) queue[i] = null; size = 0;}

3.3其他
a.堆化函数
如果在构造PriorityQueue时，使用一个非priorityqueue集合初始queue，则策略是先将集合中的元素拷贝到底层的数组中，然后调用堆化函数调整元素顺序，使满足堆的性质。
过程：
调整非叶子点[0 , 2/size-1]之间的。

private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]);}

4.总结
a:priorityqueue是无界队列
b:和其他集合容器一样，构造时，尽量大概估计容器大小
c:不允许null元素

marginUsinguseState()withanobjectasstate