master

分支 (1)

管理

管理

master

leocook-private
/
16923736135980.html

<!doctype html>
<html class="no-js" lang="en">
  <head>
    <meta charset="utf-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>

  2. JCF（Java 集合） -

  </title>
 <meta name="description" content="">
 <link href="atom.xml" rel="alternate" title="" type="application/atom+xml">
    <link rel="stylesheet" href="asset/css/foundation.min.css" />
    <link rel="stylesheet" href="asset/css/docs.css" />

    <script src="asset/js/vendor/modernizr.js"></script>
    <script src="asset/js/vendor/jquery.js"></script>
    <script src="asset/highlightjs/highlight.pack.js"></script>
    <link href="asset/highlightjs/styles/github.css" media="screen, projection" rel="stylesheet" type="text/css">
    <script>hljs.initHighlightingOnLoad();</script>

  </head>
  <body class="antialiased hide-extras">

    <div class="marketing off-canvas-wrap" data-offcanvas>
      <div class="inner-wrap">


<nav class="top-bar docs-bar hide-for-small" data-topbar>

<div id="header">
    <h1><a href="index.html"></a></h1>
</div>

</nav>
        <nav class="tab-bar show-for-small">
  <a href="javascript:void(0)" class="left-off-canvas-toggle menu-icon">
    <span> &nbsp; </span>
  </a>
</nav>

<aside class="left-off-canvas-menu">
      <ul class="off-canvas-list">
      <li><a href="index.html">Home</a></li>

        <li class="divider"></li>
        <li><label>1. Java 基础</label></li>


            <li><a title="1. Java 基础" href="16923474457318.html">1. Java 基础</a></li>


        <li class="divider"></li>
        <li><label>2. JCF（Java 集合）</label></li>


            <li><a title="2. JCF（Java 集合）" href="16923736135980.html">2. JCF（Java 集合）</a></li>

            <li><a title="2.4. Map - HashSet & HashMap 源码解析" href="16924335832240.html">2.4. Map - HashSet & HashMap 源码解析</a></li>

            <li><a title="2.5. Map - LinkedHashSet & LinkedHashMap源码解析" href="16924372183713.html">2.5. Map - LinkedHashSet & LinkedHashMap源码解析</a></li>

            <li><a title="2.6. Map - TreeSet & TreeMap 源码解析" href="16925007307182.html">2.6. Map - TreeSet & TreeMap 源码解析</a></li>


        <li class="divider"></li>
        <li><label>mysql</label></li>


            <li><a title="事务隔离" href="16925938083498.html">事务隔离</a></li>


        <li class="divider"></li>
        <li><label>常见文档</label></li>


            <li><a title="Paxos选举算法" href="16926055818559.html">Paxos选举算法</a></li>


      </ul>
    </aside>

<a class="exit-off-canvas" href="#"></a>

        <section id="main-content" role="main" class="scroll-container">

          <div class="row">
            <div class="large-3 medium-3 columns">
              <div class="hide-for-small">
                <div class="sidebar">
                <nav>
                  <ul id="side-nav" class="side-nav">


                      <li class="side-title"><span>1. Java 基础</span></li>

                          <li><a title="1. Java 基础" href="16923474457318.html">1. Java 基础</a></li>


                      <li class="side-title"><span>2. JCF（Java 集合）</span></li>

                          <li><a title="2. JCF（Java 集合）" href="16923736135980.html">2. JCF（Java 集合）</a></li>

                          <li><a title="2.4. Map - HashSet & HashMap 源码解析" href="16924335832240.html">2.4. Map - HashSet & HashMap 源码解析</a></li>

                          <li><a title="2.5. Map - LinkedHashSet & LinkedHashMap源码解析" href="16924372183713.html">2.5. Map - LinkedHashSet & LinkedHashMap源码解析</a></li>

                          <li><a title="2.6. Map - TreeSet & TreeMap 源码解析" href="16925007307182.html">2.6. Map - TreeSet & TreeMap 源码解析</a></li>


                      <li class="side-title"><span>mysql</span></li>

                          <li><a title="事务隔离" href="16925938083498.html">事务隔离</a></li>


                      <li class="side-title"><span>常见文档</span></li>

                          <li><a title="Paxos选举算法" href="16926055818559.html">Paxos选举算法</a></li>


                  </ul>
                </nav>
                </div>
              </div>
            </div>
            <div class="large-9 medium-9 columns">

 <div class="markdown-body">
