Why does Gauva cache doesn't implement Concurrent hash map using red black tree in the worst case collision?

Skip to first unread message

Abhishek Jha

Oct 13, 2021, 12:37:00 AM10/13/21
to guava-discuss

LocalCache : https://github.com/google/guava/blob/master/guava/src/com/google/common/cache/LocalCache.java#L91

It says that it is based on ConcurrentHashMap implementation from jdk.

Jdk ConcurrentHashMap : https://github.com/frohoff/jdk8u-jdk/blob/master/src/share/classes/java/util/concurrent/ConcurrentHashMap.java

The jdk yses RB-Tree to optimise collision in the worst case scenario.

Why does Gauva avoid this? Do they not expect such collision? It can degrade to O(n) in the worst case scenario. The hash function can be easily targeted to create input where all the keys fall in the same bucket thus degrading to a Linkedlist. How/Why does Gauva avoid this?

Benjamin Manes

Oct 13, 2021, 1:06:25 AM10/13/21
to Abhishek Jha, guava-discuss
Guava’s cache was written for Java 5 and is based on it’s concurrent hash table design. This was initiated in 2009 with MapMaker and much of the caching work in 2010. The modern ConcurrentHashMap was introduced in Java 8 (2014), with a backport available in 2012. Caffeine, a rewrite of the cache based on this map, was started in 2014. That builds on the best ideas of Guava and includes many learnings of where we might have done better.

Project site: https://github.com/google/guava
This group: http://groups.google.com/group/guava-discuss
This list is for general discussion.
To report an issue: https://github.com/google/guava/issues/new
To get help: http://stackoverflow.com/questions/ask?tags=guava
You received this message because you are subscribed to the Google Groups "guava-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to guava-discus...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/guava-discuss/4213090b-3021-494e-9f1c-657d896a9c4fn%40googlegroups.com.
Reply all
Reply to author
0 new messages