Какую интеллектуальную структуру данных использовать при выполнении нескольких поисков и вставок, но не удаляет?

Question

Я никогда не буду удалять из этой структуры данных, но буду выполнять огромное количество поисков и вставок (~ триллион поисков и вставок).Какова лучшая структура данных для обработки этого?

Красно-чёрные и AVL деревья кажутся приличными, но есть ли какие-нибудь подходящие для этой ситуации?

Answer 1

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

Попробуйте Splay деревья , если вы делаете вставки, и найдите / find-next по заказанным ключам.

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

Answer 2

Если все запросы выполнены успешно (т. Е. К элементам, которые фактически хранятся в таблице), то хеширование, вероятно, лучше, и вы можете поэкспериментировать с различными типами разрешения коллизий, такими как хеширование кукушки, которое обеспечивает худшеегарантии производительности при поиске (см. http://en.wikipedia.org/wiki/Hash_table).

Если между сохраненными ключами находятся некоторые запросы, я бы использовал деревья Ван-Эмде-Боаса, y-быстрые деревья или деревья слияния, которые обеспечивают лучшую производительность, чем бинарный поискдеревья (см. http://courses.csail.mit.edu/6.851/spring10/scribe/lec09.pdf и http://courses.csail.mit.edu/6.851/spring10/scribe/lec10.pdf).

Answer 3

Я бы выбрал красно-черное дерево или хеш-таблицу. Операции на красно-черном - это O (log2 (n)). Если реализация верна, хеш может иметь O (1 + k / n). Если реализация неверна, это может быть так же плохо, как o (k). Если то, что вы пытаетесь сделать, это просто сделать это как можно быстрее, я бы использовал хэш и сделал дополнительную работу. Иначе я бы пошел с красно-черным. Это довольно просто, и вы знаете свое время выполнения.