<h1>2. JCF（Java 集合）</h1>

<ul>
<li>
<a href="#toc_0">2.1. Collection</a>
</li>
<li>
<a href="#toc_1">2.2. Map</a>
<ul>
<li>
<a href="#toc_2">2.2.1. JDK7 HashMap如何实现？</a>
</li>
<li>
<a href="#toc_3">2.2.2. JDK8 HashMap如何实现？</a>
</li>
<li>
<a href="#toc_4">2.2.3. HashSet是如何实现的？</a>
</li>
<li>
<a href="#toc_5">2.2.4. 什么是WeakHashMap?</a>
</li>
</ul>
</li>
<li>
<a href="#toc_6">2.3. 核心 Collection 类源码解读</a>
<ul>
<li>
<a href="#toc_7">2.3.1. Collection - ArrayList 源码解析</a>
</li>
<li>
<a href="#toc_8">2.3.2. Collection - LinkedList源码解析</a>
</li>
<li>
<a href="#toc_9">2.3.3. Collection - Stack &amp; Queue</a>
<ul>
<li>
<a href="#toc_10">Queue</a>
</li>
<li>
<a href="#toc_11">Deque</a>
</li>
</ul>
</li>
<li>
<a href="#toc_12">2.3.4. 源码解析Collection - PriorityQueue源码解析</a>
<ul>
<li>
<a href="#toc_13">方法剖析</a>
</li>
<li>
<a href="#toc_14">element()和peek()</a>
</li>
<li>
<a href="#toc_15">remove()和poll()</a>
</li>
<li>
<a href="#toc_16">remove(Object o)</a>
</li>
</ul>
</li>
</ul>
</li>
<li>
<a href="#toc_17">2.4. 核心 Map &amp; Set 源码解读</a>
<ul>
<li>
<a href="#toc_18">2.4.1. Map - HashSet &amp; HashMap 源码解析</a>
</li>
<li>
<a href="#toc_19">2.4.2. Map - LinkedHashSet&amp;Map源码解析</a>
</li>
<li>
<a href="#toc_20">2.4.3. Map - TreeSet &amp; TreeMap 源码解析</a>
</li>
<li>
<a href="#toc_21">2.4.4. Map - WeakHashMap源码解</a>
</li>
</ul>
</li>
</ul>


<p>JCF 即 Java Collections Framework，中文为：Java集合框架。<br/>
容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对(两个对象)的映射表。</p>

<h2 id="toc_0">2.1. Collection</h2>

<ul>
<li>Set

<ul>
<li>TreeSet 基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。</li>
<li>HashSet 基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。</li>
<li>LinkedHashSet 具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。</li>
</ul></li>
<li>List

<ul>
<li>ArrayList 基于动态数组实现，支持随机访问。</li>
<li>Vector 和 ArrayList 类似，但它是线程安全的。</li>
<li>LinkedList 基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。</li>
</ul></li>
<li>Queue

<ul>
<li>LinkedList 可以用它来实现双向队列。</li>
<li>PriorityQueue 基于堆结构实现，可以用它来实现优先队列。</li>
</ul></li>
</ul>

<pre><code>Fail-Fast机制：
当iterator被创建后，除了调用 Iterator#remove() 和 Iterator#add(Object) 两个方法外，任何时间只要集合的结构被改变，再调用iterator任何方法都会抛出 ConcurrentModificationException 异常。。

Fail-Fast机制的实现原理：
通过记录modCount参数来实现，在运行迭代前会把modCount赋值给expectedModCount，当发生modCount不等于expectedModCount的时候，则会抛出异常。

通常，在源码可以很容易可以观察到：
1. 当执行 modCount++ 时，表示这个方法会触发迭代器抛出 ConcurrentModificationException 异常，if (modCount != expectedModCount) throw new ConcurrentModificationException()；
2. 如果调用对集合结构做出修改的方法，方法中没有执行 modCount++ 的代码，则表示该方法不会触发迭代器抛出 ConcurrentModificationException 异常，如ListIterator#remove() 和 ListIterator#add(Object)中可以看见。

</code></pre>

<h2 id="toc_1">2.2. Map</h2>

