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

Question

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

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

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

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

Правка - это упражнение 24 в разделе 2.2.6Кнут, том 1. В ответах приводится упражнение 2.12 «Разработка и анализ компьютерных программ» Ахо, Хопкрафта и Уллмана.Вы можете избежать обвинений в плагиате в своем ответе, сославшись на источник вопроса, который вам задавали: -)

Answer 2

Пометить каждый элемент в хеш-таблице каким-либо цветом (1, 2, ...)

F.e. Текущий цвет:

int curColor = 0;

Когда вы помещаете элемент в хеш-таблицу, ассоциируйте с ним текущий цвет (curColor)

Если вам нужен поиск, отфильтруйте элементы, которые не имеют одинаковый цвет (element.color == curColor)

Если вам нужно очистить hashTable, просто увеличьте текущий цвет (curColor++)