master

分支 (1)

管理

管理

master

leocook-private
/
16925007307182.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.6. Map - TreeSet & TreeMap 源码解析 -

  </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.6. Map - TreeSet & TreeMap 源码解析</h1>

<ul>
<li>
<a href="#toc_0">2.6.1. TreeMap中左旋代码</a>
</li>
<li>
<a href="#toc_1">2.6.2. TreeMap中右旋代码</a>
</li>
<li>
<a href="#toc_2">2.6.3. 寻找节点后继</a>
</li>
<li>
<a href="#toc_3">2.6.4. get()</a>
</li>
<li>
<a href="#toc_4">2.6.5. put()</a>
</li>
<li>
<a href="#toc_5">2.6.6. remove()</a>
</li>
<li>
<a href="#toc_6">2.6.7. TreeSet</a>
</li>
</ul>


<p>之所以把 TreeSet 和 TreeMap 放在一起讲解，是因为二者在Java里有着相同的实现，前者仅仅是对后者做了一层包装，也就是说TreeSet里面有一个TreeMap(适配器模式)。</p>

<p>因此本文将重点分析TreeMap。Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。</p>

<p>TreeMap底层通过红黑树(Red-Black tree)实现，也就意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。<br/>
<img src="media/16925007307182/16925015375091.jpg" alt=""/></p>

<p>出于性能原因，TreeMap是非同步的(not synchronized)，如果需要在多线程环境使用，需要程序员手动同步；或者通过 Collections.synchronizedXXX 包装成(wrapped)同步的:</p>

<pre><code>SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
</code></pre>

<p>红黑树是实际应用中最常用的平衡二叉查找树，它<B>不严格的具有平衡属性</B>，但平均的使用性能非常良好。相比与拥有更高平衡性的AVL树，红黑树失衡恢复较快，用此在删除和插入时性能更高，而AVL树属于易查找但不易删除、插入得平衡二叉树。综合来看，红黑树有着较为均衡的性能表现。</p>

<p>很多人到这里就直接晕了，那么我们先聊一下二叉树的相关知识，再聊一下红黑树的左旋、右旋、以及插入和删除后的调整策略。</p>

<h3 id="toc_0">2.6.1. TreeMap中左旋代码</h3>

<pre><code>//Rotate Left
private void rotateLeft(Entry&lt;K,V&gt; p) {
    if (p != null) {
        Entry&lt;K,V&gt; r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}
</code></pre>

<h3 id="toc_1">2.6.2. TreeMap中右旋代码</h3>

<pre><code>//Rotate Right
private void rotateRight(Entry&lt;K,V&gt; p) {
    if (p != null) {
        Entry&lt;K,V&gt; l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }
}
</code></pre>

<h3 id="toc_2">2.6.3. 寻找节点后继</h3>

<p>TreeMap中寻找节点后继的代码如下:<br/>
```<br/>
// 寻找节点后继函数successor()<br/>
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {<br/>
    if (t == null)<br/>
        return null;<br/>
    else if (t.right != null) { //1. t的右子树不空，则t的后继是其右子树中最小的那个元素<br/>
        Entry<K,V> p = t.right;<br/>
        while (p.left != null) //1.1. 一直找到该节点右子节点下的最左节点<br/>
            p = p.left;<br/>
        return p;<br/>
    } else {// 2. t的右孩子为空，则t的后继是其第一个向右走的祖先<br/>
        Entry<K,V> p = t.parent;<br/>
        Entry<K,V> ch = t;</p>

<pre><code>    /*
     * 1.父节点为空时，说明该节点是跟节点，直接返回；
     * 2.向上寻找时，当前节点不是父节点的右子节点（父节点第一次右拐）时，
     * 返回右拐后的第一个节点。
     */
    while (p != null &amp;&amp; ch == p.right) {
        ch = p;
        p = p.parent;
    }
    return p;
}
</code></pre>

<p>}<br/>
```</p>

<h3 id="toc_3">2.6.4. get()</h3>

<p>get(Object key)方法根据指定的key值返回对应的value，该方法调用了getEntry(Object key)得到相应的entry，然后返回entry.value。因此getEntry()是算法的核心。算法思想是根据key的自然顺序(或者比较器顺序)对二叉查找树进行查找，直到找到满足k.compareTo(p.key) == 0的entry。</p>

<p><img src="media/16925007307182/16925213108570.jpg" alt=""/></p>

<p>具体代码如下:</p>

<pre><code>//getEntry()方法
final Entry&lt;K,V&gt; getEntry(Object key) {
    ......
    if (key == null)//不允许key值为null
        throw new NullPointerException();
    Comparable&lt;? super K&gt; k = (Comparable&lt;? super K&gt;) key;//使用元素的自然顺序
    Entry&lt;K,V&gt; p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp &lt; 0)    //key小于当前比较节点的值，向左子树查找
            p = p.left;
        else if (cmp &gt; 0)   //key大于当前比较节点的值，向右子树查找
            p = p.right;
        else    //key等于当前比较节点的值，说明找到了，直接返回
            return p;
    }
    return null;
}
</code></pre>