<ul>
<li>TreeMap 基于红黑树实现。</li>
<li>HashMap 1.7基于哈希表实现，1.8基于数组+链表+红黑树。</li>
<li>HashTable 和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高(1.7 ConcurrentHashMap 引入了分段锁, 1.8 引入了红黑树)。</li>
<li>LinkedHashMap 使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用(LRU)顺序。</li>
</ul>

<h3 id="toc_2">2.2.1. JDK7 HashMap如何实现？</h3>

<p>哈希表有两种实现方式，一种开放地址方式(Open addressing)，另一种是冲突链表方式(Separate chaining with linked lists)。Java7 HashMap采用的是冲突链表方式。</p>

<p>有两个参数可以影响HashMap的性能: <br/>
capacity 容量，默认值是16；<br/>
loadFactor 负载系数,默认值是0.75;<br/>
threshold 阈值。threshold=capacity*loadFactor。默认12。当元素数量超过阈值时便会触发扩容。</p>

<h3 id="toc_3">2.2.2. JDK8 HashMap如何实现？</h3>

<p>根据 Java7 HashMap 的介绍，我们知道，查找的时候，根据 hash 值我们能够快速定位到数组的具体下标，但是之后的话，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。<br/>
为了降低这部分的开销，在 Java8 中，当链表中的元素达到了 8 个时，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。</p>

<h3 id="toc_4">2.2.3. HashSet是如何实现的？</h3>

<p>HashSet是对HashMap的简单包装，对HashSet的函数调用都会转换成合适的HashMap方法</p>

<h3 id="toc_5">2.2.4. 什么是WeakHashMap?</h3>

<p>我们都知道Java中内存是通过GC自动管理的，GC会在程序运行过程中自动判断哪些对象是可以被回收的，并在合适的时机进行内存释放。GC判断某个对象是否可被回收的依据是，是否有有效的引用指向该对象。如果没有有效引用指向该对象(基本意味着不存在访问该对象的方式)，那么该对象就是可回收的。这里的有效引用 并不包括弱引用。也就是说，虽然弱引用可以用来访问对象，但进行垃圾回收时弱引用并不会被考虑在内，仅有弱引用指向的对象仍然会被GC回收。<br/>
WeakHashMap 内部是通过弱引用来管理entry的，弱引用的特性对应到 WeakHashMap 上意味着什么呢？<br/>
WeakHashMap 里的entry可能会被GC自动删除，即使程序员没有调用remove()或者clear()方法。<br/>
WeakHashMap 的这个特点特别适用于需要缓存的场景。在缓存场景下，由于内存是有限的，不能缓存所有对象；对象缓存命中可以提高系统效率，但缓存MISS也不会造成错误，因为可以通过计算重新得到。<br/>
不是很推荐这种方式。</p>

<h2 id="toc_6">2.3. 核心 Collection 类源码解读</h2>

<h3 id="toc_7">2.3.1. Collection - ArrayList 源码解析</h3>

<p>ArrayList是基于数组实现的列表结构。</p>

<ul>
<li>底层数据结构</li>
</ul>

<pre><code>/**
 * 数组支持的最大初始容量，有的JVM需要一些header信息，预留了8个数组空间。Hotsopt不需要
 * header，最大能扩容大小到MAX_ARRAY_SIZE
 * /
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 默认的初始容量
 * /
 private static final int DEFAULT_CAPACITY = 10;

/**
 * 底层是数组实现。
 * 调用无参构造方法时创建的空数组的默认数据存储情况。
 * 当加入第一个元素时,会判断当前数组若是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，若是进行首次扩
 * 容，首次扩容的长度为DEFAULT_CAPACITY，默认值是10.
 */
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 *
 * 存储ArrayList元素的缓冲数组，ArrayList的长度就是该缓冲数组的长度。
 * 当ArrayList数据为空时，elementData值是DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
 * 当添加第一个元素时，数组长度将会被初始化为DEFAULT_CAPACITY值。
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;
</code></pre>

<ul>
<li>自动扩容</li>
</ul>

