Guava TreeMultiSet实现原理分析

1 存储模型

TreeMultiset本身实现了一棵平衡树，并通过用户定义的比对方式进行排序。用户可以通过两种方式定义比较器：数据类型实现Comparable，或者为Set注册Comparator。和普通的Set相比，TreeMultiset允许多个数据在比较器比较结果是相等的。如果相等，则放在此节点下的一个列表中。

TreeMultiset定义了两种查找方式：head和tail。和他们的名字相对应，head是从头开始截取一部分数据集合，tail是从一个节点开始到尾部截取一部分数据集合。TreeMultiset并没有定义equal的查询方式，而是需要head和tail结合使用，完成equal的功能。当然，head和tail操作可以截取任何一段数据。

TreeMultiset的数据段采用GeneralRange模型来标识。GeneralRange包含了数据段上下限的定义，比较器，以及上下限的开闭性质。

2 树形结构

TreeMultiset本身是一个平衡二叉树。树节点的类型为AvlNode，通过left和right维护节点的左右子节点。

为了快速查询遍历，树上的每个节点通过深度优先搜索的顺序维护自己的上一个节点和下一个节点。如果不做此维护，那么寻找下一节点的时间复杂度将有可能是O(log2n)。比如element4，他是根节点左子树的最后一个节点，他的下个节点是根节点。不加pred和succ的情况下，需要层层递归，直到根节点。

3 head，tail

head操作，是通过条件找到数据段的终止节点，并封装成新的TreeMultiset返回。

@Override
  public SortedMultiset<E> headMultiset(@Nullable E upperBound, BoundType  boundType) {
    return new TreeMultiset<E>(
        rootReference,
        range.intersect(GeneralRange.upTo(comparator(), upperBound, boundType)),
        header);
  }
           

GeneralRange通过upTo()方法创建了一个实例，并通过此实例找出数据区间。

GeneralRange的构造函数对参数进行了校验，如下图。其中对输入的查询信息进行了多次比对（lowerEndPoint，upperEndPoint），确保参数可比对以及参数的区间是存在的。

接下来，TreeMultiset的range将会和新的range进行交集计算，确定数据区间。

tail的实现方式和head类似。

4 iterator

TreeMultiset的iterator实际实现定义在Iterator<Entry> entryIterator()中，如下代码。

迭代器实际上通过AvlNode的信息进行遍历。本身存放当前的节点信息。当调用next时，就返回succ的节点信息。

每返回一个节点，都会先进行一次边界比较。range.tooHigh()中将upperBound和current进行比对。如果超出upperBound，则认为到达边界，结束遍历。

return new Iterator<Entry<E>>() {
      AvlNode<E> current = firstNode();
      @Nullable Entry<E> prevEntry;
      @Override
      public boolean hasNext() {
        if (current == null) {
          return false;
        } else if (range.tooHigh(current.getElement())) {
          current = null;
          return false;
        } else {
          return true;
        }
      }
      @Override
      public Entry<E> next() {
        if (!hasNext()) {
          throw new NoSuchElementException();
        }
        Entry<E> result = wrapEntry(current);
        prevEntry = result;
        if (current.succ == header) {
          current = null;
        } else {
          current = current.succ;
        }
        return result;
      }
      @Override
      public void remove() {
        checkRemove(prevEntry != null);
        setCount(prevEntry.getElement(), 0);
        prevEntry = null;
      }
    };