- HashSet和TreeSet 实质上是对Map的封装
- HashMap
- 数据结构是数组table+链表(Node<K,V>)\红黑树(TreeNode<K,V>),初始容量为16,加载因子为0.75,每次扩容为原来的二倍
- put()方法放入键值对时,根据key的hash值确定index = table.length-1 & hash,然后按照链表或者红黑树的逻辑插入Node。table中的元素存储的是头结点
- Node<K,V> 是静态内部类,对Map.Entry内部接口的实现,有四个成员变量,hash是key和value的hash值的异或,key默认,value默认,还有一个Node next,说明是单向链表
- TreeNode<K,V> 是静态内部类,对LinkedHashMap.Entry静态内部类的实现,TreeNode有5个成员:parent,left,right,prev,是否是red,LinkedHashMap.Entry 有 before和after
- 扩容在当前键值对插入后判断的,当table大小超过 容量*装载因子 时,扩容
- 线程不安全的原因:
-- jdk1.7中扩容使用头部插入,是可能发生循环死锁,CPU可以达到100%;jdk1.8在扩容时使用尾部插入,不会发生死锁
-- put 方法可能会发生覆盖问题 - Entry<K,V> 主要方法有 getKey() getValue() 等
- ConcurrectHashMap
- key和value不可以是null值
- 线程安全的原因是在put、remove、resize等操作时会对当前 Node f加同步锁 synchronized(f)
- TreeMap
- 基于红黑树的对NavigableMap接口的实现
- 构造方法: TreeMap(Comparator<? super K> comparator)
- 挖坑:红黑树
- 挖坑:LinkedHashMap