3 ms·
Interestingly in Java 8 they changed HashMap buckets to hold a binary tree instead of linked list to change from O(n) to O(log N). https://stackoverflow.com/qu
by rb808 8y ago
Interestingly in Java 8 they changed HashMap buckets to hold a binary tree instead of linked list to change from O(n) to O(log N).
https://stackoverflow.com/questions/24673567/change-to-hashmap-hash-function-in-java-8 https://stackoverflow.com/questions/24673567/change-to-hashm...
- utopcell 8y agoTo be more accurate, binary trees are constructed only after a bucket ends up containing a small number of elements, which should only happen rarely unless a bad hash function is chosen.
- dbaupp 8y agoThat's defending against hash collisions which isn't what the grandparent is noticing (the slowing down of memory accesses due to not fitting into cache).
- josefx 8y agoI think they implemented that change to deal with a denial of service attack in http servers. A malicious client could send a large list of parameters with an identical String::hashCode() value, resulting in a single large bucket. Other workarounds included a size limit on the parameter list or a hash function with some parameters randomized at program start.
- 2FC00C733A55 8y agoFYI this only happens if the objects implement comparable; if you do not, they will not make binary trees.