这是一个创建于 1799 天前的主题，其中的信息可能已经有所发展或是发生改变。
在我看来，头插法和尾插法都要遍历一遍链表啊，应该不是效率问题吧.
 | 1 VincentWang 2021-01-12 18:32:25 +08:00 有一种说法是：缓存的时间局部性原则 (新插入的数据可能会更早用到) |
 | 2 DengDDDD OP  1 我刚看了遍源码，得出一个结论，感觉还挺像的 插入时需要判断是否重复，此时要遍历一遍链表， 如果采用尾插法，需要将尾节点保存起来，传入后面的 addEntry 的方法中 addEntry 会判断是否需要扩容，如果扩容的话，待插入节点的下标就需要重新计算， 这样之前保存的尾节点就不一定正确，需要在重新计算一次尾节点， 所以说使用头插法效率会高一些 |
| 3 DengDDDD OP @VincentWang 刚刚不知道如何回复。 |
 | 4 qwerthhusn 2021-01-12 20:41:26 +08:00 插头插尾都无所谓，因为链表长度达到 8 （好像是 6，忘记了）的时候，就变成红黑树了， 长度个位数的链表，咋遍历都不会影响性能 |
 | 5 kx5d62Jn1J9MjoXP 2021-01-12 21:04:53 +08:00 via Android 因为简单啊，怎么简单怎么来呗 |
 | 6 emSaVya 2021-01-12 21:40:07 +08:00 头插有概率形成死循环 1.8 以后改成尾插 |
 | 7 cco 2021-01-13 09:31:28 +08:00 @qwerthhusn 这不是 1.8 后才有的么？ |
| 8 DengDDDD OP @qwerthhusn，在 1.8 之后确实不用考虑这个问题了，但是我当时奇怪的是 1.7 为什么用的头插法。 @emSaVya 对，就是因为头插法会形成环形链表，所以我才好奇为什么不用尾插法，当时我以为效率一样，后面发现其实是不一样的。 |
 | 9 ffhigh 2021-01-13 10:42:53 +08:00 如果 1.7 只改尾插， 不改扩容机制。 也不会形成环么？ |
 | 10 qifeng7 2021-01-15 14:49:41 +08:00 可能是在扩容迁移元素的过程中，用头插法更快 |
| 11 qifeng7 2021-01-15 14:50:57 +08:00 1.7 是一个元素一个元素迁移的，用尾插法就要遍历到链表尾部再插入 |
| 12 qifeng7 2021-01-15 14:53:19 +08:00 扩容转移元素不需要遍历一遍链表哦 |
Select Language