Структура данных, которая представляет данные в виде стека и хранит их в виде хеш-таблицы?

Question

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

Есть ли такой алгоритм или мне нужно иметь две отдельные структуры? Какая лучшая стратегия?

С наилучшими пожеланиями!

Answer 1

Что бы я, вероятно, сделал бы так:

1. Создайте хеш-таблицу, в которой вы на самом деле храните записи
2. Создание стека, в котором хранятся истинные ячейки памяти объектов (не самих объектов)
3. Абстрагируйте эти две структуры за классом (или чем-то похожим), чтобы его истинная реализация была скрыта от пользователя.

Answer 2

Это будет что-то вроде Упорядоченной Карты, верно?Они обычно реализуются путем объединения связанного списка с тем, что вы хотите использовать для реализации карты (например, хеш-таблица).

В Ruby 1.9 - спецификация класса Hash (что смущает то, как Rubyзаклинание «Карта») было изменено таким образом, чтобы сохранить порядок вставки.Большинство известных мне реализаций Ruby 1.9 реализовали это как некое сочетание списка и хеш-таблицы.Реализацию Rubinius особенно легко читать, поскольку она написана на Ruby на 100%: kernel/common/hash.rb

В Java есть реализация упорядоченной карты, которая называется LinkedHashMap.Вот источник из Oracle OpenJDK 7: /share/classes/java/util/LinkedHashMap.java

Apache Commons Collections имеет интерфейс OrderedMap и две реализации: LinkedMap и ListOrderedMap.

Если вы немного осторожны, вы сможете сохранить асимптотические гарантии сложности неупорядоченной карты.

Answer 3

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

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

2. при удалении значения из таблицы вы также должны удалить его из списка. возможно, стоит сохранить этот объект ListNode в объекте для удаления O (1) из стека / очереди.

если доминирует один из методов удаления, может быть легко принять одно из указанных выше наказаний.

1. например, если вы не хотите удалять вещи по ключу (аля hashmap) и только pop (аля стек / очередь), а ключ легко вычисляется из объекта, (p1) не так уж много и подход абстракции работает.

2. Если метод удаления hashmap действительно будет доминировать, возможно, стоит отсортировать стек по hashkey, а затем выполнить двоичный поиск и затем удалить его из стека / очереди.

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

однако, если ни один из этих случаев не подходит, и вы не можете изменить объект (чтобы заставить его реализовать вашу схему кэширования), это будет означать, что вам придется кэшировать оба этих значения самостоятельно (ключ объекта и узел узла). который вводит третью структуру данных в ваш класс абстракции. в этот момент вы должны спросить себя, стоит ли это с этим подходом абстракции? в тех ситуациях, когда данные будут удалены в обоих направлениях одинаково (или непредсказуемо), тогда стоит сделать что-то заранее, ala jorg mittag. те реализации, которые я считаю, являются прямыми хеш-картами, но у каждого хеш-узла также есть предыдущая и следующая ссылка, такая как список, а сама хеш-карта имеет хвост и голову. (для стека / очереди, например, всплывающих окон / толчков)

в основном все сводится к тому, как вы собираетесь использовать эту структуру данных. Ни один алгоритм не может рассматриваться как лучшая стратегия, без разбивки того, как будут вызываться все методы, варианты использования.

Answer 4

Прежде всего, я думаю, что вы имеете в виду «вводит данные, такие как очередь ».Стек вернет данные в обратном порядке, в котором они были введены.(Кроме того, я не совсем уверен, что вы подразумеваете под «вводом данных» - я не уверен, что это проблема языка или выражение структур данных, которое я никогда не слышал).Мое предложение будет использовать навязчивый связанный список (тот, где ссылка хранится в объекте данных), чтобы создать свой линейный список.Затем вы можете поместить объект данных (с прикрепленной ссылкой) в хеш-таблицу.