Java中的单独链接

Question

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

因此，我的理解是我应该创建一个大小为n的数组（其中n是素数），并向数组中的每个位置插入一个空链表。然后，我使用我的散列函数来散列字符串，并将它们插入到正确数组位置的相应链表中。我创建了我的散列函数，到目前为止，我的字典构造函数需要一个大小，并创建一个这样大小的数组（实际上，大小为4999，无论是在课堂上讨论的大小都是如此）。我在正确的轨道上吗？我现在应该在每个位置插入一个新的链接列表，然后处理插入/删除方法吗？

Answer 1

你到目前为止听起来不错。

请记住，默认情况下，对象引用数组的每个单元格都有每个单元格null，并且您可以编写插入和删除函数以使用该函数。如果您选择创建不包含数据的链接列表对象（有时称为哨点节点），则创建单个不可变（只读）实例以放入每个空槽是非常有利的，而不是创建4,999个单独的实例与new（其中大多数不包含任何数据）。

Answer 2

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

一些额外的指针：

• 不值得在创建每个桶一个LinkedList，直到它被实际使用。因此，您可以将这些存储桶留空，直到它们被添加为止。请记住写入您的访问函数来考虑这一点。
• 立即创建大型数组并不总是有效。从一个小阵列开始，跟踪所用容量并在必要时放大该阵列（这涉及将这些值重新分组到新阵列）可能会更好一些
• 这是一个好主意，让您的类实现整个Map<K,V>接口 - 只是为了得到一些实践其他标准Java收集方法的做法。