<pre><code>/**
 * 该方法确保集合容量最小是 minCapacity
 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
 * 计算集合将被扩容至多大
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //集合首次被扩容，应该扩到多大，通过查看add()方法得知：首次扩容大小是DEFAULT_CAPACITY，因为minCapacity为0
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    //非首次扩容，容器将会被扩展为指定的大小，即minCapacity。在add和addAll中有
    return minCapacity;
}

/**
 * 确保集合大小至少是 minCapacity
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 当需要的集合大小大于现在数组缓存的大小时，则需要扩容
    if (minCapacity - elementData.length &gt; 0)
        grow(minCapacity);
}

/**
 * 对集合进行扩容，保证容量至少为minCapacity
 *
 * @param 期望的最小容量。
 */
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;

    //新的容量扩展为之前的1.5倍
    int newCapacity = oldCapacity + (oldCapacity &gt;&gt; 1);

    //当扩容容量大于之前的1.5倍时候,则确定新的容量为指定的大小minCapacity
    if (newCapacity - minCapacity &lt; 0)
        newCapacity = minCapacity;

    //最大可扩容到Integer.MAX_VALUE大小
    if (newCapacity - MAX_ARRAY_SIZE &gt; 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

</code></pre>

<ul>
<li>发生扩容的地方</li>
</ul>

<pre><code>//下面这4个对数组添加元素的方法中会用到：
java.util.ArrayList#add(E)
java.util.ArrayList#add(int, E)

java.util.ArrayList#addAll(java.util.Collection&lt;? extends E&gt;)
java.util.ArrayList#addAll(int, java.util.Collection&lt;? extends E&gt;)

//对ArrayList反序列化的时候会用到
java.util.ArrayList#readObject(java.io.ObjectInputStream s)
</code></pre>

<ul>
<li>Fail-Fast</li>
</ul>

<p>当iterator被创建后，除了调用 ListIterator#remove() 和 ListIterator#add(Object) 两个方法外，任何时间只要集合的结构被改变，再调用iterator任何方法都会抛出 ConcurrentModificationException 异常。具体可以查看下边这个方法在哪里地方被使用。</p>

<p>如果在并发场景下使用 ArrayList ，通常有下面3种方法解决：</p>

<ul>
<li>1. 使用 Vector 集合替代 ArrayList ，Vector 中使用了大量的 synchronized 关键字对方法做同步处理，同一时刻只允许一个线程访问和修改该集合，该类一般用的比较少，下面两种方式用的多一些，因为它的迭代器只读场景下也会加独占锁。</li>
<li>2. 使用java.util.Collections工具类对集合做包装，它提供了对List Map Set的封装，如下：
<code>List<Object> list = Collections.synchronizedList(new ArrayList&lt;&gt;());</code>。
但是Collections.synchronizedXXX对集合做包装后，集合的方法均拥有了同步功能，但是他们的<B>迭代器未被实现同步</B>。</li>
<li>3. CopyOnWriteArrayList 使用 ReentrantLock 和 volatile 保证了线程安全，但是每次增加元素的时候都会调用java.util.Arrays#copyOf(T[], int)方法把久的数组复制到一个长度增加了的新数组上，所以在写少读多的场景下，比较推荐这个方法。在写比较多的情况下，建议使用Collections.synchronizedXXX。</li>
</ul>

<h3 id="toc_8">2.3.2. Collection - LinkedList源码解析</h3>

<p>LinkedList是基于链表实现的列表结构。</p>

<ul>
<li>底层数据结构</li>
</ul>

<pre><code>/**
 * 链表结构中每个节点Node的数据结构
 */
private static class Node&lt;E&gt; {
    E item;
    Node&lt;E&gt; next;
    Node&lt;E&gt; prev;

    Node(Node&lt;E&gt; prev, E element, Node&lt;E&gt; next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

//链表长度
transient int size = 0;

/**
 * 指向链表首端的第一个元素。
 * 任何时候: (first == null &amp;&amp; last == null) ||
 *          (first.prev == null &amp;&amp; first.item != null)
 */
transient Node&lt;E&gt; first;

/**
 * 指向链表首端的最后一个元素。
 * 任何时候: (first == null &amp;&amp; last == null) ||
 *          (last.next == null &amp;&amp; last.item != null)
 */
transient Node&lt;E&gt; last;
</code></pre>

<ul>
<li>关于扩容</li>
</ul>

<p>由于LinkedList是基于链表实现的列表结构，所以不存在扩容的说话。所有结构上的修改，都是链表的节点修改。不支持随机读，所以在获取指定位置上的元素值时，效率较差。</p>

<ul>
<li>Queue 相关的方法</li>
</ul>

<p>Queue，单向队列，具备FIFO属性。</p>

<pre><code>/**
 * 获取队列中最早加入的元素，但是不删除该元素。
 *
 * @return 返回队列的第一个元素，若队列为空，则返回null
 */
public E peek() {
    final Node&lt;E&gt; f = first;
    return (f == null) ? null : f.item;
}

/**
 * 获取队列中最早加入的元素，但是不删除该元素。
 *
 * @return 返回队列的第一个元素，若队列为空，则抛出异常 NoSuchElementException.
 */
public E element() {
    return getFirst();
}

/**
 * 获取队列中最早加入的元素，并删除该元素。
 *
 * @return 返回队列的第一个元素，若队列为空，则返回null
 */
public E poll() {
    final Node&lt;E&gt; f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * 删除队列中最早加入的元素,并返回它。同removeFirst
 *
 * @return 返回队列的第一个元素，若队列为空，则抛出异常 NoSuchElementException.
 */
public E remove() {
    return removeFirst();
}

/**
 * 在队列尾部加入一个元素，并返回true。若队列满了，则返回一个false。
 */
public boolean offer(E e) {
    return add(e);
}

</code></pre>

<ul>
<li>Deque 相关的方法</li>
</ul>

<p>Deque，双向队列，可以具备Queue的所有属性。在源码中：</p>

<pre><code>public interface Queue&lt;E&gt; extends Collection&lt;E&gt;{...}

public interface Deque&lt;E&gt; extends Queue&lt;E&gt;{...}

public class LinkedList&lt;E&gt;
    extends AbstractSequentialList&lt;E&gt;
    implements List&lt;E&gt;, Deque&lt;E&gt;, Cloneable, java.io.Serializable{}
</code></pre>

<ul>
<li>Fail-Fast</li>
</ul>

<p>当iterator被创建后，除了调用 ListIterator#remove 和 ListIterator#add 两个方法外，任何时间只要集合的结构被改变，再调用iterator任何方法都会抛出 ConcurrentModificationException 异常。具体可以查看下边这个方法在哪里地方被使用。</p>

<p>如果在并发场景下使用 LinkedList ，通常有下面3种方法解决：</p>

<ul>
<li>1. 使用 Vector 集合替代 ArrayList ，Vector 中使用了大量的 synchronized 关键字对方法做同步处理，同一时刻只允许一个线程访问和修改该集合，该类一般用的比较少，下面两种方式用的多一些，因为它的迭代器只读场景下也会加独占锁。</li>
<li>2. 使用java.util.Collections工具类对集合做包装，它提供了对List Map Set的封装，如下：</li>
</ul>

<pre><code>List&lt;Object&gt; list = Collections.synchronizedList(new LinkedList&lt;&gt;());

但是Collections.synchronizedXXX对集合做包装后，集合的方法均拥有了同步功能，但是他们的&lt;B&gt;迭代器未被实现同步&lt;/B&gt;。
</code></pre>

<ul>
<li>3. CopyOnWriteArrayList 使用 ReentrantLock 和 volatile 保证了线程安全，但是每次增加元素的时候都会调用java.util.Arrays#copyOf(T[], int)方法把久的数组复制到一个长度增加了的新数组上，所以在写少读多的场景下，比较推荐这个方法。在写比较多的情况下，建议使用Collections.synchronizedXXX。</li>
</ul>

<h3 id="toc_9">2.3.3. Collection - Stack &amp; Queue</h3>

<p>Java已不推荐 Stack ，而是推荐使用更高效的 ArrayDeque，或者 LinkedList。ArrayDeque是基于数组实现的双端队列，LinkedList是基于链表实现的双端队列。</p>

<h4 id="toc_10">Queue</h4>

<p>Queue接口继承自Collection接口，这里有两组格式，共6个方法，一组是通过抛出异常反馈执行结果；另外一组是通过返回值来实现(没有则返回null)。</p>

<table>
<thead>
<tr>
<th style="text-align: center">-</th>
<th style="text-align: center">Throws exception</th>
<th style="text-align: center">Returns special value</th>
</tr>
</thead>

<tbody>
<tr>
<td style="text-align: center">插入值</td>
<td style="text-align: center">add(e)</td>
<td style="text-align: center">offer(e)</td>
</tr>
<tr>
<td style="text-align: center">删除值</td>
<td style="text-align: center">remove()</td>
<td style="text-align: center">poll()</td>
</tr>
<tr>
<td style="text-align: center">查看值</td>
<td style="text-align: center">element()</td>
<td style="text-align: center">peek()</td>
</tr>
</tbody>
</table>

<h4 id="toc_11">Deque</h4>

<p>Deque是&quot;double ended queue&quot;, 表示双向的队列，英文读作&quot;deck&quot;. Deque 继承自 Queue接口，除了支持Queue的方法之外，还支持insert, remove和examine操作，由于Deque是双向的，所以可以对队列的头和尾都进行操作，它同时也支持两组格式，一组是抛出异常的实现；另外一组是返回值的实现(没有则返回null)。共12个方法如下:</p>

<table>
<thead>
<tr>
<th style="text-align: left">-</th>
<th style="text-align: left">First Element - Head</th>
<th style="text-align: left">-</th>
<th style="text-align: left">Last Element - Tail</th>
<th style="text-align: left">-</th>
</tr>
</thead>

<tbody>
<tr>
<td style="text-align: left">-</td>
<td style="text-align: left">Throws exception</td>
<td style="text-align: left">Special value</td>
<td style="text-align: left">Throws exception</td>
<td style="text-align: left">Special value</td>
</tr>
<tr>
<td style="text-align: left">Insert</td>
<td style="text-align: left">addFirst(e)</td>
<td style="text-align: left">offerFirst(e)</td>
<td style="text-align: left">addLast(e)</td>
<td style="text-align: left">offerLast(e)</td>
</tr>
<tr>
<td style="text-align: left">Remove</td>
<td style="text-align: left">removeFirst()</td>
<td style="text-align: left">pollFirst()</td>
<td style="text-align: left">removeLast()</td>
<td style="text-align: left">pollLast()</td>
</tr>
<tr>
<td style="text-align: left">Examine</td>
<td style="text-align: left">getFirst()</td>
<td style="text-align: left">peekFirst()</td>
<td style="text-align: left">getLast()</td>
<td style="text-align: left">peekLast()</td>
</tr>
</tbody>
</table>

<ul>
<li>把 Deque 当做 queue 来使用时，元素是从deque的尾部添加，从头部进行删除的； 所以deque的部分方法是和queue是等同的。具体如下:</li>
</ul>

<table>
<thead>
<tr>
<th style="text-align: left">Queue Method</th>
<th style="text-align: left">Equivalent Deque Method</th>
<th style="text-align: left">说明</th>
</tr>
</thead>

<tbody>
<tr>
<td style="text-align: left">add(e)</td>
<td style="text-align: left">addLast(e)</td>
<td style="text-align: left">向队尾插入元素，失败则抛出异常</td>
</tr>
<tr>
<td style="text-align: left">offer(e)</td>
<td style="text-align: left">offerLast(e)</td>
<td style="text-align: left">向队尾插入元素，失败则返回false</td>
</tr>
<tr>
<td style="text-align: left">remove()</td>
<td style="text-align: left">removeFirst()</td>
<td style="text-align: left">获取并删除队首元素，失败则抛出异常</td>
</tr>
<tr>
<td style="text-align: left">poll()</td>
<td style="text-align: left">pollFirst()</td>
<td style="text-align: left">获取并删除队首元素，失败则返回null</td>
</tr>
<tr>
<td style="text-align: left">element()</td>
<td style="text-align: left">getFirst()</td>
<td style="text-align: left">获取但不删除队首元素，失败则抛出异常</td>
</tr>
<tr>
<td style="text-align: left">peek()</td>
<td style="text-align: left">peekFirst()</td>
<td style="text-align: left">获取但不删除队首元素，失败则返回null</td>
</tr>
</tbody>
</table>

<ul>
<li>Deque 与 Stack 来使用</li>
</ul>

<table>
<thead>
<tr>
<th style="text-align: left">Stack Method</th>
<th style="text-align: left">Equivalent Deque Method</th>
<th style="text-align: left">说明</th>
</tr>
</thead>

<tbody>
<tr>
<td style="text-align: left">push(e)</td>
<td style="text-align: left">addFirst(e)</td>
<td style="text-align: left">向栈顶插入元素，失败则抛出异常</td>
</tr>
<tr>
<td style="text-align: left">-</td>
<td style="text-align: left">offerFirst(e)</td>
<td style="text-align: left">向栈顶插入元素，失败则返回false</td>
</tr>
<tr>
<td style="text-align: left">pop()</td>
<td style="text-align: left">removeFirst()</td>
<td style="text-align: left">获取并删除栈顶元素，失败则抛出异常</td>
</tr>
<tr>
<td style="text-align: left">-</td>
<td style="text-align: left">pollFirst()</td>
<td style="text-align: left">获取并删除栈顶元素，失败则返回null</td>
</tr>
<tr>
<td style="text-align: left">peek()</td>
<td style="text-align: left">getFirst()</td>
<td style="text-align: left">获取但不删除栈顶元素，失败则抛出异常</td>
</tr>
<tr>
<td style="text-align: left">无</td>
<td style="text-align: left">peekFirst()</td>
<td style="text-align: left">获取但不删除栈顶元素，失败则返回null</td>
</tr>
</tbody>
</table>

<h3 id="toc_12">2.3.4. 源码解析Collection - PriorityQueue源码解析</h3>

<p>前面以 Java ArrayDeque 为例讲解了 Stack 和 Queue ，其实还有一种特殊的队列叫做 PriorityQueue ，即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的。元素大小的评判可以通过元素本身的自然顺序，也可以通过构造时传入的自定义比较器Comparator。</p>

<p>Java 中 PriorityQueue 实现了 Queue 接口，不允许放入 null 元素；其通过堆实现，具体说是通过完全二叉树(complete binary tree)实现的小顶堆(任意一个非叶子节点的权值，都不大于其左右子节点的权值)，也就意味着可以通过数组来作为PriorityQueue的底层实现。</p>

<p><img src="media/16923736135980/16924322064320.jpg" alt="PriorityQueue的数据实现"/></p>

<p>上图中我们给每个元素按照层序遍历的方式进行了编号，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系:</p>

<pre><code>leftNo = parentNo*2+1
rightNo = parentNo*2+2
parentNo = (nodeNo-1)/2

通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
</code></pre>

<p><B>PriorityQueue的peek()和element操作是常数时间，add(), offer(), 无参数的remove()以及poll()方法的时间复杂度都是log(N)。</B></p>

<h4 id="toc_13">方法剖析</h4>

<p>add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。</p>

<p><img src="media/16923736135980/16924324618178.jpg" alt="java.util.PriorityQueue#offer调用的siftUp方法"/></p>

<p>新加入的元素可能会破坏小顶堆的性质，因此需要进行必要的调整。</p>

<pre><code>//offer(E e)
public boolean offer(E e) {
    if (e == null)//不允许放入null元素
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i &gt;= queue.length)
        grow(i + 1);//自动扩容
    size = i + 1;
    if (i == 0)//队列原来为空，这是插入的第一个元素
        queue[0] = e;
    else
        siftUp(i, e);//调整
    return true;
}
</code></pre>

<p>上述代码中，扩容函数grow()类似于ArrayList里的grow()函数，就是再申请一个更大的数组，并将原数组的元素复制过去。需要注意的是siftUp(int k, E x)方法，该方法用于<B>插入元素x并维持堆的特性</B>。</p>

<pre><code>private void siftUp(int k, E x) {
    while (k &gt; 0) {
        int parent = (k - 1) &gt;&gt;&gt; 1;//parentNo = (nodeNo-1)/2
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) &gt;= 0)//调用比较器的比较方法
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}
</code></pre>

<p>新加入的元素x可能会破坏小顶堆的性质，因此需要进行调整。调整的过程为 <B>从k指定的位置开始，将x逐层与当前点的parent进行比较并交换，直到满足x &gt;= queue[parent]为止</B>。注意这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。</p>

<h4 id="toc_14">element()和peek()</h4>

<p>element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时<B>前者抛出异常，后者返回null</B>。<br/>
根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。</p>

<p><img src="media/16923736135980/16924331064527.jpg" alt="java.util.PriorityQueue#peek"/></p>

<pre><code>public E peek() {
    if (size == 0)
        return null;
    return (E) queue[0];//0下标处的那个元素就是最小的那个
}
</code></pre>

<h4 id="toc_15">remove()和poll()</h4>

<p>remove() 和 poll() 方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时<B>前者抛出异常，后者返回null</B>。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。</p>

<p><img src="media/16923736135980/16924332406922.jpg" alt=""/></p>

<pre><code>public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];//0下标处的那个元素就是最小的那个
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);//调整
    return result;
}

