插入 Trie
现在，让我们关注在 Trie 中插入单词的算法：
将当前节点视为根节点。
从第一个字符开始，逐字符循环给定的单词。
如果当前节点（Map<Character, Node>）为当前字符映射一个值（Node），那么只需前进到该节点。否则，新建一个Node，将其字符设置为当前字符，并前进到此节点。
重复步骤 2（传递到下一个字符），直到单词的结尾。
将当前节点标记为完成单词的节点。
在代码行方面，我们有以下内容：
public void insert(String word) { Node node = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); Function function = k -> new Node(); node = node.getChildren().computeIfAbsent(ch, function); } node.setWord(true); }
插入的复杂度为O(n)，其中n表示字长。
搜索 Trie
现在，让我们在 Trie 中搜索一个单词：
将当前节点视为根节点。
逐字符循环给定的单词（从第一个字符开始）。
对于每个字符，检查其在 Trie 中的存在性（在Map<Character, Node>中）。
如果字符不存在，则返回false。
从第 2 步开始重复，直到单词结束。
如果是单词，则在单词末尾返回true，如果只是前缀，则返回false。
在代码行方面，我们有以下内容：
public boolean contains(String word) { Node node = root; for (int i = 0; i < word.length(); i++) { char ch = word.charAt(i); node = node.getChildren().get(ch); if (node == null) { return false; } } return node.isWord(); }
查找的复杂度为O(n)，其中n表示字长。
从 Trie 中删除
最后，让我们尝试从 Trie 中删除：
验证给定的单词是否是 Trie 的一部分。
如果它是 Trie 的一部分，那么只需移除它。
使用递归并遵循以下规则，以自下而上的方式进行删除：
如果给定的单词不在 Trie 中，那么什么也不会发生（返回false）
如果给定的单词是唯一的（不是另一个单词的一部分），则删除所有相应的节点（返回true）
如果给定的单词是 Trie 中另一个长单词的前缀，则将叶节点标志设置为false（返回false）
如果给定的单词至少有另一个单词作为前缀，则从给定单词的末尾删除相应的节点，直到最长前缀单词的第一个叶节点（返回false）
在代码行方面，我们有以下内容：
public boolean delete(String word) { return delete(root, word, 0); } private boolean delete(Node node, String word, int position) { if (word.length() == position) { if (!node.isWord()) { return false; } node.setWord(false); return node.getChildren().isEmpty(); } char ch = word.charAt(position); Node children = node.getChildren().get(ch); if (children == null) { return false; } boolean deleteChildren = delete(children, word, position + 1); if (deleteChildren && !children.isWord()) { node.getChildren().remove(ch); return node.getChildren().isEmpty(); } return false; }
查找的复杂度为O(n)，其中n表示字长。
现在，我们可以构建一个 Trie，如下所示：
Trie trie = new Trie(); trie.insert/contains/delete(...);
125 元组
基本上，元组是由多个部分组成的数据结构。通常，元组有两到三个部分。通常，当需要三个以上的部分时，一个专用类是更好的选择。
元组是不可变的，每当我们需要从一个方法返回多个结果时就使用元组。例如，假设有一个方法返回数组的最小值和最大值。通常，一个方法不能同时返回这两个值，使用元组是一个方便的解决方案。
不幸的是，Java 不提供内置元组支持。然而，Java 附带了Map.Entry<K,V>，用于表示来自Map的条目。此外，从 JDK9 开始，Map接口被一个名为entry(K k, V v)的方法丰富，该方法返回一个包含给定键和值的不可修改的Map.Entry<K, V>。
对于一个由两部分组成的元组，我们可以编写如下方法：
public static <T> Map.Entry<T, T> array( T[] arr, Comparator<? super T> c) { T min = arr[0]; T max = arr[0]; for (T elem: arr) { if (c.compare(min, elem) > 0) { min = elem; } else if (c.compare(max, elem)<0) { max = elem; } } return entry(min, max); }
如果这个方法存在于一个名为Bounds的类中，那么我们可以如下调用它：
public class Melon { private final String type; private final int weight; // constructor, getters, equals(), hashCode(), // toString() omitted for brevity } Melon[] melons = { new Melon("Crenshaw", 2000), new Melon("Gac", 1200), new Melon("Bitter", 2200), new Melon("Hami", 800) }; Comparator<Melon> byWeight = Comparator.comparing(Melon::getWeight); Map.Entry<Melon, Melon> minmax = Bounds.array(melons, byWeight); System.out.println("Min: " + minmax1.getKey()); // Hami(800g) System.out.println("Max: " + minmax1.getValue()); // Bitter(2200g)
但我们也可以编写一个实现。一个由两部分组成的元组通常被称为一个对；因此，一个直观的实现可以如下所示：
public final class Pair<L, R> { final L left; final R right; public Pair(L left, R right) { this.left = left; this.right = right; } static <L, R> Pair<L, R> of (L left, R right) { return new Pair<>(left, right); } // equals() and hashCode() omitted for brevity }
现在，我们可以重写计算最小值和最大值的方法，如下所示：
public static <T> Pair<T, T> array(T[] arr, Comparator<? super T> c) { ... return Pair.of(min, max); }
126 并查集
并查算法在不相交集数据结构上运行。
不相交的集合数据结构定义了在某些不相交的子集中分离的元素集合，这些子集是不重叠的。从图形上看，我们可以用三个子集表示不相交集，如下图所示：
在代码中，不相交集表示为：
n是元素的总数（例如，在上图中，n是 11）。
rank是一个用 0 初始化的数组，用于决定如何合并两个具有多个元素的子集（具有较低rank的子集成为具有较高rank的子集的子子集）。
parent是允许我们构建基于数组的并查的数组（最初为parent[0] = 0; parent[1] = 1; ... parent[10] = 10;）：
public DisjointSet(int n) { this.n = n; rank = new int[n]; parent = new int[n]; initializeDisjointSet(); }
并查算法主要应具备以下功能：
- 将两个子集合并为一个子集
- 返回给定元素的子集（这对于查找同一子集中的元素很有用）
为了在内存中存储不相交的集合数据结构，我们可以将它表示为一个数组。最初，在数组的每个索引处，我们存储该索引（x[i] = i。每个索引可以映射到一段对我们有意义的信息，但这不是强制性的。例如，这样一个数组的形状可以如下图所示（最初，我们有 11 个子集，每个元素都是它自己的父元素）：
或者，如果我们使用数字，我们可以用下图来表示：
在代码行方面，我们有以下内容：
private void initializeDisjointSet() { for (int i = 0; i < n; i++) { parent[i] = i; } }
此外，我们需要通过并集操作来定义我们的子集。我们可以通过（父、子对）序列来定义子集。例如，让我们定义以下三对-union(0,1);、union(4, 9);和union(6, 5);。每次一个元素（子集）成为另一个元素（子集）的子元素时，它都会修改其值以反映其父元素的值，如下图所示：
这个过程一直持续到我们定义了所有的子集。例如，我们可以添加更多的联合-union(0, 7);、union(4, 3);、union(4, 2);、union(6, 10);和union(4, 5);。这将产生以下图形表示：
根据经验，建议将较小的子集合并为较大的子集，反之亦然。例如，检查包含4的子集与包含5的子集相统一的时刻。此时，4是子集的父项，它有三个子项（2、3、9），而5紧挨着10，6的两个子项。因此，包含5的子集有三个节点（6、5、10），而包含4的子集有四个节点（4、2、3、9）。因此，4成为6的父，并且隐含地成为5的父。
在代码行中，这是rank[]数组的工作：
现在让我们看看如何实现find和union操作
实现查找操作
查找给定元素的子集是一个递归过程，通过跟随父元素遍历子集，直到当前元素是其自身的父元素（根元素）：
public int find(int x) { if (parent[x] == x) { return x; } else { return find(parent[x]); } }
好吧。现在让我们定义一个不相交集：
DisjointSet set = new DisjointSet(11); set.union(0, 1); set.union(4, 9); set.union(6, 5); set.union(0, 7); set.union(4, 3); set.union(4, 2); set.union(6, 10); set.union(4, 5);
现在让我们来玩玩它：
// is 4 and 0 friends => false System.out.println("Is 4 and 0 friends: " + (set.find(0) == set.find(4))); // is 4 and 5 friends => true System.out.println("Is 4 and 5 friends: " + (set.find(4) == set.find(5)));
该算法可以通过压缩元素间的路径来优化。例如，检查下图：
在左侧，在寻找5的父代时，必须经过6直到4。同样，在寻找10的父代时，必须经过6，直到4为止。然而，在右侧，我们通过直接链接到4来压缩5和10的路径。这一次，我们不需要通过中间元素就可以找到5和10的父代。
路径压缩可以针对find()操作进行，如下所示：
public int find(int x) { if (parent[x] != x) { return parent[x] = find(parent[x]); } return parent[x]; }
捆绑到本书中的代码包含两个应用，有路径压缩和没有路径压缩。
127 Fenwick 树或二叉索引树
芬威克树（FT）或二叉索引树（BIT）是为存储对应于另一给定数组的和而构建的数组。构建数组的大小与给定数组的大小相同，并且构建数组的每个位置（或节点）都存储给定数组中某些元素的总和。由于 BIT 存储给定数组的部分和，因此通过避免索引之间的循环和计算和，它是计算给定数组中两个给定索引（范围和/查询）之间的元素和的非常有效的解决方案。
位可以在线性时间或O(n log n)中构造。显然，我们更喜欢线性时间，所以让我们看看如何做到这一点。我们从给定的（原始）数组开始，该数组可以是（下标表示数组中的索引）：
3(1), 1(2), 5(3), 8(4), 12(5), 9(6), 7(7), 13(8), 0(9), 3(10), 1(11), 4(12), 9(13), 0(14), 11(15), 5(16)
构建位的想法依赖于最低有效位（LSB)概念。更准确地说，假设我们正在处理索引中的元素，a。那么，紧靠我们上方的值必须位于索引b，其中b = a + LSB(a)。为了应用该算法，索引 0 的值必须是 0；因此，我们操作的数组如下：
0(0), 3(1), 1(2), 5(3), 8(4), 12(5), 9(6), 7(7), 13(8), 0(9), 3(10), 1(11), 4(12), 9(13), 0(14), 11(15), 5(16)
现在，让我们应用算法的几个步骤，用和填充位。在位的索引 0 处，我们有 0。此外，我们使用b = a + LSB(a)公式计算剩余和，如下所示：
a=1：如果a=1=0b00001，则b=0b00001+0b00001=1+1=2=0b00010。我们说 2 负责a（也就是 1）。因此，在位中，在索引 1 处，我们存储值 3，在索引 2 处，我们存储值的和，3+1=4。
a=2：如果a=2=0b00010，则b=0b00010+0b00010=2+2=4=0b00100。我们说 4 负责a（即 2）。因此，在索引 4 处，我们以位的形式存储值的和，8+4=12。
a=3：如果a=3=0b00011，则b=0b00011+0b00001=3+1=4=0b00100。我们说 4 负责a（也就是 3）。因此，在位中，在索引 4 处，我们存储值的和，12+5=17。
a=4。如果a=4=0b00100，则b=0b00100+0b00100=4+4=8=0b01000。我们说 8 负责a（也就是 4）。因此，在位中，在索引 8 处，我们存储值的和，13+17=30。
算法将以相同的方式继续，直到位完成。在图形表示中，我们的案例可以如下所示：
如果索引的计算点超出了界限，那么只需忽略它。
在代码行中，前面的流的形状可以如下所示（值是给定的数组）：
public class FenwickTree { private final int n; private long[] tree; ... public FenwickTree(long[] values) { values[0] = 0 L; this.n = values.length; tree = values.clone(); for (int i = 1; i < n; i++) { int parent = i + lsb(i); if (parent < n) { tree[parent] += tree[i]; } } } private static int lsb(int i) { return i & -i; // or // return Integer.lowestOneBit(i); } ... }
现在，位准备好了，我们可以执行更新和范围查询。
例如，为了执行范围求和，我们必须获取相应的范围并将它们相加。请考虑下图右侧的几个示例，以快速了解此过程：
就代码行而言，这可以很容易地形成如下形状：
public long sum(int left, int right) { return prefixSum(right) - prefixSum(left - 1); } private long prefixSum(int i) { long sum = 0L; while (i != 0) { sum += tree[i]; i &= ~lsb(i); // or, i -= lsb(i); } return sum; }
此外，我们还可以增加一个新的值：
public void add(int i, long v) { while (i < n) { tree[i] += v; i += lsb(i); } }
我们还可以为某个索引设置一个新值：
public void set(int i, long v) { add(i, v - sum(i, i)); }
具备所有这些功能后，我们可以按如下方式为数组创建位：
FenwickTree tree = new FenwickTree(new long[] { 0, 3, 1, 5, 8, 12, 9, 7, 13, 0, 3, 1, 4, 9, 0, 11, 5 });
然后我们可以玩它：
long sum29 = tree.sum(2, 9); // 55 tree.set(4, 3); tree.add(4, 5);
128 布隆过滤器
布隆过滤器是一种快速高效的数据结构，能够提供问题的概率答案“值 X 在给定的集合中吗？”
通常情况下，当集合很大且大多数搜索算法都面临内存和速度问题时，此算法非常有用。
布隆过滤器的速度和内存效率来自这样一个事实，即该数据结构依赖于位数组（例如，java.util.BitSet）。最初，该数组的位被设置为0或false。
比特数组是布隆过滤器的第一个主要组成部分。第二个主要成分由一个或多个哈希函数组成。理想情况下，这些是成对独立的和均匀分布的散列函数。另外，非常重要的是要非常快。murrur、fnv系列和HashMix是一些散列函数，它们在布鲁姆过滤器可以接受的范围内遵守这些约束。
现在，当我们向布隆过滤器添加一个元素时，我们需要对这个元素进行散列（通过每个可用的散列函数传递它），并将这些散列的索引处的位数组中的位设置为1或true。
下面的代码片段应该可以阐明主要思想：
private BitSet bitset; // the array of bits private static final Charset CHARSET = StandardCharsets.UTF_8; ... public void add(T element) { add(element.toString().getBytes(CHARSET)); } public void add(byte[] bytes) { int[] hashes = hash(bytes, numberOfHashFunctions); for (int hash: hashes) { bitset.set(Math.abs(hash % bitSetSize), true); } numberOfAddedElements++; }
现在，当我们搜索一个元素时，我们通过相同的散列函数传递这个元素。此外，我们检查结果值是否在位数组中标记为1或true。如果不是，那么元素肯定不在集合中。但如果它们是，那么我们就以一定的概率知道元素在集合中。这不是 100% 确定的，因为另一个元素或元素的组合可能已经翻转了这些位。错误答案称为假正例。
在代码行方面，我们有以下内容：
private BitSet bitset; // the array of bits private static final Charset CHARSET = StandardCharsets.UTF_8; ... public boolean contains(T element) { return contains(element.toString().getBytes(CHARSET)); } public boolean contains(byte[] bytes) { int[] hashes = hash(bytes, numberOfHashFunctions); for (int hash: hashes) { if (!bitset.get(Math.abs(hash % bitSetSize))) { return false; } } return true; }
在图形表示中，我们可以用大小为 11 的位数组和三个哈希函数来表示布隆过滤器，如下所示（我们添加了两个元素）：
显然，我们希望尽可能减少假正例的数量。虽然我们不能完全消除它们，但我们仍然可以通过调整位数组的大小、哈希函数的数量和集合中元素的数量来影响它们的速率。
以下数学公式可用于塑造最佳布隆过滤器：
- 过滤器中的项数（可根据
m、k、p估计）：
n = ceil(m / (-k / log(1 - exp(log(p) / k))));
- 假正例的概率，介于 0 和 1 之间的分数，或表示
p中的 1 的数量：
p = pow(1 - exp(-k / (m / n)), k);
- 过滤器中的位数（或按 KB、KiB、MB、MB、GiB 等表示的大小）：
m = ceil((n * log(p)) / log(1 / pow(2, log(2))));
- 散列函数个数（可根据
m和n估计）：
k = round((m / n) * log(2));
根据经验，一个较大的过滤器比一个较小的过滤器具有更少的假正例。此外，通过增加散列函数的数量，我们可以获得较少的假正例，但我们会减慢过滤器的速度，并将其快速填充。布隆过滤器的性能为O(h)，其中h是散列函数的个数。
在本书附带的代码中，有一个布隆过滤器的实现，它使用基于 SHA-256 和 murrur 的散列函数。由于这段代码太大，无法在本书中列出，因此请考虑将Main类中的示例作为起点。
总结
本章涵盖了涉及数组、集合和几个数据结构的 30 个问题。虽然涉及数组和集合的问题是日常工作的一部分，但涉及数据结构的问题引入了一些不太知名（但功能强大）的数据结构，如并查集和 Trie。