<h3 id="toc_4">2.6.5. put()</h3>

<p>put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找，看是否包含该元组，如果已经包含则直接返回，查找过程类似于getEntry()方法；如果没有找到则会在红黑树中插入新的entry，如果插入之后破坏了红黑树的约束条件，还需要进行调整(旋转，改变某些节点的颜色)。</p>

<pre><code>public V put(K key, V value) {
    ......
    int cmp;
    Entry&lt;K,V&gt; parent;
    if (key == null)
        throw new NullPointerException();
    Comparable&lt;? super K&gt; k = (Comparable&lt;? super K&gt;) key;//使用元素的自然顺序
    do {
        parent = t;
        cmp = k.compareTo(t.key);
        if (cmp &lt; 0) t = t.left;    //key小于当前比较节点的值，向左子树查找
        else if (cmp &gt; 0) t = t.right;  //key大于当前比较节点的值，向右子树查找
        else return t.setValue(value);  //key值已存在，直接覆盖，并直接返回
    } while (t != null); //找到要插入的叶子节点时跳出循环，插在 parent 下
    Entry&lt;K,V&gt; e = new Entry&lt;&gt;(key, value, parent);//创建并插入新的entry
    if (cmp &lt; 0) parent.left = e;//key小于parent节点的值，应该插在左边
    else parent.right = e; //key大于parent节点的值，应该插在左边
    fixAfterInsertion(e);//修复红黑树，保持平衡性
    size++;//插入成功，size+1
    return null;
}
</code></pre>

<p>上述代码就在红黑树上找到合适的位置，然后创建新的entry并插入,如key节点已存在则直接覆盖。</p>

<p>插入值后需要检查和修复树的平衡度，则调用 fixAfterInsertion() 实现：1.改变某些节点的颜色；2.对某些节点进行旋转。<br/>
<img src="media/16925007307182/16925225781198.jpg" alt=""/></p>

<pre><code>/**
 * 采用先序遍历的方式来对红黑树进行调整。&lt;br/&gt;
 * 找到合适的地方进行左旋与右旋
 */
private void fixAfterInsertion(Entry&lt;K,V&gt; x) {
    x.color = RED; //当前写入的节点颜色变为RED
    while (x != null &amp;&amp; x != root &amp;&amp; x.parent.color == RED) {
        //假设x节点的父节点为A，A若是A父节点的左节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Entry&lt;K,V&gt; y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);  //左旋
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));  //右旋
            }
        } else {
            Entry&lt;K,V&gt; y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);  //右旋
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));  //左旋
            }
        }
    }
    root.color = BLACK;
}
</code></pre>

<h3 id="toc_5">2.6.6. remove()</h3>

<p>remove(Object key) 的作用是删除 key 值对应的 entry，该方法首先通过上文中提到的 getEntry(Object key) 方法找到 key值 对应的 entry，然后调用 deleteEntry(Entry<K,V> entry) 删除对应的 entry。由于删除操作会改变红黑树的结构，有可能破坏红黑树的约束条件，因此有可能要进行调整。<br/>
deleteEntry() 函数删除指定的entry并在红黑树的约束被破坏时进行调用 fixAfterDeletion(Entry<K,V> x) 进行调整。<br/>
由于红黑树是一棵增强版的二叉查找树，红黑树的删除操作跟普通二叉查找树的删除操作也就非常相似，区别是红黑树在节点删除之后可能需要进行调整。<br/>
一棵普通二叉查找树的删除过程，可以简单分为两种情况:</p>

