История изменений
Исправление Siborgium, (текущая версия) :
Тогда дерево. Смотря какие данные, как распределены.
Можно было бы дополнительно схитрить: для ключей короче некоторой длины, у которых не так много возможных значений (я бы взял длину в 4-8 байт, смотря какая версия SSE доступна) вообще не заниматься никакими хешами, а хранить в массиве как есть, та самая unordered_map и получится. Должно будет хорошо вписаться в кеш. Для ключей длиннее этого значения строить префиксное дерево глубиной в разницу длины и этого значения, в листьях хранить все те же массивы с ключами без префикса.
Исходная версия Siborgium, :
Тогда дерево. Смотря какие данные, как распределены.
Можно было бы дополнительно схитрить: для ключей короче некоторой длины, у которых не так много возможных значений (я бы взял длину в 4-8 байт, смотря какая версия SSE доступна) вообще не заниматься никакими хешами, а хранить в массиве как есть, та самая unordered_map и получится. Должно будет хорошо вписаться в кеш. Для ключей длиннее этого значения строить префиксное дерево глубиной в разницу длины и этого значения, на ветвях хранить все те же массивы с ключами без префикса.