Hashtable и список бок о бок?

Question

Мне нужна структура данных, которая упорядочена, но также дает быстрый произвольный доступ и вставляет и удаляет. Linkedlists упорядочены и быстро вставляются и удаляются, но они дают медленный произвольный доступ. Hashtables дают быстрый произвольный доступ, но не упорядочены.

Так что, кажется, приятно использовать оба из них вместе. В моем текущем решении моя Hashtable включает итераторы списка, а List содержит фактические элементы. Хороший и эффективный. Хорошо, это требует двойной памяти, но это не проблема.

Я слышал, что некоторые древовидные структуры могут это сделать, но так же быстро, как это решение?

Answer 1

Самая эффективная древовидная структура, которую я знаю, это Red Black Tree, и это не так быстро, как ваше решение, поскольку оно имеет O (log n) для всех операций, в то время как ваше решение имеет O (1) для некоторых, если не всех, операций.

Если память не является проблемой, и вы уверены, что ваше решение O (1) означает, что время, необходимое для добавления/удаления/поиска элемента в структуре, не связано с количеством предметов, которые у вас есть, идите за ним.

Answer 2

На самом деле Java содержит LinkedHashTable, который похож на структуру данных, которую вы описываете. Это может быть неожиданно полезно время от времени.

Структуры деревьев также могут работать, видя, что они могут выполнять произвольный доступ (и большинство других операций) в (O log n) времени. Не так быстро, как Hashtables (O 1), но все же быстро, если ваша база данных не очень большая.

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

Answer 3

Вы должны рассмотреть Skip List, который является упорядоченным связанным списком с временем доступа O (log n). Другими словами, вы можете перечислить его O (n), а index/insert/delete - O (log n).

Answer 4

Деревья изготовлены для этого. Наиболее подходящими являются деревья с самобалансировкой, такие как AVL tree или Red Black tree. Если вы имеете дело с очень большими суммами данных, также может быть полезно создать B-tree (они используются, например, для файловых систем).

Что касается вашей реализации: это может быть более или менее эффективен, чем дерева в зависимости от количества работы с данными и HashTable реализации. Например. некоторые хеш-таблицы с очень плотными данными могут давать доступ не в O (1), а в O (log n) или даже O (n). Также помните, что вычисляющий хэш из данных занимает некоторое время, поэтому для вывода небольших данных абсолютное время для вычисления хэша может быть больше, чем для поиска в дереве.

Answer 5

Что вы сделали, это в значительной степени правильный выбор.

Замечательно, что добавление порядка к существующей реализации карты с использованием двунаправленного дважды связанного списка фактически не изменяет его асимптотической сложности, поскольку все соответствующие операции с списком (добавление и удаление) имеют наихудшая сложность этапа Θ (1). (Да, удаление Θ (1) тоже.Причина обычно Θ (n) заключается в том, что вы должны найти элемент, который нужно удалить первым, то есть Θ (n), но фактическое удаление себя is Θ (1). В этом конкретном случае вы даете карте сделать вывод, что-то вроде Θ (1) амортизируется сложность худшего случая или Θ (log _b & thinsp; n) наихудшая сложность шага в зависимости от типа карты используемая реализация.)

Класс Hash в Ruby 1.9, например, является упорядоченной картой, и он реализован, по крайней мере, в YARV и Rubinius в качестве хеш-таблицы, встроенной в связанный список.

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

[Примечание: Я намеренно говорю об асимптотическом поведении здесь, ака «бесконечно большие» коллекции. Если ваши коллекции малы, то просто выберите тот, у которого наименьшие постоянные факторы.]