HashMap

HashMap HashMap 1, 特点:

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是线程安全的