小编Ale*_*ier的帖子

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

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