深入源码看数据结构(再探集合框架)

从源码的高度来看看集合中各个实现类的是如何组织我们存进去的数据的，主要包括Java类库中提供的几个具体的类：?
LinkedList?
ArrayList?
HashMap?
HashSet?
TreeMap?
TreeSet?
PriorityQueue（顺序按下面的讲解顺序）?

-----------------------------------------------------------------?
1、java.util.LinkedList<E>?
当我们创建一个LinkedList类的对象，并且试图增加一个新的元素的时候，到底是如何组织我们传进去的数据的呢？?

?

这里解释一下，这个图的最左边的一些就是上面源码中的table也就是HashMap的一个属性Entry[] table。
将一个新的键值对插入需要经过这几步：?
---给key值计算哈码（计算在这一步int hash = hash(key.hashCode());），?
??? ---得出在table数组的中index：int i = indexFor(hash, table.?
length);?
---将键值对插入index确定的上图所示的一个横向的链表中。如果在这个链表中有要插入的pair的key经过hashcode()的
一系列运算和equals()的一系列运算相同的元素，就替换原来的value。（这也就是我们自己定义的类要用到HashMap
存储的时候，必须重写hashcode()和equals()方法，并且要保证对同一对象两个方法计算结果要相同的原因。
因为如果不相同，在一个同一对象为key插入值的时候就不会像你期望的那样后插入的value覆盖前面的value了，
而是会重新开辟一个空间存储）?

于是，到这里我们明白了，原来HashMap就是通过散列表这种数据结构组织数据的！?


-----------------------------------------------------------------?
4、java.util.HashSet<E>?


public boolean add(E e) {        return offer(e);}public boolean offer(E e) {//前面这的几行无非就是判断非空，判断本类的属性queue的长度是否够用然后做相应调整        if (e == null)            throw new NullPointerException();        modCount++;        int i = size;        if (i >= queue.length)            grow(i + 1);        size = i + 1;//最后终于要将元素插进去了//如果queue空就插在index为0的位置，很好理解//否则调用siftUp()方法（第一个参数是the position to fill,第二个参数是the element to insert）        if (i == 0)            queue[0] = e;        else            siftUp(i, e);        return true;}//再来看看siftUp()方法是如何实现的//api文档的注释的意思是：将x插入合适的位置保持heap的有序性不变//排序标准有两种途径获取：//1、在构造PriorityQueue的时候传入的Comparator ，这个优先选用//2、 要插入的x自己实现的compareTo方法private void siftDown(int k, E x) {        if (comparator != null)            siftDownUsingComparator(k, x);        else            siftDownComparable(k, x);}//这里我只需分析comparator的情况就可以了private void siftUpUsingComparator(int k, E x) {//最坏的情况是：我找了一圈发现x才是整棵树种最小的。这时k为0，也就是到达整个堆的最小的元素（或者整棵树的根节点），停止循环。        while (k > 0) {//第一句的意思是获得要插入的这个k位置在queue中对应的父元素的索引//我可以告诉大家这个式子的计算结果是：queue[n]节点的子节点是queue[2*n+1]和queue[2*(n+1)]            int parent = (k - 1) >>> 1;            Object e = queue[parent];//如果比较规则确定x"大于"父节点，就插在k位置了，跳出循环            if (comparator.compare(x, (E) e) >= 0)                break;//如果发现x较小，就将父节点的元素移到这个k位置            queue[k] = e;            k = parent;//现在要插入的位置变为原来父节点的位置        }        queue[k] = x;//}

嗯，这个类用了一种“堆”（逻辑上是二叉树，存储上用数组，树中的元素有大小关系，越小在数组中的index也越小）
的数据结构。?
典型应用是存储有优先级的任务，因为每次调用remove移除最小的元素（优先级最高的元素），都会自动排序，
保证每次移除的都是优先级最高的任务。 同样，TreeMap逻辑上也是通过有序二叉树来组织数据的，不过，TreeMap通过节点的链接来组织存储结构， 而PriorityQueue是通过数组的一些列计算确定逻辑上的树的节点的存放位置。