Ein Bloomfilter der Hashmap vorgeschalten werden und verhindern, dass bei einer Kollision (bei Millionen unterschiedlichen Werten nicht unwahrscheinlich) die Liste in einem Hashmap-Eintrag durchsucht werden muss.
Eine gute Hashmap skaliert, d.h. die Anzahl der Kollisionen ist dann relativ gering.
Zitat:
Das könnte also schon was bringen.
Das wäre denkbar. Bei den mir bekannten Bloomfilter-Implementierungen werden jedoch verschiedene Hashfunktionen verwendet. Dies dürfte der Pferdefuß werden.