2

我读到 HashTable 可以将相同的键映射到多个值。这就是碰撞。

现在我像这样运行程序：

Dictionary<String,String> hTable = new Hashtable<String,String>();
hTable.put("a", "aa");
hTable.put("a", "ab");
System.out.println(""+hTable.get("a"));

我的想法说我应该得到aaand ab。

但实际输出是ab

为什么会这样？那么碰撞在哪里呢？

4

5 回答 5

3

没有碰撞。HashTable 条目仅将一个键映射到一个值。

示例中的第三行：

hTable.put("a", "ab");

a将映射 from to替换为 from toaa的映射。aab

在你的四行代码执行完毕后，hTable只有一个映射：ato ab。

于 2011-08-20T04:29:25.193 回答
3

碰撞只发生在内部。对用户来说，是透明地解决的。

这就是为什么哈希表可以是字典的原因——它将每个键映射到精确的 1 个值。如果它映射到超过 1 个值，那么它就不是字典。

于 2011-08-20T04:30:49.317 回答
2

Hashtable 不会将同一个键映射到多个值。冲突是多个键可能映射到同一个哈希值。它由对您透明的数据结构本身解决。

如果要通过 hTable.get("a") 获取 aa 和 ab，则需要创建Dictionary<String,List<String>>并附加具有相同键值的列表。

在您的代码中

hTable.put("a", "aa");
hTable.put("a", "ab");

钥匙是一样的。所以第二个操作使用“ab”覆盖“aa”。这就是为什么你只会得到“ab”。

于 2011-08-20T04:31:50.967 回答
2

HashTable 是 Key -> Value 的映射。这意味着您不能为多个键设置多个值。您需要将两个数据结构组合在一起，用一个键存储多个值。

例如，您可以在 HashTable 中放置一个链接列表。例如

HashTable<String,LinkedList<String>> table = new HashTable();
LinkedList<String> list = new LinkedList();
list.add("aa");
list.add("ab");
table.add("a",list);

现在你可以这样做得到aa和ab值；

table.get("a").get(0); // returns aa
table.get("a").get(1); // returns ab

我强烈建议您阅读数据结构和算法的基础知识。

于 2011-08-20T05:00:07.837 回答
1

您想通过键检索值。数组用于此目的，但仅限于使用整数键，并且可能会占用太多空间（考虑仅在位置 0 和 1000 存储值，您必须为 2 个元素分配整个数组）。

HashTables 通过以下方式解决了这两个问题：

  • 一个分散的非内射函数，将可变长度的字节数组转换为固定长度的字节数组。这意味着你有 hash(bytes_1) == hash(bytes_2) 但它不会经常发生，如果 bytes_1 ~ bytes_2 哈希是不同的；
  • 已使用哈希的索引。如果该函数返回一个 10 字节的数组，则您有 2^80 种可能性，因此您需要保留已遇到的哈希的排序列表；
  • 一个链表数组。哈希索引将哈希映射到数组中的位置。

冲突意味着两个键具有相同的哈希值：map.put("key1", "value1"); map.put("key2", "value2")key1 和 key2 可能会出现在同一个链表中。

于 2011-08-20T06:09:20.707 回答