Лучшая структура данных, чем HashTable для отслеживания обработанных записей?

Question

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

Из-за природы моей базы данных мой метод обработки может встретиться с одним и тем же ключом дважды, поскольку это реляционная база данных иодна запись может иметь более одной «родительской» записи.

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

Я посмотрел на HashTable, так как это O (1) для функций get и put, и это единственные функции, которые мне нужны.Тем не менее, кажется, что трата памяти, по существу, состоит из (1000+) / блока нагрузки и фактора, в котором хранятся логические значения.Кроме того, я не знаю желаемой емкости и мне пришлось бы мириться с большим количеством перефразировок или выделять намного больше памяти, чем мне нужно.

Я думаю, что ищу структуру данных, в которую можно добавить значениечтобы он выдавал какую-то ошибку, если идентификатор уже существует в коллекции, например, возвращает false из метода put(T value).

Answer 1

Прежде всего, звучит так, будто вы хотите набор, а не стол.

Во-вторых, если вы хотите O (1), ваш единственный вариант - это HashSet с накладными расходами памяти. Если вы готовы использовать O (log (n)), то TreeSet будет работать нормально, без накладных расходов.

В-третьих, набор add (T t) вернет false, если элемент уже присутствует. Похоже, вы действительно хотите набор вместо таблицы.

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

Answer 2

Я думаю, что HashSet - это то, что вы ищете: http://download.oracle.com/javase/6/docs/api/java/util/HashSet.html

Answer 3

Вы можете использовать Фильтр Блума вместо hashmap. Это вероятностная структура данных. Проблема с фильтром Блума заключается в том, что он даст false + ve's. Проверьте эту реализацию фильтра Блума . Это было бы эффективным и быстродействующим решением по сравнению с хэш-картой.

Подробнее о фильтре Блума:

• Какие проблемы вы решили с помощью фильтров Блума? [SO Question]
• Фильтр Блума: варианты и приложения [Блог]
• Использование фильтра Блума для оптимизации SQL-запроса

Answer 4

Если набор результатов упорядочен правильно, не могли бы вы просто сохранить «последний обработанный» идентификатор в памяти?Таким образом, вам просто нужно проверить «текущий идентификатор» по сравнению с «последним идентификатором» - если они разные, обработать, иначе перейти к следующей записи?

Answer 5

Эй, поскольку вы работаете с базой данных, не могли бы вы просто сохранить эту информацию во вторичной таблице базы данных или вместе с записями? Также, если у вас есть древовидная структура (поскольку вы говорите о родителях), почему бы не использовать алгоритм обхода дерева, который отмечает обработанные узлы. Оформить заказ Анимации поиска в ширину / первый поиск и эти записи в Википедии:

В общем, я бы обязательно следил за флагом обработки с помощью объекта / строки. Вместо отдельной структуры данных.