Hashtable и список рядом?

Question

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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