Лучшая структура данных для следующих ограничений?

Когда N является маленьким простой массив или единственный связанный список с ключом + значение, поскольку полезная нагрузка очень эффективна. Даже если не лучше, когда N становится больше.

Вы получаете O (N) время поиска, что означает, что поиски берут k * N время. O (1) поиск берет константу K время. Таким образом, Вы получаете лучшую производительность с O (N) для N < K/k. Здесь k является очень маленьким, таким образом, можно добраться до интересных значений N. Помните, что Большая нотация O только описывает поведение для большого Ns, не, что Вы после. Для маленьких таблиц

void *lookup(int key_to_lookup)
{
  int n = 0;
  while (table_key[n] != key_to_lookup)
    n++;
  return table_data[n];
}

может быть твердо биться.

Сравните своих хеш-таблиц, сбалансированного дерева и простого массива / связанный список и посмотрите, в которых значениях N каждый из них начинает быть лучше. Затем Вы будете знать, который лучше для Вас.

Я почти забыл: сохраните ключи, к которым часто получают доступ, в начале своего массива. Учитывая Ваше описание, которое средства сохраняют отсортированным.

Этот совет принимает современные CPU с:

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

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

Используя основанных на простом массиве пар значения ключа с O (N) доступ, как упомянуто, но очень низкие постоянные множители и чрезвычайно хорошее поведение кэширования. Эта начальная структура должна быть маленькой (вероятно, не больше, чем 16 и возможно 8 значений) для предотвращения выхода за пределы единственной строки кэша. К сожалению, параметр, который необходимо было бы настроить сами.

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

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

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

Другие опции включают:

• Обработка всех значений ключа <256 по-другому и хранение их в байте -> пара структуры массивов, оставляющих свободное место на ключах (и потенциально позволяющих им остаться там, когда Вы переключаетесь на вторичную структуру), это может работать плохо из-за потребности распаковать массив на лету к собственной длине слова.
• использование trie как структура, делающая байт во время ключа. Я сомневаюсь, что сложность этого заставит его работать хорошо на практике

Еще раз я повторю очень хороший совет от kmkaplan. Сравните его полностью избегающие микросравнительные тесты. В этом виде анализа вещественные числа могут удивительно отличаться от теории...

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

Поиск хеш-таблицы о с такой скоростью, как он CAN быть:

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

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

Так как большинство хеш-функций, используемых для хеш-таблиц, имеет k*c_1% c_2, различие к поиску массива в довольно редкой и/или оптимальной хеш-таблице состоит из одной косвенности, двух умножения, вычитание и разделение (эффективная реализация по модулю с помощью возможностей CPU могла бы уменьшить это вычитанием и умножением), и поиск массива.

Это просто не становится быстрее, чем это.

Вы могли рассмотреть Judy Arrays:

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

Я рассмотрел бы хеш-таблицу, которая обрабатывает хэш-коллизии с самоуравновешивающимся двоичным деревом вместо простого объединения в цепочку. Необходимо смочь добраться, O (1) амортизируемый ищут по всем ключам и худшему поиску случая O (logN). Так как Ваше ключевое распределение скашивается, вероятно, что у Вас будут коллизии с низкими значениями индекса, и древовидный поиск действительно окупится там.

Вы могли попробовать открыто обращенный хеш квадратичным зондированием вместо отдельного объединения в цепочку, если Ваш N является обычно маленьким. Необходимо было бы перераспределить от, скажем, начального размера 32 к большим ширинам, если Вы получаете редкий случай N, который переполняет его. Линейное зондирование или сумасшедшее хеширование дадут Вам хорошую производительность, если можно заставить целую структуру помещаться в несколько строк кэша.

Честно я удивлен, что даже стандартная хеш-таблица дает Вам такую скудную производительность. Возможно, Вы могли представить в него для наблюдения, что делает его настолько медленным - если это - сама хеш-функция, используйте простой как power-two модуль (например, ключ и (N-1), где N, как известно, 2^x), который будет способствовать дистрибутивам, центрируемым приблизительно 0 так или иначе. Если это - dcache мисс преследования отдельной цепочки, запишите реализацию, которая хранит первые четыре элемента в каждом блоке в самом блоке так, чтобы Вы, по крайней мере, получили их быстро. Насколько медленный N=1?

Я сохранил бы указатели на структуры, а не сами структуры в цепочках блока: если структуры будут большими, то обход цепочки их будет иметь много неудачных обращений в кэш. С другой стороны, можно соответствовать приблизительно 16 парам ключа/указателя на единственной строке кэша и только заплатить за мисс при нахождении корректного элемента.

Единственное объяснение I видит для описанной проблемы, то, что хеш-функция слишком сложна. Я был бы склонен к двухэтапному подходу:

1) Для маленьких ключей, простого массива указателей. Никакой хеш или что-либо.

2) Для ключей, которые больше, чем размер таблицы, которую Вы выделяете:

Как насчет очень простой хеш-функции, которая распространит кластеризованные ключи:

Лево-порядок 5 битов (я принимаю 32-разрядные целые числа. Если это является 64-разрядным, затем добавляют еще один бит.) число битов, которые на самом деле содержат данные, остальное - просто сумма (отбрасывание несет) исходного ключевого сокращения в блоки однако многих битов, которые Вы используете для цели и добавили вместе.

Обратите внимание, что число значимых бит может быть частично предварительно вычислено - создают 64k таблицу высоких битовых значений. Если высокого уровня слово является ненулевым, используйте его в качестве индекса к таблице и добавьте 16, иначе используйте слово низкоуровневое в качестве индекса. Для 64-разрядных целых чисел, очевидно, необходимо использовать 4 шага вместо два.

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

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

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

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

Я рекомендовал бы список Пропуска здесь. java.util.concurrent пакет имеет хорошую реализацию, если Вы в это.