我需要实现一个数组哈希表,无需在开始时将数组初始化为null.有任何线索如何做到这一点？

Question

所以,这是实际问题(这是作业):

哈希表是允许在恒定时间(O(1))访问和操纵日期的数据结构.在创建哈希表期间,哈希表数组必须初始化为null,以便识别空单元格.在大多数情况下,时间损失是巨大的,特别是考虑到大多数细胞永远不会被读取.我们要求您实现一个散列表,以较重的插入价格绕过此问题,但仍然是在恒定的时间.为了完成这项功课并简化您的工作,我们假设您无法删除此哈希表中的元素.

在这个作业的存档中,您将找到需要填充的哈希表的界面.您可以使用java中的函数hashcode()作为哈希函数.您将不得不使用Java中的Vector数据结构来绕过初始化,您必须自己找到如何执行此操作.您只能在向量的末尾插入元素,以便复杂性仍为O(1).

以下是一些需要考虑的事实:

• 在包含整数的哈希表中,该表包含数值(但它们没有任何意义).

• 在堆栈中,您无法访问最高元素上的元素,但您确定所有值都是有效的.此外,您知道最高元素的索引.

使用这些事实绕过哈希表的初始化.该表必须使用线性探测来解决冲突.

此外,这是我需要为此作业实现的界面:

public interface NoInitHashTable<E>
{
    public void insert(E e);
    public boolean contains(E e);

    public void rehash();
    public int nextPrime(int n);
    public boolean isPrime(int n);
}

我已经实现了nextPrime和isPrime(我认为它们与普通的哈希表不同).另外三个我需要弄清楚.

我想了很多,并与我的队友讨论过,但我真的找不到任何东西.我只需要知道如何实现它的基本原理,我可以处理编码.

tl; dr我需要实现一个数组哈希表,无需在开始时将数组初始化为null.插入必须在恒定时间内完成.我只需要知道如何做到这一点的基本原则.

Answer 1

我想我在一本书上看到过这个作为练习，后面有答案，但我不记得是哪本书或在哪里。这通常与为什么我们通常关注程序所花费的时间而不是空间的问题相关 - 一个在时间上有效运行的程序不应该需要大量的空间。

这是一些伪代码，用于检查哈希表中的单元格是否有效。我将保留更改其定义的数据结构以使哈希表中的另一个单元格有效的工作，作为读者的剩余练习。

// each cell here is for a cell at the same offset in the
// hash table
int numValidWhenFirstSetValid[SIZE];
int numValidSoFar = 0; // initialise only this
// Only cells 0..numValidSoFar-1 here are valid.
int validOffsetsInOrderSeen[SIZE];

boolean isValid(int offsetInArray)
{
  int supposedWhenFirstValid =
   numValidWhenFirstSetValid[offsetInArray]
  if supposedWhenFirstValid >= numValidSoFar)
  {
    return false;
  }
  if supposedWhenFirstValid < 0)
  {
    return false;
  }
  if (validOffsetsInOrderSeen[supposedWhenFirstValid] !=
    offsetInArray)
  {
    return false;
 }
 return true;
}

编辑 - 这是 Knuth 第 1 卷第 2.2.6 节中的练习 24。提供的答案参考了 Aho、Hopcraft 和 Ullman 的“计算机程序的设计和分析”练习 2.12。您可以通过引用所问问题的来源来避免在您的回答中出现抄袭的指控:-)