S>>>Это слишком примитивное мышление. Нужно рассмотреть не 1 случай а множество вариантов, в т.ч. создание списка и поиск по хеш-коду. Там нужно сотни разных тестов провести, прежде чем сделать вывод.
O>>Вариант на хэштаблицах имеет нулевую разницу, 40+-1 миллисекунд:
S>А почему вы вставку не измеряете, когда вычисляется хеш?
Вставка будет ожидаемо дважды дольше: генерация рандома + копирование дважды больше объемов в памяти.

Речь шла именно про поиск, я его и померял, потому что:

Да хотя бы поиск по адресам в памяти. 16 байт потребуют введения спец. типа или создавать процессоры в которых есть нейтивный 16-байтный тип

(c) https://rsdn.org/forum/flame.comp/8851284.1

Автор: Shmj
Дата: 12.11 17:30

Напиши на C++ поиск по IP-адресам из черного списка. Сначала напиши для 8-байтных адресов (а это делается нейтивным типом), потом для 16 байт. Сравни скорость работы.

(c) https://rsdn.org/forum/flame.comp/8851259.1

Автор: Shmj
Дата: 12.11 17:00

Вот я написал, скорость отличается максимум на 5%, и это еще раз — без оптимизаций. Даже если говорить про локальность данных у бинарного поиска, то если это будет проблемой (на уровне 5% да), то адреса банально разбиваются на две части, строится две таблицы, каждая содержащая одну половинку каждого адреса, в первую вносятся максимально вариабельная часть адреса и бинарный поиск будет искать по первой таблице лишь изредка залазя во вторую. Разница скорости между 64 и 128 битными адресами по поиску будет примерно ноль.

S>И нужно не в миллисекундах. +- а в процентах.
Ну так разница если и есть то она на уровне рандомных флуктуаций на моей системе. То есть иногда 128 бит работает за 39 мсек, иногда 64 бит за 40 мсек, а иногда наоборот. Зато наглядно видна польза хэштаблиц — как раз становится окончательно пофиг на длину хранимого ключа.