Отдельное Цепное Хеширование заказано против неупорядоченного - PullRequest
Новая
       26

Отдельное Цепное Хеширование заказано против неупорядоченного

0 голосов
/ 19 мая 2018

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

Как это влияет на операции над массивом с точки зрения сложности (в основном, вставки, удаления и поиска)?

Сначала я подумал, что это может быть тривиально, но чем больше я думаю об этом, тем больше не могу понять, почему бы вам НЕ держать это в порядке?Конечно, несколько операций вставки и удаления узла занимают гораздо меньше времени, чем обход всего списка при каждой попытке найти определенное значение?

Я не ищу никакого решения кода, просто пониманиеза концепцией.Почему-то я не смог найти никаких источников, обсуждающих этот вопрос.

1 Ответ

0 голосов
/ 19 мая 2018

Сначала я подумал, что это может быть тривиально, но чем больше я об этом думаю, тем больше не могу понять, почему бы вам НЕ держать это в порядке?

Я могу думать об этомпричины, по которым элементы цепочки хеш-таблицы не сортируются:

  • Ключи в хеш-таблице не всегда являются примитивными типами данных, такими как integer, float, double или string.Это может быть что угодно - любой сложный экземпляр объекта / класса, который нелегко сопоставить для сортировки.Таким образом, в этом случае каждый раз вам нужно будет реализовать политику сравнения для объекта, который будет ключевым (реализовать оператор <, = в C ++, реализовать Comparable<T> в Java и т. Д.).

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

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

Редактировать

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

...