Java Collection - Concrete data structure under the hood for dictionary/tree based abstract data structure
-
12-06-2021 - |
Question
My question is about what are the fundamental/concrete data structure (like array) used in implementing abstract data structure implementations like variations maps/trees?
I'm looking for what's used really in java collection, not theoretical answers.
Solution
Based on quick code review of Sun/Oracle JDK. You can easily find the details yourself.
Lists/queues
ArrayList
Growing Object[] elementData
field. Can hold 10 elements by default, grows by around 50% when cannot hold more objects, copying the old array to a bigger new one. Does not shrink when removing items.
LinkedList
Reference to Entry
which in turns hold reference to actual element, previous and next element (if any).
ArrayDeque
Similar to ArrayList
but also holding two pointers to internal E[] elements
array - head
and tail
. Both adding and removing elements on either side is just a matter of moving these pointers. The array grows by 200% when is too small.
Maps
HashMap
Growing Entry[] table
field holding so called buckets. Each bucket contains linked list of entries having the same hash of the key module table size.
TreeMap
Entry<K,V> root
reference holding the root of the red-black balanced tree.
ConcurrentHashMap
Similar to HashMap
but access to each bucket (called segment) is synchronized by an independent lock.
Sets
TreeSet
Uses TreeMap
underneath (!)
HashSet
Uses HashMap
underneath (!)
BitSet
Uses long[] words
field to be as memory efficient as possible. Up to 64 bits can be stored in one element.
OTHER TIPS
There is of course one answer for each implementation. Look at the javadocs, they often describe these things. http://docs.oracle.com/javase/7/docs/api/