06 为什么头插法容易形成死循环而尾插法不会

vvEcho 2024-01-20 14:08:36
Categories: Tags:

其实这个问题是jdk1.7版本下的hashMap多线程情况下发生的,hashMap扩容时采用头插法链表的顺序可能发生变化,导致线程1中链表指针原本由A指向B,在线程2中链表指针由B指向A, 由于彼此都不可见;那么循环指向就产生了;

jdk1.8则是先插入然后再进行扩容且采用的是尾插法,这样新来的元素位置就是确定的,只用建立新的指针就好了,避免了链表元素的位置变动,从而避免了循环链表的产生

总结
JDK1.7 扩容迁移头插法会把链表顺序反转,多线程同时访问可能看到 next 指针被覆盖 → 循环链表;
JDK1.8:先插入再扩容 + 尾插法 → 链表顺序稳定 → 避免循环链