黄小华的个人网站
熬过无人问津的日子才有诗和远方!
深析HashMap原理

HashTable(哈希表也叫散列表)底层的put方法使用Synchronized保证线程安全,是一种非常重要的数据结构,与HashMap相似的键值对
但是不可以接受null,应用场景很多。
HashMap的数组称为哈希桶 每个桶包含四个字段
QQ图片20200313203623.jpg Java7是先扩容再插入新值,头插法,结构是数组+链表,hash采用取模运算
Java8是先插入后扩容,尾插法,结构是数组+链表+红黑树,hash采用高位与运算。
Java7的头插法在并发插入数据时可能会形成环,接下来的get查询方法就会死循环(就是指针在两个节点之间互相引用)
Java8采用尾插法解决了死循环问题。
HashMap是线程不安全的,他的put方法在线程并发时可能会丢失数据

put方法的执行过程

QQ图片20200313203628.jpg HashMap有四种构造方法,它的无参构造函数 默认初始容量为16,默认负载因子为0.75 ,即容量达到12(阈值16*0.75)时便扩容一倍,
java7扩容后是重新对元素取模哈希,Java8是通过高位与运算来确定元素是否要移动 结果为0表示不移动 极大地提高了性能, 容量始终是2的幂次倍。
默认0.75的负载因子较为合适,负载因子为0.5太低,临时阈值明显会很小,这样会造成分配内存的浪费,也不满足了哈希表均匀分布的情况。
如果负载因子达到了1的情况,也就是Entry数组存满了才发生扩容,会出现大量的哈希冲突的情况,出现链表过长,因此造成get查询数据的效率。
Java8使用一个Node数组取代了JDK7的Entry数组来存储数据,这个Node可能是链表结构,也可能是红黑树结构,红黑树极大地提高了性能;
如果插入的元素key的hashcode值相同,那么这些key也会被定位到Node数组的同一个格子里,如果不超过8个使用链表存储;
超过8个,会调用treeifyBin函数,将链表转换为红黑树。那么即使所有key的hashcode完全相同,由于红黑树的特点,
查找某个特定元素,也只需要O(logn)的开销。 红节点的子节点一定是黑色 ,一个节点到null的所有路径中的黑节点数目相同
新插入的节点为红色 保持红黑树的结构会进行颜色变换和旋转
深入理解红黑树可以看我另一篇博文