private void siftDown(int k, E x) {
    int half = size &gt;&gt;&gt; 1;
    while (k &lt; half) {
        //首先找到左右孩子中较小的那个，记录到c里，并用child记录其下标
        int child = (k &lt;&lt; 1) + 1;//leftNo = parentNo*2+1
        Object c = queue[child];
        int right = child + 1;
        if (right &lt; size &amp;&amp;
            comparator.compare((E) c, (E) queue[right]) &gt; 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) &lt;= 0)
            break;
        queue[k] = c;//然后用c取代原来的值
        k = child;
    }
    queue[k] = x;
}
</code></pre>

<h4 id="toc_16">remove(Object o)</h4>

<p>remove(Object o) 方法用于删除队列中跟 o 相等的某一个元素(如果有多个相等，只删除一个).<br/>
该方法不是Queue接口内的方法，而是Collection接口的方法。<br/>
由于删除操作会改变队列结构，所以要进行调整；又由于删除元素的位置可能是任意的，所以调整过程比其它函数稍加繁琐。<br/>
具体来说，remove(Object o)可以分为2种情况: </p>

<ul>
<li>1. 删除的是最后一个元素。直接删除即可，不需要调整。</li>
<li>2. 删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用一次siftDown()即可。</li>
</ul>

<p><img src="media/16923736135980/16924334176468.jpg" alt=""/></p>

