Блог

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

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

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

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

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

Например, текущий цвет:

 int curColor = 0;
  

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

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

Если вам нужно очистить хэш-таблицу, просто увеличьте текущий color ( curColor )