Collection-2

前序:此篇介绍Map和Set,为什么放在一起,通过了解可以知道,大多数的Set内部实现都是Map,Map里的KeySet就是个Set,而Value是假值,同一个Object。

为什么说是大多数,因为有特例JUC包里有个CopyOnWriteArraySet内部是CopyOnWriteArrayList

Map相关的问题主要是HashMap的数据结构,哈希算法、扩容机制、线程安全、是不是有序的,有序的是什么、如果保证顺序的 保证顺序的方式 哪个比较好、有没有更好的实现方式

2. 集合框架 

    2.2 Map

HashMap 

容量 1 << 4 (16)  load factor 0.75f

结构 

1.7 ->transient Entry<K,V>[] table; 

1.8-> Node<K,V>[] table;

扩容 

1.7 ->resize(2 * table.length); 

1.8  newThr = oldThr << 1;

特点  

Hashtable 

容量 this(11, 0.75f);

结构 Entry<?,?>[] table;  

final int hash;

        final K key;

        V value;

        Entry<K,V> next;

扩容 newCapacity = (oldCapacity << 1) + 1;

特点 线程安全  所有方法同步修饰 synchronized

LinkedHashMap

容量 1 << 4 (16)  load factor 0.75f

结构 afterNodeAccess Entry<K,V> before, after;

扩容 1.7 ->resize(2 * table.length); 1.8  newThr = oldThr << 1;

特点 有序 双向链表保证顺序

    TreeMap 实现NavigableMap接口

容量 无限 size

结构 

       K key;

       V value;

       Entry<K,V> left;

       Entry<K,V> right;

       Entry<K,V> parent;

       boolean color = BLACK;

扩容 无限

特点 有序 自平衡二叉树 红黑树

2.3 Set   

Hashset ->HashMap

容量 

结构  

transient HashMap<E,Object> map;

public HashSet() {

map = new HashMap<>();

}

扩容 return map.put(e, PRESENT)==null;

特点

LinkedHashset -> HashSet->LinkedHashMap->HashMap

容量 1 << 4 (16)  load factor 0.75f

结构 

afterNodeAccess Entry<K,V> before, after;

public boolean add(E e) {

       return map.put(e, PRESENT)==null;

}

扩容 见HashMap

特点

TreeSet  TreeSet->NavigableMap的实现类TreeMap

容量 无限

结构 NavigableMap->new TreeMap<E,Object>()

扩容 无限

特点

评论已关闭。