HashMap是如何Put一个元素的
首先,将key进行hash运算,将这个hash值与上当前数组长度减1的值,计算出索引。此时判断该索引位置是否已经有元素了,如果没有,就直接放到这个位置
如果这个位置已经有元素了,也就是产生了哈希碰撞,那么判断旧元素的key和新元素的key的hash值是否相同,并且将他们进行equals比较,如果相同证明是同一个key,就覆盖旧数据,并将旧数据返回,如果不相同的话
再判断当前桶是链表还是红黑树,如果是红黑树,就按红黑树的方式,写入该数据,
如果是链表,就依次遍历并比较当前节点的key和新元素的key是否相同,如果相同就覆盖,如果不同就接着往下找,直到找到空节点并把数据封装成新节点挂到链表尾部。然后需要判断,当前链表的长度是否大于转化红黑树的阈值,如果大于就转化红黑树,最后判断数组长度是否需要扩容。
HashMap是如何Get一个元素的
首先将key进行哈希运算,计算出数组中的索引位置,判断该索引位置是否有元素,如果没有,就返回null,如果有值,判断该数据的key是否为查询的key,如果是就返回当前值的value
如果第一个元素的key不匹配,判断是红黑树还是链表,如果是红黑树,就就按照红黑树的查询方式查找元素并返回,如果是链表,就遍历并匹配key,让后返回value值
你知道HahsMap死循环问题吗
HashMap在扩容数组的时候,会将旧数据迁徙到新数组中,这个操作会将原来链表中的数据颠倒,比如a->b->null,转换成b->a->null
这个过程单线程是没有问题的,但是在多线程环境,就可能会出现a->b->a->b….,这就是死循环
在JDK1.8后,做了改进保证了转换后链表顺序一致,死循环问题得到了解决。但还是会出现高并发时数据丢失的问题,因此在多线程情况下还是建议使用ConcurrentHashMap来保证线程安全问题
说一下你对ConcurrentHashMap的理解
ConcurrentHashMap,它是HashMap的线程安全,支持高并发的版本
在jdk1.7中,它是通过分段锁的方式来实现线程安全的。意思是将哈希表分成许多片段Segment,而Segment本质是一个可重入的互斥锁,所以叫做分段锁。
在jdk1.8中,它是采用了CAS操作和synchronized来实现的,而且每个Node节点的value和next都用了volatile关键字修饰,保证了可见性