Я знаю, что могу просто использовать массив сегментов для ассоциативного контейнера, если у меня есть равномерно распределенные целочисленные ключи или ключи, которые можно преобразовать в равномерно распределенные целые числа. Если я смогу создать достаточно большой массив, чтобы обеспечить определенный коэффициент загрузки (который предполагает, что коллекция не слишком динамична), то ожидаемое количество коллизий для ключа будет ограничено, потому что это просто хеш-таблица с хеш-функцией идентификации.
Изменить: я рассматриваю строки как эквивалентные позиционным дробям в диапазоне [0..1]. Таким образом, они могут быть отображены в любой целочисленный диапазон путем умножения и получения результата.
Я также могу эффективно выполнять префиксные запросы, как и с попытками. Я предполагаю (не зная доказательства), что ожидаемое количество пустых слотов, соответствующих заданному префиксу, которые должны быть последовательно пропущены до того, как будет достигнуто первое ведро с хотя бы одним элементом, также будет ограничено константой (опять же в зависимости от выбранный коэффициент нагрузки).
И, конечно же, я могу выполнять колющие запросы в наихудшем постоянном времени, а запросы диапазона — исключительно в линейное ожидаемое время, зависящее от вывода (если гипотеза о плотности из предыдущего абзаца действительно верна).
Каковы преимущества попытки тогда?
Если распределение равномерное, я не вижу ничего, что могло бы улучшить ситуацию. Но я могу ошибаться.
Если распределение имеет большую некомпенсированную асимметрию (потому что у нас не было априорных вероятностей или мы просто рассматривали наихудший случай), массив сегментов работает плохо, но попытки также становятся сильно несбалансированными и могут иметь линейную производительность в наихудшем случае со строками произвольной длины. Таким образом, использование любой структуры для ваших данных сомнительно.
Итак, мой вопрос: каковы преимущества производительности попыток над массивами сегментов, которые можно формально продемонстрировать? Какие дистрибутивы обеспечивают эти преимущества?
Я думал о дистрибутивах с самоподобной структурой в разных масштабах. Я полагаю, что это так называемые фрактальные распределения, о которых я ничего не знаю. Возможно, тогда, если дистрибутив склонен к кластеризации в каждом масштабе, попытки могут обеспечить превосходную производительность, сохраняя одинаковый коэффициент загрузки каждого узла, добавляя уровни в плотных регионах по мере необходимости - что-то, что массивы сегментов не могут сделать.
Спасибо
