1

我们班正在学习哈希表，我的一个学习问题涉及我使用带有单独链接的哈希表创建字典。但是，问题是我们不允许使用 Java 提供的方法来创建哈希表。相反，我们的讲义提到，单独的链接涉及数组中的每个单元格，指向一个条目的链接列表。

因此，我的理解是我应该创建一个大小为 n 的数组（其中 n 是素数），并将一个空链表插入到数组中的每个位置。然后，我使用我的哈希函数对字符串进行哈希处理，并将它们插入到相应的链表中的正确数组位置。我创建了我的哈希函数，到目前为止，我的 Dictionary 构造函数接受了一个大小并创建了一个该大小的数组（实际上，大小为 4999，既是质数又是大的，如课堂上所讨论的）。我在正确的轨道上吗？我现在应该在每个位置插入一个新的链表，然后使用插入/删除方法吗？

4

2 回答 2

1

到目前为止，你所拥有的听起来不错。

请记住，对象引用数组null默认具有每个单元格，您可以编写插入和删除函数来处理它。如果您选择创建一个不包含数据的链表对象（有时称为哨兵节点），那么创建一个不可变（只读）实例以放入每个空槽中可能是有利的，而不是创建 4,999 个单独的实例new（大多数不保存任何数据的地方）。

于 2012-10-16T04:04:52.133 回答
0

听起来你在正确的轨道上。

一些额外的指针：

  • 在实际使用之前，不值得在每个存储桶中创建 LinkedList。因此，您可以将存储桶保留为空，直到它们被添加到。只需记住编写访问器函数来考虑这一点。
  • 立即创建一个大数组并不总是有效的。最好从一个小数组开始，跟踪使用的容量，并在必要时扩大数组（这涉及将值重新存储到新数组中）
  • 让您的类实现整个Map<K,V>接口是一个好主意——只是为了获得一些实现其他标准 Java 集合方法的实践。
于 2012-10-16T04:08:39.520 回答