1, HashMap是Map的一个具体子实现, 存储的是key-value键值对
2, HashMap的结构: 数组+链表+红黑树(jdk1.8才有红黑树) (jdk1.7及其以前只有单纯的数组+链表)
3, HashMap底层的数组: 数组的默认初始长度16, 数组的扩容机制, 默认的加载因子0.75
4, 存储的元素无序(key无序)
5, 不允许存储重复的key:
6, 允许存储null作为key
7, 线程不安全
8, 加载因子/装载因子
HashMap底层数组扩容阈值 = 加载因子*数组长度
(假如数组长度16 只能存储12份key-value数据)
不建议大家修改默认的加载因子, 如果实在要改: 0.5-1之间
9, HashMap如果我们在构造方法里指定初始长度, 它会产生一个大于等于给定值的最小的2的幂值, 作为底层数组长度
10, 在HashMap存储数据的过程中, 要把key-value中的key 计算得到一个"数", 再和底层数组长度取模
"数"是怎么算的? 这个数叫hash值,
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
h = key.hashCode() ^ (h >>> 16)
hashCode值向right移动16位再取异或运算的目的是, 让hashCode的高位和低位充分混合, 最终参加到取模运算中去(还是为了模拟真正的Hash算法其中输入敏感/冲突避免/充分散列的思想)
11, 存储到HashMap底层数组位置的不仅仅只是key-value数据, 而是包含key, value , key的hash值, 和一个next引用的Node结点类型
12, HashMap中不允许存储重复的key, 那么key怎么样才算重复?
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
key的hash值一样, 在hash值一样的基础上, key值直接相等或者相equals 就是重复
13, 如果存储量一份重复key数据, 新的key-value的value, 要覆盖旧对应的key的value
14, 如果key经过计算取模之后得到的下标, 存储了数据, 如果单个数据直接比较, 如果链表按照next下移比较, 如果是个红黑树先根据hash确定大小(确定左右方向), 找到hash一样的位置再比较,
比较的方式统统都是: p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
15, 如果存储的多份key-value数据在链表上, 链表过长会转化为红黑树,
链表长度超过8达到9 的时候 由链表转化为红黑树
16, 链表长度超过8达到9 的时候一定会由链表转化为红黑树? 不一定, 有一个特殊情况
如果底层数组长度小于64的时候, 是优先扩容, 而非转化为红黑树
17, 红黑树有可能转化为链表: 两种情况
1, 删除的时候, 删除的结点是树上的结点, 导致树结点变少
如果这个树, 根, 根的左右子结点, 和根节点左节点左节点, 有任何一个是null, 就由红黑树转化为链表
root == null || root.right == null || (rl = root.left) == null || rl.left == null
2, 扩容的时候, 导致树拆成两部分,
拆成的两步任一部分只要小于等于6个key-value数据, 就要由红黑树转化为链表
18, 如果扩容 一个原本存在于x位置元素, 旧数组长度 n, 扩容之后, 新的位置就两个选择, x 或者 x+n
19, 如果一份key-value数据已经存储到HashMap上, 不要通过引用直接修改( 特殊情况)
2, 构造方法构造方法摘要
HashMap()
构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity)
构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor)
构造一个带指定初始容量和加载因子的空 HashMap。
HashMap(Map m)
构造一个映射关系与指定 Map 相同的新 HashMap。
Hashtable补充
Hashtable 也是Map的子实现 ( Hashtable在jdk1.0时候已经出现)
Hashtable底层结构是 数组+链表 (和HashMap在jdk1.8之前一样)
Hashtable数组的初始容量11, 扩容机制 扩为原来的2倍加一
Hashtable存储元素key无序
Hashtable不允许存储重复的元素
Hashtable不允许存储null 键和null值
Hashtable是线程安全的
