Map接口的实现类:HashMap
底层结构:哈希表
jdk7:数组+链表
jdk8:数组+链表+红黑树
简单源码分析:
HashMap中维护了Node类型的数组table
当HashMap创建对象时,只是对loadFactor(加载因子)初始化为0.75;table还保持默认值null
当第一次添加时,将初始table容量为16,临界值为12(容量*加载因子)
每次添加调用putVal方法:
1.先获取key的二次哈希值并进行取与(&)运算,得出存放位置
2.判断该存放位置上是否有元素,如果没有直接存放,
如果该位置上已有元素,则进行继续判断:
如果和当前元素直接相等,则覆盖
如果不相等,则继续判断是否是链表结构还是树状结构,按照对应结构的判断方式判断相等。
3.将size(是里面数据的个数,不是长度)更新,判断是否超过了临界值,如果超过了,则需要重新resize()进行2倍扩容,并打乱原来的顺序,重新排序。
4.当一个桶中的链表节点数>=8 && 桶的总个数(table的容量) >= 64是,会将链表结构变成红黑树结构(就是有一个桶的节点数大于8的话,就会扩容,直到扩容到桶的数量为64时,会将链表结构变成红黑树结构,所以是两个条件)
所以一个桶中的链表节点数可以超过8个,而且也没有变成红黑树
jdk7和jdk8的区别:
1.jdk7:创建HashMap对象时,则初始table容量为16
jdk8:创建HashMap对象时,没有初始table,仅仅只是初始加载因子。只有当第一次添加时才会初始table容量为16
2.jdk7:table的类型为Entry
jdk8:table 的类型为Node
3.jdk7:哈希表为数组+链表,不管链表的总结点数是多少都不会变成树结构
jdk8:哈希表为数组+链表+红黑树,当一个桶中的链表的节点数>=8 && 桶的总个数(table的容量)>=64时,
会将链表结构变成红黑树结构。