昆山建设信息网站,ps制作网站过程,福州市城乡建设发展总公司网站,wordpress加代码广告HashMap底层数据结构在1.7与1.8的变化
1.7是基于数组链表实现的#xff0c;1.8是基于数组链表红黑树实现的#xff0c;链表长度达到8时会树化
使用哈希表的好处
使用hash表是为了提升查找效率#xff0c;比如我现在要在数组中查找一个A对象#xff0c;在这种情况下是无法…HashMap底层数据结构在1.7与1.8的变化
1.7是基于数组链表实现的1.8是基于数组链表红黑树实现的链表长度达到8时会树化
使用哈希表的好处
使用hash表是为了提升查找效率比如我现在要在数组中查找一个A对象在这种情况下是无法根据数组下标查找的这样我们就需要从数组头部开始将A对象与数组元素依次比较直到找到A对象这样显然是比较麻烦的如果使用了hash表我们只需要计算出A元素的hash值通过hash值找到其在数组中的索引就可以很快的找到A元素了当然一个索引对应的很可能不止一个元素所以需要使用数组链表的形式但如果链表的长度过长查找时还是需要沿着链表一一比对这样也是比较消耗性能的为了避免链表长度过长造成的查找效率下降有两种解决方案1是数组扩容2是链表树化
HashMap底层数组的扩容
底层数组默认长度是16当数组使用超过最大长度的0.75这个0.75被称为负载因子则会对该数组进行扩容扩容为原来长度的两倍扩容结束之后由于数组的长度发生了变化元素位置的确定是由元素哈希值对数组长度取模因此会重新计算集合元素在数组中的存储位置因此扩容前存在的链表结构很可能会消失这样也就在一定程度上解决了链表长度过长的问题
负载因子为什么选择0.75
在空间占用与查询时间之间取得较好的权衡大于这个值空间节省了但链表就会比较长影响性能小于这个值冲突减少了但扩容就会更频繁空间占用也更多
链表树化
链表的树化有两个必要条件一是数组长度大于等于64二是链表长度必须超过8如果链表长度超过了8但是数组长度小于64那么会直接对数组进行扩容此时不考虑阈值的问题而非将链表树化也就是说在数组长度小于64时链表长度是可能大于8的当上述两个条件都满足时链表会树化为红黑树红黑树的一个特点是父节点左侧的都是比它小的元素父节点右侧的都是比它大的元素因此在元素较多的情况下红黑树的查找效率就比链表要高很多了这也就是jdk1.8使用数组链表红黑树的意义
链表的树化我们还需要思考几个问题 为什么不一上来就树化 在链表短时没有必要进行树化在链表比较短的情况下无论是查询还是更新其性能都要高于红黑树而且红黑树的内存占用比链表高红黑树是由TreeNode组成的而链表是由Node组成的TreeNode的成员变量要比Node多很多因此没有必要一上来就树化 树化阈值为什么选择8 首先需要说明的是虽然HashMap底层数据结构使用的是数组链表红黑树但是正常情况下是几乎不可能出现红黑树的如果hash 值足够随机则在 hash 表内按泊松分布在负载因子 0.75 的情况下长度超过 8 的链表出现概率是 0.00000006一亿分之六之所以树化阈值选择 8 就是为了让树化几率足够小
正常情况下链表几乎不可能树化红黑树存在的意义主要是用来避免 DoS 攻击的是用来应对偶然情况的一种保底策略
红黑树退化成链表
链表会树化成红黑树红黑树也会退化成链表红黑树退化的场景
数组扩容时会对红黑树进行拆分若拆分后树的元素小于等于6则退化为链表remove任意一个树节点之前若root根节点、root.left根节点的左孩子、root.right根节点的右孩子、root.left.left根节点的左孙子 有一个为 null 那么remove完成后树也会退化为链表
索引的计算过程
对象先调用其自身的hashCode方法计算出hash值再由HashMap的hash方法对这个hash值进行二次hash二次hash的结果再使用位与运算hash值 (数组长度 – 1)得到这个对象在hash表中的索引
这个过程中也有几个问题需要思考 数组容量为何要设计为2的n次幂 如果数组容量是2的n次幂则位与运算与取模运算的结果是相同的可以用位与运算代替取模运算且效率更高在数组扩容时如果数组容量是2的n次幂那么扩容时重新计算索引效率更高只需要将链表中每个元素与oldCap扩容前的容量做位与运算如果结果为0那么说该元素在扩容后会保留在原位置如果结果不为零那么该元素在扩容后位置会发生变化这样遍历下来就可以把原来的链表拆分成两个链表一是位置不需要移动的二是位置需要移动的在扩容后位置需要移动的链表的新位置的索引旧位置oldCap容量设计为2的n次幂虽然可以提高计算索引时的效率但是会导致hash的分布性变差比如说我现在要存放一组较小的偶数那么这些偶数就会集中在数组的偶数索引位置上在没有经过二次hash的情况下因此为了避免这种情况需要进行二次hash如果我们选择质数作为数组容量那么hash的分布性是很好的我们完全不需要进行二次hash即使这样HashMap仍然选择2的n次幂作为数组容量是出于更看重效率的角度出发的 为什么要进行二次hash 之所以要进行二次hash是为了让hash分布的更为均匀避免一组数据的hash值集中在某些索引上导致链表过长
Put元素流程
HashMap 是懒惰创建数组的首次插入元素时才会去创建数组假如说现在要插入一个元素A流程如下 计算出元素A的索引值 如果该索引上没有元素则创建元素A的Node节点占位并返回 如果该索引上已经有元素了则 如果该索引位置上的元素是TreeNode则走红黑树的添加或更新逻辑如果该索引位置上的元素是Node则走链表的添加或更新逻辑添加完毕后如果链表长度超过树化阈值走树化逻辑 是添加还是更新需要比对元素A与其他元素的hash值hash值不同走添加逻辑hash值相同则调用元素的equals方法进行比对返回false走添加逻辑返回true走更新逻辑 返回前检查容量是否超过阈值一旦超过则对数组进行扩容
上述过程中1.7 的实现与 1.8 的实现有所不同
1.7 使用头插法新增的元素会插入到链表头部1.8 使用尾插法新增的元素会插入到链表尾部1.7 是数组使用长度超过阈值且再次put时put的索引位置上已经有元素了才会去对数组扩容 1.8 是使用长度超过阈值就会扩容1.8 在扩容计算 Node 索引时会进行优化这个优化上面提到过1.7是没有这个优化的
多线程下HashMap存在的问题
数据丢失假如现在HashMap索引为1的位置上是空的现在有t1和t2两个线程同时希望在该位置上插入元素假设此时t1希望插入元素A那么首先t1线程需要检查该位置上是否已经存在元素经过检查后发现不存在元素正当t1线程准备插入元素时发生了线程切换CPU执行权给到了t2线程t2线程将要插入元素B那么它首先还是会去检查该位置是否存在元素结果当然是也不存在于是t2线程便在该位置上插入了元素B然后返回如果此时执行权再次给到t1线程那么t1线程插入元素A就会把原来位置上的元素B给覆盖这样就丢失了一次数据更新并发扩容死链存在于jdk1.7中在1.7中由于使用头插法当两个线程同时对数组进行扩容时很有可能会产生死链环形链表此时一旦有任意查找元素的动作线程将会进入死循环导致CPU飙升1.8使用尾插法避免了这一问题
HashMap的key是否为null作为key的对象应该有哪些要求
HashMap 的 key 可以为 nullMap 的其他实现则不然作为 key 的对象必须实现 hashCode 和 equals 方法并且要保证 key 的内容不能修改不可变一旦key被修改了那么其hash值就会发生变化那么就无法找到其在hash表中的索引了key 的 hashCode 应该有良好的散列性
HashMap和HashTable的区别
HashMap线程不安全HashTable线程安全(大多使用Synchronize修饰)所以相对来说HashMap要更快一些这是最主要也是最重要的区别HashMap的key和value都允许为null而HashTable键值对都不能为空否则会报空指针异常HashMap在计算Hash值时需要二次Hash而HashTable不需要原因在于HashTable不使用2的n次幂来作为数组长度Hash分布更加均匀接上一点既然说了HashTable不使用2的n次幂来作为数组长度那就需要提一下HashTable的扩容规则了HashTable的数组扩容是扩容为原来的两倍加一而HashMap是扩容为原来的两倍Java8中HashMap使用数组链表红黑树的形式而Java8中HashTable仍然是数组链表