<pre><code>//remove(Object o)
public boolean remove(Object o) {
    //通过遍历数组的方式找到第一个满足o.equals(queue[i])元素的下标
    int i = indexOf(o);
    if (i == -1)
        return false;
    int s = --size;
    if (s == i) //情况1
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);//情况2
        ......
    }
    return true;
}
</code></pre>

<h2 id="toc_17">2.4. 核心 Map &amp; Set 源码解读</h2>

<h3 id="toc_18">2.4.1. Map - HashSet &amp; HashMap 源码解析</h3>

<h3 id="toc_19">2.4.2. Map - LinkedHashSet&amp;Map源码解析</h3>

<h3 id="toc_20">2.4.3. Map - TreeSet &amp; TreeMap 源码解析</h3>

<h3 id="toc_21">2.4.4. Map - WeakHashMap源码解</h3>

<p>维度：</p>

<p>默认初始容量&amp;允许的最大长度<br/>
首次扩容时间&amp;扩容逻辑<br/>
哪些地方会发生扩容？调用了什么方法<br/>
底层数据结构<br/>
自定义初始容量<br/>
同步机制<br/>
Fail-Fast<br/>
并发场景下怎么使用<br/>
关于性能：<br/>
    读/查找/修改/随机插入的性能：<br/>
    写入性能：</p>