<ul>
<li><p>情况一：删除节点p的左右子树都为空，或者只有一棵子树非空。<br/>
当左右子树都为空时，直接将节点p删除。当只有一棵子树时，直接用子树替代节点p。</p></li>
<li><p>情况二：删除点p的左右子树都非空。<br/>
可以用p的后继节点s(树中大于x的最小的那个元素)代替p。红黑树的节点删除函数deleteEntry()代码如下:</p></li>
</ul>

<pre><code>// 红黑树entry删除函数deleteEntry()
private void deleteEntry(Entry&lt;K,V&gt; p) {
    modCount++;
    size--;
    if (p.left != null &amp;&amp; p.right != null) {  //待删除节点p的左右子树都非空。
        Entry&lt;K,V&gt; s = successor(p);  //找到节点p的后继节点
        p.key = s.key;
        p.value = s.value;
        p = s;
    }
    Entry&lt;K,V&gt; replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {// 1. 删除点p只有一棵子树非空。
        replacement.parent = p.parent;
        if (p.parent == null)
            root = replacement;
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        else
            p.parent.right = replacement;
        p.left = p.right = p.parent = null;
        if (p.color == BLACK)
            fixAfterDeletion(replacement);// 调整
    } else if (p.parent == null) {
        root = null;
    } else { // 1. 删除点p的左右子树都为空
        if (p.color == BLACK)
            fixAfterDeletion(p);// 调整
        if (p.parent != null) {
            if (p == p.parent.left)
                p.parent.left = null;
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}
</code></pre>

<p>只有删除BLACK节点的时候，才会触发调整函数，因为删除RED节点不会破坏红黑树的任何约束，而删除BLACK节点会破坏红黑树的规则。</p>

<p>与 fixAfterInsertion() 函数一样，这里也分成多种情况。但具体的调整操作只有两种:</p>

<ul>
<li>1.改变某些节点的颜色；</li>
<li>2.对某些节点进行旋转。</li>
</ul>

<p><img src="media/16925007307182/16925467665936.jpg" alt=""/></p>

<p>代码如下：</p>

<pre><code>private void fixAfterDeletion(Entry&lt;K,V&gt; x) {
    while (x != root &amp;&amp; colorOf(x) == BLACK) {
        if (x == leftOf(parentOf(x))) {
            Entry&lt;K,V&gt; sib = rightOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x)); //左旋
                sib = rightOf(parentOf(x));
            }
            if (colorOf(leftOf(sib))  == BLACK &amp;&amp;
                colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib); //右旋
                    sib = rightOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x)); //左旋
                x = root;
            }
        } else { // 跟前四种情况对称
            Entry&lt;K,V&gt; sib = leftOf(parentOf(x));
            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x)); //右旋
                sib = leftOf(parentOf(x));
            }
            if (colorOf(rightOf(sib)) == BLACK &amp;&amp;
                colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib); //左旋
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x)); //右旋
                x = root;
            }
        }
    }
    setColor(x, BLACK);
}
</code></pre>

<h3 id="toc_6">2.6.7. TreeSet</h3>

<p>前面已经说过TreeSet是对TreeMap的简单包装，对TreeSet的函数调用都会转换成合适的TreeMap方法，因此TreeSet的实现非常简单。这里不再赘述。</p>

<pre><code>// TreeSet是对TreeMap的简单包装
public class TreeSet&lt;E&gt; extends AbstractSet&lt;E&gt;
    implements NavigableSet&lt;E&gt;, Cloneable, java.io.Serializable
{
    ......
    private transient NavigableMap&lt;E,Object&gt; m;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public TreeSet() {
        this.m = new TreeMap&lt;E,Object&gt;();// TreeSet里面有一个TreeMap
    }
    ......
    public boolean add(E e) {
        return m.put(e, PRESENT)==null;
    }
    ......
}
</code></pre>


</div>

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

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

	        <a href="16924372183713.html"  title="Previous Post: 2.5. Map - LinkedHashSet & LinkedHashMap源码解析">&laquo; 2.5. Map - LinkedHashSet & LinkedHashMap源码解析</a>

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

	        <a href="16926055818559.html"
	        title="Next Post: Paxos选举算法">Paxos选举算法 &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 = '16925007307182.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>