Двойное хэширование против линейного хэширования

Question

Я пишу двойную хеш-таблицу, которая принимает только целое число.

unsigned int DoubleHashTable::HashFunction1(unsigned int const data)
{
   return (data % GetTableSize());
}

unsigned int DoubleHashTable::HashFunction2(unsigned int const data, unsigned int count)
{
   return ((HashFunction1(data) + count * (5 - (data % 5)) % GetTableSize()));
}

и пытается вставить данные в таблицу с помощью SetData()

void DoubleHashTable::SetData(unsigned int const data)
{
   unsigned int probe = HashFunction1(data);

   if (m_table[probe].GetStatus())
   {
      unsigned int count = 1;
      while (m_table[probe].GetStatus() && count <= GetTableSize())
      {
         probe = HashFunction2(data, count);
         count++;
      }
   }

   m_table[probe].Insert(data);
}

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

Дополнительный вопрос Существуют хорошо известные алгоритмы хеширования, и цель двойного хеширования заключается в том, чтобы сделать как можно меньше коллизий, H2(T) является резервным для H1(T). Но если хорошо известный алгоритм хеширования (например, MD5, SHA и т. Д., Я не говорю о безопасности, просто хорошо известный алгоритм) быстрее и хорошо распространен, зачем нам двойное хеширование?

Спасибо!

Answer 1

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

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

Чтобы ответить на ваш второй вопрос (теперь, когда вы исправили свой код самостоятельно), в двух словах, двойное хеширование лучше подходит для небольших хеш-таблиц, а одиночное хеширование лучше подходит для больших хеш-таблиц.