</div>

<br /><br />
<hr />

<div class="row clearfix">
  <div class="large-6 columns">
	<div class="text-left" style="padding:15px 0px;">

	        <a href="16923474457318.html"  title="Previous Post: 1. Java 基础">&laquo; 1. Java 基础</a>

	</div>
  </div>
  <div class="large-6 columns">
	<div class="text-right" style="padding:15px 0px;">

	        <a href="16924335832240.html"
	        title="Next Post: 2.4. Map - HashSet & HashMap 源码解析">2.4. Map - HashSet & HashMap 源码解析 &raquo;</a>

	</div>
  </div>
</div>

<div class="row">
<div style="padding:0px 0.93em;" class="share-comments">

</div>
</div>
<script type="text/javascript">
	$(function(){
		var currentURL = '16923736135980.html';
		$('#side-nav a').each(function(){
			if($(this).attr('href') == currentURL){
				$(this).parent().addClass('active');
			}
		});
	});
</script>
</div></div>


<div class="page-bottom">
  <div class="row">
  <hr />
  <div class="small-9 columns">
  <p class="copyright">Copyright &copy; 2015
Powered by <a target="_blank" href="http://www.mweb.im">MWeb</a>,&nbsp;
Theme used <a target="_blank" href="http://github.com">GitHub CSS</a>.</p>
  </div>
  <div class="small-3 columns">
  <p class="copyright text-right"><a href="#header">TOP</a></p>
  </div>

  </div>
</div>

        </section>
      </div>
    </div>


    <script src="asset/js/foundation.min.js"></script>
    <script src="asset/js/foundation/foundation.offcanvas.js"></script>
    <script>
      $(document).foundation();


    </script>


  </body>
</html>