HashMap
HashMap主要结构
- 数组加链表
- 数组加红黑树
存放数据的对象
- Node <- Map.Entry
- TreeNode <- Node <- Map.Entry
默认构造函数
- 数组默认初始化容量 1 << 4
- 数组最大容量 1 << 30
- 默认负载因子 0.75f
- 负载阀值 = 容量 * 负载因子
- 链表树化阀值，链表长度大余等于8
- 树结构链化，树的大小小余等于6
- 树化最小数组长度，也就是如果数组长度小于64，如果遇到链表长度大于树化阀值，则是扩容数组，而不是将链表树化
初始化
- 构造HashMap时，数组还未真正初始化
- 构造HashMap时，主要设置数组大小，负载因子，负载阀值
- 使用旧的HashMap构造新的HashMap，会resize初始化数组，并且把旧数据加入
- 构造一个空HashMap，在第一次put时才会通过resize初始化数组
数组长度和扩容规则
- 数组长度为2的N次幂，如：1、2、4、8、16
- 扩容就是在原来基础上乘以2
- 当数据个输超过阀值则扩容
- 当链表准备树化发现数组长度小于64时，优先扩容
运算方式
- 主要通过位运算
- hash值和数组长度减一与运算(&)，获取下标
备注
- HashMap非线程安全
- 计算hash值高16位和低16位进行异或运算，使高低位都参与运算
- 如果是链表，则在尾部插入
其他
- & 与
- | 或
- ~ 非
- ^ 异或
Hashtable
默认构造参数
- 默认的数组容量为 11
- 默认的负载因子为 0.75
- 初始化的时候，负载阀值默认为初始化容量
- 构造方面内就把数组初始化
简介
- Hashtable是线程安全的
- 方法用synchronized关键字修饰，对象级别的锁
- put的value不能为null，否则报错
- 下标是通过求余(%)来计算
- 输入通过链表头部插入
扩容规则
- 扩容方法rehash()
- 数据量大于等于负载阀值开始扩容
- hash值直接通过Object.hashCode()获取
- 扩容大小为(旧容量 * 2) + 1
- 负责阀值为容量大小 * 负载因子
存放数据的对象
- HashtableEntry <- Map.Entry
HashSet
原理
- HashSet有个内部成员变量map为HashMap，操作都与map有关
- 数据存放规则和HashMap一样
- add存放的值对应HashMap的key,value为PRESENT的一个Object(),所以可以为null
- HashSet非线程安全
总结
- HashSet就是一个只关心key不关心value的HashMap封装类
HashMap和Hashtable的区别
- 扩容规则HashMap是2的幂次，Hashtable是当前容量*2+1
- 链表插入HashMap是尾部插入，Hashtable是头部插入
- HashMap会树化，Hashtable一直是链表
- 下标计算HashMap是通过与运算，Hashtable通过求余
- HashMap非线程安全，Hashtable线程安全
- 默认情况下，HashMap在put才会初始化数组，Hashtable构造方法内就初始化
- hash值HashMap是高低16位通过异或运算，Hashtable直接获取Object的hashCode
