Если честно, у меня пока нет никаких мыслей, как это можно развить, чтобы было 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
Попробуй декодируй его онлайн-сервисами и посмотри что там внутри.