Guava-ImmutableTable

前言

在学习HashBiMap后,接着学习ImmutableTable,该类由行和列共同确定一个元素,类似于表格。

ImmutableTable

ImmutableTable实现Table接口,Table接口中定义了表格操作规范,具体方法需要子类实现。

示例


package com.hust.grid.leesf.guavalearning;

import com.google.common.collect.ImmutableSet;
import com.google.common.collect.ImmutableTable;

import java.util.Map;

public class ImmutableTableTest {
    public static void main(String[] args) {
        ImmutableTable<String, String, Integer > immutableTable = ImmutableTable.<String, String, Integer>builder()
                .put("0", "0", 0)
                .put("50", "50", 50)
                .put("100", "100", 100)
                .build();
        ImmutableSet<String> rows = immutableTable.rowKeySet();
        for (String row : rows) {
            for (Map.Entry<String, Integer> entry : immutableTable.row(row).entrySet()) {
                System.out.println(entry.getKey() + " -> " + entry.getValue());
            }
        }

    }
}


运行结果

0 -> 0
50 -> 50
100 -> 100

ImmutableTable#Builder

在调用builder方法时会生成一个Builder对象,Builder类结构如下。


  public static final class Builder<R, C, V> {
    private final List<Cell<R, C, V>> cells = Lists.newArrayList();
    private Comparator<? super R> rowComparator;
    private Comparator<? super C> columnComparator;
  }

可以看到Builder类中使用cells对象存放表格元素,Cell对象表示表单元素,由行和列以及值组成;同时,还包含了行列比较器。

put

在构造完Builder对象后,调用put方法添加元素,put方法源码如下。


    public Builder<R, C, V> put(R rowKey, C columnKey, V value) {
	  // 构造表单元素,并添加至列表中
      cells.add(cellOf(rowKey, columnKey, value));
      return this;
    }

其中,cellof方法会构造一个ImmutableCell对象,ImmutableCell实现了Cell接口。

forCellsInternal

在添加完元素后,调用build方法,该方法根据cells大小确定构造何种Table,本例中,会构造RegularImmutableTable,并且最后会调用forCellsInternal方法,其源码如下。


  private static final <R, C, V> RegularImmutableTable<R, C, V>
      forCellsInternal(Iterable<Cell<R, C, V>> cells,
          @Nullable Comparator<? super R> rowComparator,
          @Nullable Comparator<? super C> columnComparator) {
	// 行构建器
    ImmutableSet.Builder<R> rowSpaceBuilder = ImmutableSet.builder();
	// 列构建器
    ImmutableSet.Builder<C> columnSpaceBuilder = ImmutableSet.builder();
	// 拷贝表格元素列表
    ImmutableList<Cell<R, C, V>> cellList = ImmutableList.copyOf(cells);
    for (Cell<R, C, V> cell : cellList) { // 遍历
	  // 将行添加至行构建器中
      rowSpaceBuilder.add(cell.getRowKey());
	  // 将列添加至列构建器中
      columnSpaceBuilder.add(cell.getColumnKey());
    }

	// 行Set
    ImmutableSet<R> rowSpace = rowSpaceBuilder.build();
    if (rowComparator != null) { // 行比较器不为空
	  // 将Set转化为List
      List<R> rowList = Lists.newArrayList(rowSpace);
	  // 根据比较器进行排序
      Collections.sort(rowList, rowComparator);
	  // 重新赋值排序后的List
      rowSpace = ImmutableSet.copyOf(rowList);
    }
	// 对列进行同样处理
    ImmutableSet<C> columnSpace = columnSpaceBuilder.build();
    if (columnComparator != null) {
      List<C> columnList = Lists.newArrayList(columnSpace);
      Collections.sort(columnList, columnComparator);
      columnSpace = ImmutableSet.copyOf(columnList);
    }

    // use a dense table if more than half of the cells have values
    // TODO(gak): tune this condition based on empirical evidence
	
	// 构建稠密或稀疏表,当元素个数超过行列积一半时,构建稠密表,否则构建稀疏表
    return (cellList.size() > ((rowSpace.size() * columnSpace.size()) / 2)) ?
        new DenseImmutableTable<R, C, V>(cellList, rowSpace, columnSpace) :
        new SparseImmutableTable<R, C, V>(cellList, rowSpace, columnSpace);
  }

可以看到,最后会构造出DenseImmutableTable或者SparseImmutableTable表,两个类中都存在rowMap(行 -> (列,value))columnMap(列 -> (行,value))。而后调用rowKeySet或者columnKeySet时,SparseImmutableTable会从rowMapcolumnMap中取出keySet,而DenseImmutableTablerowKeyToIndex(R -> Integer)columnKeyToIndex(C -> Integer)中取出keySet,其中DenseImmutableTable存在行列索引主要是为了加快检索速度。两个类的核心是rowMapcolumnMap,其提供底层存储和访问支持。

总结

本篇博文讲解了ImmutableTable,其相当于表格,通过行列确定元素,与数据结构中的图密不可分,特别是稠密和稀疏表,该类可用于图类场景中。并且简单分析了源码实现,有兴趣的读者可详细研读源码。