Я посчитал за тебя. Я взял 10M пар рандомных u64 и использовал их как ключ/значение для внесения в native-american/afro-american деревья и те же ключи/значения в хеш-таблички. Прошёлся несколько раз по этим парам, деля их поровну между разным количеством ассоциативных массивов. Например, в первый раз был миллион хештабличек и миллион деревьев, каждое из которых содержало 10 пар ключ/значение. На последней итерации было по сто хештабличек и деревьев, в каждом из которых было 100k пар.При этом на каждой такой итерации я замерял суммарное время создания и время суммирования всех значений хранящихся в контейнерах.
Хештаблички использовали дефолтную хешсумму стандартной растовой реализации хештабличек, то есть с устойчивостью к HashDoS. Память под хештаблички я не предвыделял (размеры можно было посчитать заранее и предвыделить, но я решил, что это будет нечестно по-отношению к деревьям).
Так же, я НЕ пытался намеренно создавать деревья таким образом, чтобы их элементы были бы максимально ровным слоем размазаны по куче -- все пары ключ/значение каждой таблички я вбрасывал серией, чтобы все выделения памяти связанные с деревом были бы последовательны и ничто бы не затёсывалось между ними.
Подробности по ссылке[1]. Ниже результаты (ах, да, euclidian distance нужно игнорить, это типа для грубой проверки одинаковости содержимого получившихся структур).
generated 1000000 + 1000000 maps of size 10
Euclidian distance between sums: 0
htable: (1.4651s, 0.2207s) (GenTime, SumTime)
rtable: (1.2479s, 0.3766s) (GenTime, SumTime)
generated 100000 + 100000 maps of size 100
Euclidian distance between sums: 0
htable: (1.1254s, 0.1540s) (GenTime, SumTime)
rtable: (1.1358s, 0.4749s) (GenTime, SumTime)
generated 10000 + 10000 maps of size 1000
Euclidian distance between sums: 0
htable: (1.3795s, 0.1816s) (GenTime, SumTime)
rtable: (1.4985s, 0.5023s) (GenTime, SumTime)
generated 1000 + 1000 maps of size 10000
Euclidian distance between sums: 0
htable: (1.2782s, 0.2284s) (GenTime, SumTime)
rtable: (2.0798s, 0.5645s) (GenTime, SumTime)
generated 100 + 100 maps of size 100000
Euclidian distance between sums: 0
htable: (1.4600s, 0.2728s) (GenTime, SumTime)
rtable: (6.1659s, 1.3407s) (GenTime, SumTime)
Как видишь, на размерах до сотни пар (ключ, значение) хеш-табличка может создаваться чуть медленнее, но к размеру в 100k пар, дерево создаётся в разы медленнее. Суммирование же всех значений по этим контейнерам всегда быстрее на хеш-табличке. То есть, можно предположить, что при заполнении map'а высчитывание хеша плюс-минус компенсируется кеш-промахами, пока этих кеш-промахов не становится совсем уж много (по нескольку штук на каждую вносимую пару, их ведь O(log(N)) где N -- это количество элементов в дереве). При итерации по всем элементам, когда хештабличке уже не нужно считать хеши, она работает быстрее, хотя дерево продолжает так же мазать мимо кеша.
Я тебе реально говорю, деревья могут быть лучше, если тебе нужно, скажем, сортировать элементы, то есть нужны какие-то особые свойства деревьев. И то, стоит подумать, нельзя ли как-нибудь на хеш-табличке выкрутиться. Но если тебе нужен просто ассоциативное отображение, то деревья в помойку летят сразу.
[1] https://github.com/v-creizer/compare-rbtree-and-hashmap
