Java集合之LinkedHashMap, TreeMap, HashSet, LinkedHashSet和TreeSet的底层实现

LinkedHashMap

  • LinkedHashMap是一个维护了插入顺序的HashMap,通过继承HashMap实现
  • LinkedHashMap在Map的实现上通过继承HashMap实现,在此基础上维护了一个双向链表,根据Key访问元素用的是HashMap,按序迭代的时候用的是双向链表
// LinkedHashMap维护的双向链表 transient LinkedHashMap.Entry<K,V> head; transient LinkedHashMap.Entry<K,V> tail; // LinkedHashMap.Entry<K, V> static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }

TreeMap

  • TreeMap 实现的是NavigationMap这个接口,NavigationMap继承自SortedMap
  • TreeMap 是一个排序Map,内部是靠红黑树实现的。内部有一个静态类实现红黑树的结构和Map.Entry接口
  • TreeMap key不允许设置为Null
// TreeMap实际维护的数据 private transient Entry<K,V> root; static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK; // 其他代码 }
  • TreeMap可以传入一个Comparator接口用于制定Key的排序规则
  • 如果没有传入,则需要 Key 实现Comparable接口

HashSet

  • HashSet把所有的实现都委托给了HashMap
  • HashSet使用了HashMap的key不能重复的性质,把每个元素都当作key存在HashMap中,而value只存一个Object对象的引用
private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public boolean add(E e) { return map.put(e, PRESENT)==null; } public Iterator<E> iterator() { return map.keySet().iterator(); }

LinkedHashSet

  • LinkedHashMap继承自HashSet,直接委托给LinkedHashMap了,
    下面这段代码是LinkedHashSet的所有构造器,实际上也没有重写任何一个Set的接口,直接调用了父类的构造器,
    这个构造器是一个包内访问构造器,专门用来实现LinkedHashMap的
// LinkedHashSet public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true); } public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true); } public LinkedHashSet() { super(16, .75f, true); } public LinkedHashSet(Collection<? extends E> c) { super(Math.max(2*c.size(), 11), .75f, true); addAll(c); } // 以上四个构造器都调用了下面这个构造器 // HashSet HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } // HashSet

TreeSet

  • TreeSet是一个排序Set
  • TreeSet的所有方法实现都委托给了一个NavigationMap, 同HashSet一样value都是一个Object对象
  • 可以自己传入NavigationMap的实现,默认使用TreeMap
阅读(42)
评论(0)
updated@2020-11-03
评论区
目录