Java 之路/表
array Vector table
数组是一种通用的数据结构，但它们存在两个重要的限制
项目符号
数组的大小不取决于它包含的项目数量。如果数组太大，就会浪费空间。如果太小，可能会导致错误，或者我们可能需要编写代码来调整它的大小。
虽然数组可以包含任何类型的项目，但数组的索引必须是整数。例如，我们不能使用字符串来指定数组中的元素。
项目符号
在向量部分，我们看到了内置的 Vector 类是如何解决第一个问题的。随着用户添加项目，它会自动扩展。还可以缩小 Vector，使其容量与当前大小相同。
但是 Vectors 无法帮助解决第二个问题。索引仍然是整数。
这就是表 ADT 出现的地方。表是 Vector 的泛化，可以使用任何类型作为索引。这些泛化索引称为键。
就像使用索引访问数组中的值一样，使用键访问表中的值。因此，每个键都与一个值相关联，这就是为什么表有时被称为关联数组的原因。
dictionary associative array key entry index
表的常见示例是字典，它是将单词（键）与其定义（值）相关联的表。由于这个例子，表有时也被称为字典。此外，将特定键与特定值相关联称为条目。
Table ADT ADT!Table
与我们看过的其他 ADT 一样，表是由它们支持的操作集定义的
描述
[构造函数：] 创建一个新的空表。
[put：] 创建一个将值与键关联的条目。
[get：] 对于给定的键，查找相应的 value。
[containsKey：] 如果表中存在使用给定键的条目，则返回 true。
[keys：] 返回包含表中所有键的集合。
描述
Hashtable class!Hashtable
Java 提供了表 ADT 的实现，称为 Hashtable。它位于 java.util 包中。在本章后面，我们将看到为什么它被称为 Hashtable。
为了演示 Hashtable 的使用，我们将编写一个简短的程序，该程序遍历一个字符串并统计每个单词出现的次数。
我们将创建一个名为 WordCount 的新类，该类将构建表并打印其内容。自然地，每个 WordCount 对象都包含一个 Hashtable
逐字 public class WordCount
Hashtable ht;
public WordCount ()
ht = new Hashtable ();
逐字
WordCount 的唯一公共方法是 processLine，它接受一个字符串并将它的单词添加到表中，以及 print，它在最后打印结果。
processLine 使用 StringTokenizer 将字符串分解为单词，并将每个单词传递给 processWord。
逐字
public void processLine (String s)
StringTokenizer st = new StringTokenizer (s, " ,.");
while (st.hasMoreTokens())
String word = st.nextToken();
processWord (word.toLowerCase ());
逐字
有趣的工作在 processWord 中。
逐字
public void processWord (String word)
if (ht.containsKey (word))
Integer i = (Integer) ht.get (word);
Integer j = new Integer (i.intValue() + 1);
ht.put (word, j);
else
ht.put (word, new Integer (1));
逐字
如果单词已存在于表中，我们将获取其计数器，递增它，然后放入新值。否则，我们只将一个新条目放入表中，并将计数器设置为 1。
Enumeration class class!Enumeration traverse
要打印表中的条目，我们需要能够遍历表中的键。幸运的是，Hashtable 实现提供了一个名为 keys 的方法，该方法返回一个我们可以使用的 Enumeration 对象。枚举与我们在迭代器部分看到的迭代器非常相似。两者都是 java.util 包中的抽象类；您应该查看两者的文档。以下是使用 keys 打印 Hashtable 内容的方法
逐字
public void print ()
Enumeration enum = ht.keys ();
while (enum.hasMoreElements ())
String key = (String) enum.nextElement ();
Integer value = (Integer) ht.get (key);
System.out.println (" " + key + ", " + value + " ");
逐字
枚举的每个元素都是一个对象，但由于我们知道它们是键，因此我们将它们类型转换为字符串。当我们从表中获取值时，它们也是对象，但我们知道它们是计数器，因此我们将它们类型转换为整数。
最后，要统计字符串中的单词
逐字
WordCount wc = new WordCount ();
wc.processLine ("da doo ron ron ron, da doo ron ron");
wc.print ();
逐字
输出是
逐字
ron, 5 doo, 2 da, 2
逐字
枚举的元素没有任何特定的顺序。唯一保证的是表中的所有键都会出现。
implementation!Table table!vector implementation KeyValuePair
实现表 ADT 的一种简单方法是使用条目向量，其中每个条目都是包含键和值的 object。这些对象被称为键值对。
KeyValuePair 的类定义可能如下所示
逐字 class KeyValuePair
Object key, value;
public KeyValuePair (Object key, Object value)
this.key = key;
this.value = value;
public String toString ()
return " " + key + ", " + value + " ";
逐字
然后表的实现如下所示
逐字 public class Table
Vector v;
public Table ()
v = new Vector ();
逐字
要将新条目放入表中，我们只需将新的 KeyValuePair 添加到 Vector 中
逐字
public void put (Object key, Object value)
KeyValuePair pair = new KeyValuePair (key, value);
v.add (pair);
逐字
然后，要查找表中的键，我们必须遍历 Vector 并找到具有匹配键的 KeyValuePair
逐字
public Object get (Object key)
Iterator iterator = v.iterator ();
while (iterator.hasNext ())
KeyValuePair pair = (KeyValuePair) iterator.next ();
if (key.equals (pair.key))
return pair.value;
return null;
逐字
遍历 Vector 的习惯用法是我们之前在迭代器部分看到的。当我们比较键时，我们使用深度相等（equals 方法）而不是浅层相等（== 运算符）。这允许键类指定相等的定义。在我们的示例中，键是字符串，因此它将使用 String 类中的内置 equals 方法。
traverse
对于大多数内置类，equals 方法实现深度相等。然而，对于某些类，很难定义这意味着什么。例如，请参阅 Doubles 的 equals 文档。
equals equality
由于 equals 是一个对象方法，因此 get 的这个实现如果 key 为 null 则无法正常工作。我们可以将 null 作为特殊情况进行处理，或者我们可以像内置的 Hashtable 一样---简单地声明 null 不是合法键。
说到内置的 Hashtable，它的 put 实现与我们的实现略有不同。如果表中已经存在使用给定键的条目，put 会更新它（赋予它一个新值），并返回旧值（如果没有旧值，则返回 null。以下是它们的版本的实现
逐字
public Object put (Object key, Object value)
Object result = get (key);
if (result == null)
KeyValuePair pair = new KeyValuePair (key, value);
v.add (pair);
else
update (key, value);
return result;
逐字
update 方法不是表 ADT 的一部分，因此它被声明为私有。它遍历向量，直到找到正确的 KeyValuePair，然后更新 value 字段。请注意，我们不必修改 Vector 本身，只需修改它包含的其中一个对象即可。
逐字
private void update (Object key, Object value)
Iterator iterator = v.iterator ();
while (iterator.hasNext ())
KeyValuePair pair = (KeyValuePair) iterator.next ();
if (key.equals (pair.key))
pair.value = value;
break;
逐字
我们还没有实现的唯一方法是 containsKey 和 keys。containsKey 方法几乎与 get 相同，除了它返回 true 或 false 而不是对象引用或 null。
作为练习，通过构建键向量并返回向量中的元素来实现 keys。有关更多信息，请参阅 Vector 类中的元素文档。
abstract class!List List abstract class
java.util 包定义了一个名为 List 的抽象类，它指定了类为了被认为（非常抽象地）是一个列表而必须实现的操作集。当然，这并不意味着每个实现 List 的类都必须是链表。
不出所料，内置的 LinkedList 类是 List 抽象类的一个成员。令人惊讶的是，Vector 也是如此。
List 定义中的方法包括 add、get 和 iterator。事实上，我们用来实现 Table 的 Vector 类中的所有方法都在 List 抽象类中定义。
这意味着我们可以使用任何 List 类来代替 Vector。在 Table.java 中，我们可以用 LinkedList 替换 Vector，程序仍然可以正常工作！
这种类型通用性对于调整程序性能很有用。你可以用 List 这样的抽象类来编写程序，然后用几个不同的实现来测试程序，看看哪个实现可以获得最佳性能。
implementation!Table implementation!hash table hash table!implementation table!hash table implementation
Table ADT 的内置实现被称为 Hashtable，因为它使用了一种称为哈希表的 Table 的特别高效的实现。
当然，定义 ADT 的全部意义在于它允许我们在不知道细节的情况下使用实现。因此，Java 库的编写者根据其实现而不是其 ADT 来命名这个类可能不是一件好事，但我认为在他们所做的一切坏事中，这件事算是很小了。
无论如何，你可能想知道哈希表是什么，以及为什么我说它特别高效。我们将从分析我们刚刚完成的 List 实现的性能开始。
查看 put 的实现，我们看到有两种情况。如果键不在表中，那么我们只需要创建一个新的键值对并将其添加到 List 中。这两种操作都是常数时间操作。
在另一种情况下，我们必须遍历 List 以找到现有的键值对。这是一个线性时间操作。出于同样的原因，get 和 containsKey 也是线性的。
虽然线性操作通常足够好，但我们可以做得更好。事实证明，有一种方法可以实现 Table ADT，使 put 和 get 都是常数时间操作！
关键是认识到遍历列表所需的时间与列表的长度成正比。如果我们可以对列表的长度设置上限，那么我们就可以对遍历时间设置上限，而任何具有固定上限的东西都被认为是常数时间。
analysis!hashtable
但是，如何在不限制表中项目数量的情况下限制列表的长度？通过增加列表的数量。我们不会使用一个长列表，而是保留许多短列表。
只要我们知道要搜索哪个列表，我们就可以对搜索量设置上限。
hash function mapping
这就是哈希函数的作用。我们需要某种方法来查看一个键，并在不搜索的情况下知道它位于哪个列表中。我们将假设列表位于数组（或 Vector）中，因此我们可以通过索引引用它们。
解决方案是找到键值与列表索引之间的一种映射关系——几乎任何映射都可以。对于每个可能的键，必须有一个索引，但可能有多个键映射到同一个索引。
例如，想象一个包含 8 个列表的数组和一个由键（为整数）和值（为字符串）组成的表。由于它们是正确的类型，因此使用整数的 intValue 作为索引可能很诱人，但有很多整数不在 0 到 7 之间，而 0 到 7 是唯一合法的索引。
modulus operator!modulus
模运算符提供了一种简单（就代码而言）且高效（就运行时间而言）的方法，将所有整数映射到范围。表达式
逐字
key.intValue()
逐字
保证产生 -7 到 7（包含两者）之间的值。如果取其绝对值（使用 Math.abs），你将获得一个合法的索引。
对于其他类型，我们可以玩类似的游戏。例如，要将 Character 转换为整数，我们可以使用内置方法 Character.getNumericValue，对于 Doubles，可以使用 intValue。
shifted sum
对于字符串，我们可以获取每个字符的数值并将其加起来，或者使用移位求和。要计算移位求和，请在将新值添加到累加器和将累加器左移之间交替。通过“左移”我的意思是“乘以一个常数”。
为了了解它是如何工作的，请查看以下数字列表。
and compute their shifted sum as
首先，将累加器初始化为 0。然后，
枚举
将累加器乘以 10。
将列表的下一个元素添加到累加器。
重复此操作，直到列表结束。
枚举
作为练习，编写一个方法，使用 32 的乘数计算字符串中字符的数值的移位求和。
对于每种类型，我们可以找到一个函数，它接收该类型的值并生成相应的整数值。这些函数称为哈希函数，因为它们通常涉及对对象组件进行散列。每个对象的整数值称为其哈希码。
还有一种方法可以为 Java 对象生成哈希码。每个 Java 对象都提供一个名为 hashCode 的方法，该方法返回对应于该对象的整数。对于内置类型，hashCode 方法的实现方式是，如果两个对象包含相同的数据，它们将具有相同的哈希码（如深度相等）。这些方法的文档解释了哈希函数是什么。你应该查看它们。
deep equality hash function hash code
对于用户定义的类型，由实现者提供适当的哈希函数。在 Object 类中提供的默认哈希函数通常使用对象的地址来生成哈希码，因此它对“相同性”的理解是浅层相等。通常，当我们在哈希表中搜索一个键时，浅层相等不是我们想要的。
无论哈希码是如何生成的，最后一步都是使用模运算符和绝对值将哈希码映射到合法索引的范围内。
resizing hash table!resizing
让我们回顾一下。哈希表由一个列表数组（或 Vector）组成，每个列表包含少量键值对。要将新条目添加到表中，我们计算新键的哈希码，并将条目添加到相应的列表中。
要查找一个键，我们再次对其进行散列，并搜索相应的列表。如果列表的长度是有界的，那么搜索时间也是有界的。
那么我们如何保持列表的长度很短呢？一个目标是尽可能地保持它们平衡，这样就不会出现一些列表非常长而其他列表为空的情况。这并不容易做到完美——这取决于我们选择哈希函数的好坏——但我们通常可以做得很好。
即使完全平衡，平均列表长度也会随着条目数量的增加而线性增长，我们必须阻止这种情况发生。
解决方案是跟踪每个列表的平均条目数量，称为负载因子；如果负载因子过高，我们必须调整表的大小。
load factor rehashing
要调整大小，我们创建一个新表，通常是原始表的两倍大，将所有条目从旧表中取出，再次对其进行散列，然后将它们放到新表中。通常我们可以使用相同的哈希函数；我们只是对模运算符使用不同的值。
analysis!Hashtable
调整表大小需要多长时间？显然，它与条目数量成正比。这意味着，在大多数情况下，put 需要常数时间，但有时——当我们调整大小——它需要线性时间。
一开始这听起来很糟糕。这难道不会破坏我关于 put 可以用常数时间执行的说法吗？坦率地说，是的。但只要稍微哄哄，我就可以解决它。
由于有些 put 操作比其他操作花费的时间更长，让我们计算一下 put 操作的平均时间。平均值将是，一个简单 put 的常数时间，再加上一个额外的项，即，我们必须调整大小的百分比，乘以，调整大小的成本。
方程 t(n) = c + p kn 方程
我不知道 和 是什么，但我们可以弄清楚是什么
is. Imagine that we have just resized the hash table by
将其大小加倍。如果有 个条目，那么在必须再次调整大小之前，我们可以添加 个额外的条目。因此，我们必须调整大小的百分比是 。
代入方程，我们得到
方程 t(n) = c + 1/n kn = c + k 方程
换句话说，是常数时间！
table entry key value dictionary associative array hash table hash function hash code shifted sum load factor
描述
[表:] 定义对条目集合的操作的 ADT。
[条目:] 表中包含键值对的元素。
[键:] 用于在表中查找值的任何类型的索引。
[值:] 存储在表中的任何类型的元素。
[字典:] 另一个表名。
[关联数组:] 另一个字典名。
[哈希表:] 一种特别高效的表实现。
[哈希函数:] 一个将某种类型的映射到整数的函数。
[哈希码:] 对应于给定值的整数值。
[移位求和:] 一种简单的哈希函数，通常用于像字符串这样的复合对象。
[负载因子:] 哈希表中条目的数量除以哈希表中列表的数量；即每个列表的平均条目数。
描述