Мне нужно реализовать хеш-таблицу массива, которая работает без инициализации массива нулевым значением в начале. Есть какие-нибудь подсказки, как это сделать?

Итак, вот реальный вопрос (это для домашнего задания):

Хеш-таблица - это структура данных, которая позволяет получать доступ и управлять датой в постоянное время (O (1) ). Массив хеш-таблицы должен быть инициализирован нулевым значением во время создания хеш-таблицы, чтобы идентифицировать пустые ячейки. В большинстве случаев потеря времени огромна, особенно с учетом того, что большинство ячеек никогда не будет прочитано. Мы просим вас реализовать хэш-таблицу, которая позволяет обойти эту проблему за счет более тяжелой вставки, но все же в постоянное время. В целях этой домашней работы и для упрощения вашей работы мы предполагаем, что вы не можете удалять элементы в этой хеш-таблице.

В архиве этого домашнего задания вы найдете интерфейс хеш-таблицы, которую вам нужно заполнить. Вы можете использовать функцию hashcode () из java как хеш-функцию. Вам нужно будет использовать структуру данных Vector из Java, чтобы обойти инициализацию, и вы должны сами найти, как это сделать. Вы можете вставлять элементы только в конец вектора, чтобы сложность оставалась равной 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 Мне нужно реализовать хеш-таблицу массива, которая работает без инициализации массива нулевым значением в начале. Вставка должна производиться за постоянное время. Мне нужно только знать основной принцип, как это сделать.