我需要实现一个数组哈希表，它在开始时不将数组初始化为null.知道怎么做吗

那么，这是实际的问题(这是一个家庭作业):

哈希表是一种数据结构，它允许在固定时间(O(1))访问和操作日期。在创建哈希表期间，哈希表数组必须初始化为空，以便识别空单元格。在大多数情况下，时间损失是巨大的，特别是考虑到大多数单元格永远不会被读取。我们要求您实现一个哈希表，以更重的插入为代价，绕过这个问题，但仍然是常数时间。为了本作业的目的和简化您的工作，我们假设您不能删除这个哈希表中的元素。

在本作业的存档中，您将找到需要填充的散列表的接口。您可以使用java中的hashcode()函数作为散列函数。为了绕过初始化，您必须使用Java中的Vector数据结构，并且您必须自己找到如何这样做。你只能在vector的末尾插入元素，这样复杂度仍然是0(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。插入必须在恒定时间内完成。我只需要知道如何做到这一点的基本原则。

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

下面是一些伪代码，检查哈希表中的单元格是否有效。我将把修改它定义的数据结构以使哈希表中的另一个单元格有效的工作留给读者，作为剩下的练习。

// 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。你可以通过参考你被问到的问题的来源来避免任何抄袭的指控:-)

用颜色标记hashtable中的每个元素(1,2，…)

初版现有颜色:

int curColor = 0;

当你将元素放入哈希表时，与它的当前颜色(curColor)相关联

如果需要搜索，请过滤颜色不相同的元素(element.color == curColor)

如果您需要清除hashTable，只需增加当前颜色(curColor++)

相关内容

最新更新

热门标签：