Java.util.Hashtable类的介绍
1.概述
Hashtable是Java中最古老的哈希表数据结构的实现。HashMap是第二个实现，它在JDK 1.2中被引入。
这两个类都提供了类似的功能，但也有一些小的区别，我们将在本教程中探讨这些区别。
2.何时使用Hashtable
假设我们有一本字典，其中每个词都有它的定义。同时，我们需要从字典中快速获取、插入和删除单词。
因此，Hashtable（或HashMap）是合理的。词将是Hashtable中的键，因为它们应该是唯一的。另一方面，定义将是值。
3.使用实例
让我们继续讨论字典的例子。我们将Word作为一个键的模型。
public class Word {
private String name;
public Word(String name) {
this.name = name;
}
// ...
}比方说，这些值是字符串。现在我们可以创建一个Hashtable。
Hashtable<Word, String> table = new Hashtable<>();首先，让我们添加一个条目。
Word word = new Word("cat");
table.put(word, "an animal");另外，为了获得一个参赛名额。
String definition = table.get(word);最后，让我们删除一个条目。
definition = table.remove(word);该类中还有许多方法，我们将在后面描述其中的一些方法。
但首先，让我们谈一谈对关键对象的一些要求。
4. hashCode()的重要性
要被用作Hashtable中的一个键，对象必须不违反hashCode()约定。简而言之，同等对象必须返回相同的代码。为了理解原因，让我们看看哈希表是如何组织的。
Hashtable使用一个数组。数组中的每个位置是一个“桶”，它可以是空的，也可以包含一个或多个键值对。每个键值对的索引都被计算出来。
但是，为什么不按顺序存储元素，将新的元素添加到数组的末尾呢？
重点是，通过索引找到一个元素要比用比较法依次遍历元素快得多。因此，我们需要一个将键映射到索引的函数。
4.1.直接地址表
这种映射的最简单例子是直接地址表。这里的键被用作索引。
index(k)=k,
where k is a key键是唯一的，也就是每个桶包含一个键值对。当整数键的可能范围相当小时，这种技术对整数键很有效。
但是，我们在这里有两个问题。
- 首先，我们的键不是整数，而是Word对象。
- 第二，如果它们是整数，没有人会保证它们是小的。想象一下，键是1、2和1000000。我们会有一个大小为1000000的大数组，只有三个元素，其余的都是浪费的空间
hashCode()方法解决了第一个问题。
在Hashtable中进行数据操作的逻辑解决了第二个问题。
让我们深入讨论一下这个问题。
4.2.hashCode()方法
任何Java对象都继承了hashCode()方法，它返回一个int值。这个值是由对象的内部内存地址计算出来的。默认情况下，hashCode()为不同的对象返回不同的整数。
因此任何键对象都可以用hashCode()转换为一个整数。但这个整数可能很大。
4.3.缩小范围
get(), put() 和 remove() 方法包含了解决第二个问题的代码 – 减少可能的整数范围。
该公式计算出了一个键的索引。
int index = (hash & 0x7FFFFFFF) % tab.length;其中tab.length是数组的大小，hash是由键的hashCode()方法返回的数字。
我们可以看到index是提醒除法hash的数组大小。注意，相等的哈希代码产生相同的索引。
4.4.碰撞
此外，即使是不同的哈希代码也能产生相同的索引。我们把这称为碰撞。为了解决碰撞问题，Hashtable存储了一个LinkedList的键值对。
这样的数据结构被称为带链式的哈希表。
4.5.负载因子
很容易猜到，碰撞会减慢对元素的操作。为了得到一个条目，仅仅知道它的索引是不够的，我们还需要遍历整个列表，并与每个项目进行比较。
因此，减少碰撞的数量是很重要的。数组越大，碰撞的机会就越小。负载因子决定了数组大小和性能之间的平衡。默认情况下，它是0.75，这意味着当75%的桶不为空时，数组的大小会增加一倍。这个操作是由rehash()方法执行的。
但让我们回到key的问题上。
4.6.重写 equals() 和 hashCode()
当我们把一个条目放入Hashtable并从其中获取时，我们希望不仅可以用相同的键的实例来获取值，而且还可以用相同的键来获取。
Word word = new Word("cat");
table.put(word, "an animal");
String extracted = table.get(new Word("cat"));为了设置相等的规则，我们覆盖了键的equals()方法。
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Word))
return false;
Word word = (Word) o;
return word.getName().equals(this.name);
}但是如果我们在覆盖equals()时没有覆盖hashCode()，那么两个相等的键可能最终会出现在不同的桶中，因为Hashtable使用哈希码来计算键的索引。
让我们仔细看一下上面的例子。如果我们不覆盖hashCode()会怎样？
- 这里涉及到两个Word的实例 - 第一个是用来放置条目，第二个是用来获取条目。虽然这些实例是相等的，但它们的hashCode()方法返回不同的数字
- 每个键的索引是由第4.3节的公式计算的。根据这个公式，不同的哈希代码可能产生不同的索引
- 这意味着我们把条目放到一个桶里，然后试图从另一个桶里把它拿出来。这样的逻辑打破了Hashtable的局面。
相同的键必须返回相同的哈希代码，这就是为什么我们要覆盖hashCode()方法的原因。
public int hashCode() {
return name.hashCode();
}注意，也建议让不相等的键返回不同的哈希代码，否则它们最终会出现在同一个桶里。这将影响性能，因此，失去了Hashtable的一些优势。
另外，请注意，我们并不关心String、Integer、Long或其他封装类型的键。equal()和hashCode()方法都已经在封装类中被重写。
5.迭代 Hashtable
有几种方法可以迭代Hashtables。在这一节中，我们将讨论这些方法，并解释其中的一些含义。
5.1.快速失败：Iteration
快速失败迭代意味着如果一个Hashtable在其Iterator创建后被修改，那么ConcurrentModificationException将被抛出。让我们来演示一下。
首先，我们将创建一个Hashtable，并向其添加条目。
Hashtable<Word, String> table = new Hashtable<Word, String>();
table.put(new Word("cat"), "an animal");
table.put(new Word("dog"), "another animal");其次，我们将创建一个Iterator。
Iterator<Word> it = table.keySet().iterator();第三，我们要修改一下表格。
table.remove(new Word("dog"));现在，如果我们试图遍历该表，我们会得到一个ConcurrentModificationException。
while (it.hasNext()) {
Word key = it.next();
}java.util.ConcurrentModificationException
at java.util.Hashtable$Enumerator.next(Hashtable.java:1378)ConcurrentModificationException有助于发现错误，从而避免不可预测的行为，例如，当一个线程正在迭代表，而另一个线程正试图同时修改它。
5.2.不是快速失败：Enumeration
Hashtable中的Enumeration是不会失败的。让我们看一个例子。
首先，让我们创建一个Hashtable，并向其添加条目。
Hashtable<Word, String> table = new Hashtable<Word, String>();
table.put(new Word("1"), "one");
table.put(new Word("2"), "two");第二，让我们创建一个Enumeration。
Enumeration<Word> enumKey = table.keys();第三，让我们来修改一下这个表格。
table.remove(new Word("1"));现在，如果我们对表进行迭代，就不会出现异常了。
while (enumKey.hasMoreElements()) {
Word key = enumKey.nextElement();
}5.3.不可预测的迭代顺序
另外，请注意，Hashtable中的迭代顺序是不可预测的，与添加条目的顺序并不一致。
这是可以理解的，因为它使用键的哈希代码来计算每个索引。此外，重新洗牌会不时发生，重新安排数据结构的顺序。
因此，让我们添加一些条目并检查输出结果。
Hashtable<Word, String> table = new Hashtable<Word, String>();
table.put(new Word("1"), "one");
table.put(new Word("2"), "two");
// ...
table.put(new Word("8"), "eight");
Iterator<Map.Entry<Word, String>> it = table.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<Word, String> entry = it.next();
// ...
}
}five
four
three
two
one
eight
seven6. Hashtable vs HashMap
Hashtable和HashMap提供了非常类似的功能。
他们都提供了：
- 快速-失败的迭代
- 不可预测的迭代顺序
但也有一些不同之处。
- HashMap没有提供任何 Enumeration，而Hashtable提供的不是快速失败的 Enumeration 。
- Hashtable不允许null键和null值，而HashMap则允许一个null键和任意数量的null值。
- Hashtable的方法是同步的，而HashMaps的方法是不同步的。
7.Java中的Hashtable API 8
Java 8引入了新的方法，有助于使我们的代码更加简洁。特别是，我们可以去掉一些if块。让我们来演示一下。
7.1. getOrDefault()
假设我们需要得到单词“dog”的定义，如果它在表上，就把它分配给变量。否则，将“未找到”分配给该变量。
在Java 8之前。
Word key = new Word("dog");
String definition;
if (table.containsKey(key)) {
definition = table.get(key);
} else {
definition = "not found";
}在Java 8之后。
definition = table.getOrDefault(key, "not found");7.2. putIfAbsent()
假设我们只需要在字典中还没有“cat“这个词时放在字典里。
在Java 8之前。
if (!table.containsKey(new Word("cat"))) {
table.put(new Word("cat"), definition);
}在Java 8之后。
table.putIfAbsent(new Word("cat"), definition);7.3. boolean remove()
比方说，我们需要删除“cat”这个词，但只有在它的定义是“an animal”的情况下。
在Java 8之前。
if (table.get(new Word("cat")).equals("an animal")) {
table.remove(new Word("cat"));
}在Java 8之后。
boolean result = table.remove(new Word("cat"), "an animal");最后，旧的remove()方法返回值，而新的方法则返回boolean。
7.4. replace()
比方说，我们需要替换“cat”的定义，但前提是它的旧定义是“a small domesticated carnivorous mammal”。
在Java 8之前。
if (table.containsKey(new Word("cat"))
&& table.get(new Word("cat")).equals("a small domesticated carnivorous mammal")) {
table.put(new Word("cat"), definition);
}在Java 8之后。
table.replace(new Word("cat"), "a small domesticated carnivorous mammal", definition);7.5. computeIfAbsent()
这个方法类似于putIfabsent()。但是putIfabsent()直接接受值，而computeIfAbsent()接受一个映射函数。它只在检查了键之后才计算值，这更有效率，特别是在值很难得到的情况下。
table.computeIfAbsent(new Word("cat"), key -> "an animal");因此，上面这句话等价于：
if (!table.containsKey(cat)) {
String definition = "an animal"; // note that calculations take place inside if block
table.put(new Word("cat"), definition);
}7.6. computeIfPresent()
这个方法与replace()方法类似。但是，同样，replace()直接取值，而computeIfPresent()取一个映射函数。它在if块内计算值，这就是为什么它更有效率。
比方说，我们需要改变这个定义：
table.computeIfPresent(cat, (key, value) -> key.getName() + " - " + value);因此，上面这句话等同于：
if (table.containsKey(cat)) {
String concatination=cat.getName() + " - " + table.get(cat);
table.put(cat, concatination);
}7.7. compute()
现在我们要解决另一个任务。假设我们有一个String的数组，其中的元素是不唯一的。另外，让我们计算一下一个字符串在数组中能有多少次出现。下面是这个数组。
String[] animals = { "cat", "dog", "dog", "cat", "bird", "mouse", "mouse" };另外，我们想创建一个Hashtable，其中包含一个动物作为键，其出现的数量作为值。
这里有一个解决方案：
Hashtable<String, Integer> table = new Hashtable<String, Integer>();
for (String animal : animals) {
table.compute(animal,
(key, value) -> (value == null ? 1 : value + 1));
}最后，让我们确定，该表包含两只cat、两只dog、一只bird和两只mouse。
assertThat(table.values(), hasItems(2, 2, 2, 1));7.8. merge()
还有另一种方法来解决上述任务。
for (String animal : animals) {
table.merge(animal, 1, (oldValue, value) -> (oldValue + value));
}第二个参数，1，是映射到键的值，如果键还没有在表中。如果键已经在表中，那么我们计算它为oldValue+1。
7.9. foreach()
这是一种遍历条目的新方法。让我们打印所有的条目。
table.forEach((k, v) -> System.out.println(k.getName() + " - " + v)7.10. replaceAll()
此外，我们还可以不经迭代就替换所有的值。
table.replaceAll((k, v) -> k.getName() + " - " + v);8.结语
在这篇文章中，我们已经描述了哈希表结构的目的，并展示了如何将直接地址表结构复杂化以获得该结构。
此外，我们还介绍了什么是碰撞，以及什么是Hashtable.中的负载因子，我们还学习了为什么要覆盖equals()和hashCode()中的关键对象。
最后，我们谈到了Hashtable‘的属性和Java 8特定的API。
像往常一样，完整的源代码可以在Github上获得。