Здравствуйте, vdimas, Вы писали:

V>А там разве не рекурсия?
V>(руки не дошли взять полный код, пока справшиваю словами)
Неа. Там цепочка типов. Внизу лежит LeafNode<int>, над ними — BranchNode<LeafNode<int>, int>, над ними — BranchNode<BranchNode<LeafNode<int>, int>, int>, и так далее.
V>В крайнем случае это можно сделать ручками, но при малой фактической вложенности (единицы десятков, те самые 20-30 максимум) смысла обычно нет.
V>И да, я когда-то более 15 лет назад сравнивал бинарные деревья с N-арными, ну вот 2-4 элемента в узле давали максимум производительности, т.е. увеличение кол-ва элементов в узле ничего не давало. Гораздо больше дал кастомный аллокатор узлов, но вряд ли это поможет в случае дотнета.
Ну вот 16 мне дали объехать и 2, и 8 элементов. На подробное сравнение производительности различных размеров узлов времени не хватило.

V>(Кстате, не увидел у тебя балансировки, но может не весь код смотрел)
Там она просто выкинута, чтобы sharplab.io не тормозил. В исходниках она, естественно, есть.

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

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

V>Но в хеш-таблицах есть еще любопытный способ их построения — через подбор коэфициентов хеш-функции.
V>На пальцах — существует несколько классов хеш-функций, в которых через параметры можно управлять "законом" разброса.
V>Наполнение такой таблицы дорогое, т.к. в процессе наполнения происходит подбор коэфициентов хеш-функции для минимизации конфликтов.
V>Но зато при последующем чтении данных такие таблицы показывают хорошие результаты практически при любых сценариях, например даже в таких, где классические хеш-таблицы с фиксированными хеш-функциями из-за стечения обстоятельств (вернее, данных) вырождаются в своей эффективности до эффективности только механизма, разруливающего конфликты.
V>Т.е. когда классические (дефолтные) реализации хеш-таблиц де-факто профанируются.
Стандартом в наши дни является случайное подсаливание хеша. То есть в пределах запуска VM одинаковые данные получают одинаковый хеш, но после перезапуска — уже нет.
Всё это потому, что случайно нарваться на такое распределение данных, которое перегружает хеш, маловероятно. Если у нас обнаружился перекос — то скорее всего какой-то добрый человек выполняет DOS-атаку, запихивая к нам в API особо подобранные данные. Соль позволяет это предотвратить, и при этом не ухудшает стоимость хеширования.