white_niggerа ты индексный доступ специально делал? Просто для перебора ключей?
Специально. Вообще, главной задачей было сохранить порядок ключей.

Распределение для ELFHash. Словарь Лопатина:

Распределение для ELFHash. Словарь Российских фамилий:

Распределение для ELFHash. Строковые GUIDS:

Aleksandr SharahovНасчет снижения расхода памяти не понял. Нам пофиг где там данные, в таблице или снаружи. Мы тестируем только таблицу, к данным не обращаемся, потому как это все всегда можно сделать как угодно.
Ну вот у тебя элемент таблицы состоит из Hash, Key, Value. Value у тебя объект, 4 байта, у меня Value 16 байт. У таблицы нехилая избыточность, соответственно за счёт неиспользуемых Value набегает хороший оверхед по памяти. Поэтому у меня Value отделены от самой таблицы, за счёт этого экономится память.

Что я сделал с твоей таблицей. Поменял твой 4-байтный Value, на свой 16-байтный Value, дабы корректно оценить скорость вставки. Но из-за этого при поиске твоя таблица стала менее cache friendly, отсюда и отставание. Поэтому я и сказал, что если мне свою таблицу привести ко классической структуре, то она не будет показывать лучший результат на поиске.

Aleksandr SharahovЭто аналог "найти+доступ по индексу", а после этого можно править на месте и все такое. Хотя я не понимаю причем тут вообще это, если тестируем голую таблицу?

Может перетестить надо? )
Не надо. Там всё честно протестировано (на поиске тестировался только поиск, данные по ключам не вычитывались). Я индексный доступ упомянул, просто для того чтобы стало понятнее о другой внутренней структуре моей таблицы.

__Avenger__Спасибо. И как Вам распределение данной функции?
Чем более схожи ключи, тем хуже распределение.

Вот распределение ELFHash для последовательных ключей index1 .. index262144:

Aleksandr SharahovНе понял. Зачем? Правильнее было наоборот сделать. Поменять твой 16 на 4. Данные на вставляем же.
Мне бы пришлось полностью изменять структуру своей таблицы, просто по времени было бы более затратно.

Aleksandr SharahovГлавное, чтобы при тестировании размер элемента в обеих таблицах точно совпадал.
С этим-то как раз и проблема. Без переделки структуры моей таблицы этого не сделать.

Aleksandr SharahovИначе всегда проиграет тот, у кого в таблице размер элемента больше, т.к. там и вставка и поиск обращаются практически по случайным адресам в пределах таблицы. Получается тестируем кеш.
Я же говорил, что напрямую сравнить не получится. Вот сейчас без переделки структуры "просто" заменил свой value на объект, в твоей тоже вернул объект и проверил на реальном железе: по вставке паритет 26/29, на поиске (1 тыс. итераций) 17700/19193. Теперь твоя таблица оказалась в более выгодном положении и на поиске появилось опережение.

Aleksandr Sharahov,

Сделал одинаковым размер элементов таблиц. Пришлось изменить структуру у своей таблицы. В результате вставка/поиск: моя - 25/16761, твоя - 26/16237. У меня переупорядочивание не выполняется.

Aleksandr Sharahovсовсем почти вровень,
посмотрю еще, может получится побыстрее вставку сделать.
Я ещё не убрал дополнительный вызов на вычислении хеша, не стал совсем-то уж маньячить :)

Aleksandr SharahovНе помню, результаты поиска в TDictionary ты приводил?
Приводил, но там было с моим Value. Вот TDictionary<UnicodeString, TObject>: 81/32369