Если честно, у меня пока нет никаких мыслей, как это можно развить, чтобы было O(1) без жирных констант на containsДействительно, можно отсортировать данные по частоте заросов на них, скажем на 10% объектов приходится 90% запросов contains/get, тогда можно с обычным линейным пробированием эти 10% запихать первыми (так, чтобы distance от места вставки до реального места был не больше 1.05 скажем), а остальные 90% запихать потом. Тогда мат. ожидание кеш мисса будет близко к 1.
2023-07-28 20:06:28,511 : [INFO] - Start demo
2023-07-28 20:06:29,417 : [INFO] - Populated successfully!
2023-07-28 20:06:29,417 : [INFO] - Inserted : 3160854
2023-07-28 20:06:29,419 : [INFO] - Collision list size : 1839146
2023-07-28 20:06:29,419 : [INFO] - Hash set physical size is 5000000 slots (20000000 bytes)
2023-07-28 20:06:29,419 : [INFO] - Inserted/slots ratio : 63%
2023-07-28 20:06:29,419 : [INFO] - Finish
часто бывал лет 15 назад когда я ставил еще тогда хреновые драйвера NVidia
на всякие SuseLinux, Slack e.t.c. И OpenGL не включался и рендеринг плоской
графики в VLC плеере шел с чудовищными лагами. Не лечилось это никак.
Тогда только сумашедший красноглазик мог играть в игрухи на Linux. Все понимали
что реально Windows была игровой платформой а Linux драйера для Radeon/NV
делали только энтузиасты. И как делали чорт его знает. Может реверс-инжинерингом?
И на windows такой эффект можно словить когда какая-нть Windows-2000 не осилила
найти подходящий драйвер.