我需要实现一个数组哈希表，该哈希表无需在开始时将数组初始化为空即可工作。有任何线索如何做到这一点吗？

发布于 2024-12-12 19:45:12 字数 1024 浏览 0 评论 0原文

所以，这里是实际的问题（这是一个家庭作业）：

哈希表是允许在恒定时间 (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 即可工作。插入必须在恒定时间内完成。我只需要知道如何做到这一点的基本原理。

原文

So, here is the actual question (it's for a homework):

A hashtable is data structure that allows access and manipulation of the date at constant time (O(1)). The hashtable array must be initialized to null during the creation of the hashtable in order to identify the empty cells. In most cases, the time penalty is enormous especially considering that most cells will never be read. We ask of you that you implement a hashtable that bypasses this problem at the price of a heavier insertion, but still at constant time. For the purpose of this homework and to simplify your work, we suppose that you can't delete elements in this hashtable.

In the archive of this homework you will find the interface of an hashtable that you need to fill. You can use the function hashcode() from java as a hash function. You will have to use the Vector data structure from Java in order to bypass the initialization and you have to find by yourself how to do so. You can only insert elements at the end of the vector so that the complexity is still O(1).

Here are some facts to consider:

In a hashtable containing integers, the table contains numeric values (but they don't make any sense).
In a stack, you cannot access elements over the highest element, but you know for sure that all the values are valid. Furthermore, you know the index of the highest element.

Use those facts to bypass the initialization of the hashtable. The table must use linear probing to resolve collisions.

Also, here is the interface that I need to implement for this homework:

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);
}

I have already implemented nextPrime and isPrime (I don't think they are different from a normal hashtable). The three other I need to figure out.

I thought a lot about it and discussed it with my teammate but I really can't find anything. I only need to know the basic principle of how to implement it, I can handle the coding.

tl;dr I need to implement an array hashtable that works without initializing the array to null at the start. The insertion must be done in constant time. I only need to know the basic principle of how to do that.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

森罗 2024-12-19 19:45:13

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

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

// 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。您可以通过引用所问问题的来源来避免在您的回答中出现抄袭的指控:-)

I think I have seen this in a book as exercise with answer at the back, but I can't remember which book or where. It is generally relevant to the question of why we usually concentrate on the time a program takes rather than the space - a program that runs efficiently in time shouldn't need huge amounts of space.

Here is some pseudo-code that checks if a cell in the hash table is valid. I will leave the job of altering the data structures it defines to make another cell in the hash table valid as a remaining exercise for the reader.

// 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;
}

Edit - this is exercise 24 in section 2.2.6 of Knuth Vol 1. The provided answer references exercise 2.12 of "The Design And Analysis of Computer Programs" by Aho, Hopcraft, and Ullman. You can avoid any accusation of plaigarism in your answer by referencing the source of the question you were asked :-)

回复收藏 0 原文