Depends. Are you searching for the complicated thing by identity, or in a system that caches identities and/or interns objects of the type you’re handling? All
Of those can result in searches being word-based and thus vectorizable/cache-sympathetic more often.
So now the result of `new HashMap<>()` should be backed by an array for the first 200 elements or so? Potentially the size depending on the L1 size etc.
Comments
This has always been the case. The RAM effects only changed at which point the O(n) stops being faster than the O(log n) solution.
Apparently linear search now beats hashmap if you have less than TWO HUNDRED elements. Crazy!
But when you compare native integers, not something more complicated, right?
Depends. Are you searching for the complicated thing by identity, or in a system that caches identities and/or interns objects of the type you’re handling? All Of those can result in searches being word-based and thus vectorizable/cache-sympathetic more often.
For which key types, hashmap implementation, and hasher? Depending on these factors hashmaps performance can vary a lot.
So now the result of `new HashMap<>()` should be backed by an array for the first 200 elements or so? Potentially the size depending on the L1 size etc.
Not in Java, because a linear search map in Java means traversing over 100 (on average) pointers.
Right, but not once these records/structs/value types arrive anymore I gather.
Does this also mean we need to worry about word aligning our fields?? What about strings?