4 ms·
Java uses a tree instead of a linked list for collided items, so the search performance degrades more gracefully (e.g. O(N) vs O(logN)).
by sedatk 1y ago
Java uses a tree instead of a linked list for collided items, so the search performance degrades more gracefully (e.g. O(N) vs O(logN)).
- 77 1y agoTo be more precise, Java initially uses a linked list for nodes within a bin. If the number of items inside the bin crosses TREEIFY_THRESHOLD (which is 8), then that specific bin is converted into a RB tree. This is detailed in implementation notes comment here: https://github.com/openjdk/jdk/blob/56468c42bef8524e53a929dc2ae603cff05b55e3/src/java.base/share/classes/java/util/HashMap.java#L146 https://github.com/openjdk/jdk/blob/56468c42bef8524e53a929dc...
- jillesvangurp 1y agoDepends on which Map / Set implementation you use. There are multiple, each with different and interesting properties.