内容有序的集合之 ProrityQueue
2017-09-30 本文已影响30人
Frank_Kivi
大家可能都知道，List是有序的，Set是无序的。其中ArrayList是使用数组实现的，ArrayList实现了RandomAccess使其可以根据位置快速访问。HashSet的实现原理大家可以参阅 Set去重原理
HashSet是可以去重的。
大家可能有这样的需求，一堆元素放入集合之后，我们想要让元素本身有顺序，比如元素进入的时候是以63279，我们想要集合能够变成23679，这样方便我们使用，为了能把两种有序区分开来 ，我们把ArrayList叫做访问有序，而ProrityQueue是内容有序。当然数组有Arrays.sort(),List有Collecctions.sort()。还有其它方法吗？今天就给大家介绍ProrityQueue。
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
private static final long serialVersionUID = -7720805057305804111L;
private static final int DEFAULT_INITIAL_CAPACITY = 11;
<!--真正存储数据的数组-->
transient Object[] queue; // non-private to simplify nested class access
<!--数据的长度-->
private int size = 0;
<!--比较器-->
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
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
<!--最终被调用的构造-->
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();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
<!--当是从一个内容有序的构建时，直观理解是直接复制即可，调用的是 initElementsFromCollection-->
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
<!--当是从一个内容有序的构建时，直观理解是直接复制即可，调用的是 initFromPriorityQueue，我们可以得到一个信息PriorityQueue不是SortedSet-->
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
<!--如果不是内容有序的就调用initFromCollection-->
this.comparator = null;
initFromCollection(c);
}
}
@SuppressWarnings("unchecked")
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
@SuppressWarnings("unchecked")
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}
private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
// If c.toArray incorrectly doesn't return Object[], copy it.
if (a.getClass() != Object[].class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new NullPointerException();
this.queue = a;
this.size = a.length;
}
private void initFromCollection(Collection<? extends E> c) {
<!--现在我们明白了，initElementsFromCollection就是复制元素，而heapify就是对其进行排序-->
initElementsFromCollection(c);
heapify();
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
@SuppressWarnings("unchecked")
private void heapify() {
<!--循环遍历前边的一半元素，然后调用siftDown方法，其内部是使用二叉树来管理的，i的左孩子在2i-1,i的右孩子在2i-->
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
private void siftDown(int k, E x) {
两个基本一样，我们找一个来分析，siftDownComparable
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
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) {
<!--前边调用的地方，k恰好比half小1，k*2恰好是size-2,所以child是其size-1，恰好是他的左孩子-->
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
<!--right是它的右孩子-->
int right = child + 1;
<!--如果左孩子比右孩子大说明需要调整-->
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
<!--对c进行赋值，让其是后边两个节点的小值-->
如果右边比左边大，这里不走，最后交换的就是k和左节点，如果右边比左边小，最后交换的是k和右节点
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
<!--当前元素和c比较，如果比c小，就结束循环-->
break;
<!--交换k和c的元素-->
queue[k] = c;
k = child;
}
queue[k] = key;
}
答案并不是完全的正序，这是为什么呢。
我们再来看下siftDown的注释，它的作用是使当前的元素插入队列，最后它比它的子节点小或者相等，或者它本身是个叶子节点。所以我们在构造的时候就是让左边一半调用，假设有6个元素，先保证了2是25中最小的，1是34中最小的，0是12中最小的，0就是最小。所以最后第一个元素是最小的。
<!--非常清楚的说了，使用iterator并不保证顺序-->
/**
* Returns an iterator over the elements in this queue. The iterator
* does not return the elements in any particular order.
*
* @return an iterator over the elements in this queue
*/
public Iterator<E> iterator() {
return new Itr();
}
我们先来看offer方法
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
<!--长度+1，保证可以存储-->
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
<!--最重要的方法-->
siftUp(i, e);
return true;
}
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
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;
}
分析过程和前边的sfitDown类似，它能保证从k找它的父节点，一直到队列的开始，这些节点都是有序的，所以最开始的还是最小的。
<!--使用poll可以保证有序-->
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;
}
移除一个后，马上调用siftDown，传的是0,它能保证从0开始到它的叶子结点，0的子结点如果还有子结点就继续比较，在这一系列中，0位置的是最小的，所以最后又保证了下次调用的时候还是有序的。
SVN和git
是时候放弃HashMap了-SparseArray和ArrayMap源码分析
SparseArray
ArrayMap的实现原理
system类
object类。
FragmentStatePagerAdapter save restore FM getFragmet和putFragment;
viewpager的
@Override
public Parcelable onSaveInstanceState() {
Parcelable superState = super.onSaveInstanceState();
SavedState ss = new SavedState(superState);
ss.position = mCurItem;
if (mAdapter != null) {
ss.adapterState = mAdapter.saveState();
}
return ss;
}
@Override
public void onRestoreInstanceState(Parcelable state) {
if (!(state instanceof SavedState)) {
super.onRestoreInstanceState(state);
return;
}
SavedState ss = (SavedState) state;
super.onRestoreInstanceState(ss.getSuperState());
if (mAdapter != null) {
mAdapter.restoreState(ss.adapterState, ss.loader);
setCurrentItemInternal(ss.position, false, true);
} else {
mRestoredCurItem = ss.position;
mRestoredAdapterState = ss.adapterState;
mRestoredClassLoader = ss.loader;
}
}
双进程问题
