HashMap调整方法实现细节
正如标题所示，这是一个关于HashMap#resize的实现细节的问题 – 当内部数组的大小加倍时。 这有点罗嗦，但我真的试图certificate我对此有了最好的理解……
这发生在此特定桶/箱中的条目以Linked方式存储的时刻 – 因此具有确切的顺序并且在问题的上下文中这是重要的 。
一般来说， resize也可以从其他地方调用，但让我们只看一下这种情况。
假设您将这些字符串作为键放在HashMap （右侧是HashMap hashcode 之后的 HashMap#hash – 这是内部重新散列。）是的，这些都是精心生成的，而不是随机的。
DFHXR - 11111 YSXFJ - 01111 TUDDY - 11111 AXVUH - 01111 RUTWZ - 11111 DEDUC - 01111 WFCVW - 11111 ZETCU - 01111 GCVUR - 11111
这里有一个简单的模式 – 最后4位对于所有这些都是相同的 – 这意味着当我们插入这些键中的8个（总共9个）时，它们最终会在同一个桶中; 在第9个HashMap#put ，将调用resize 。
因此，如果当前在HashMap有8个条目（具有上面的一个键） – 这意味着在该映射中有16个桶，并且它们的最后4个位决定了条目最终的位置。
我们把第九个关键。 此时，将TREEIFY_THRESHOLD并调用resize 。 这些容器加倍到32并且键的另一位决定了该条目的位置（现在是5位）。
最终到达这段代码（ resize时）：
Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }
它实际上并不复杂……它的作用是将当前的bin分成多个条目， 这些条目将移动到其他bin和不会移动到其他bin的条目 – 但肯定会保留在这个bin中。
它实际上非常聪明 – 它是通过这段代码：
if ((e.hash & oldCap) == 0)
这样做是检查下一位（在我们的例子中是第5位）是否实际为零 – 如果是，则表示该条目将保持原样; 如果不是，它将以新箱中的两个偏移力移动。
最后问题是：resize中的那段代码是经过仔细制作的，以便保留该 bin中条目的顺序 。
因此，在将这9个键放入HashMap ，顺序将是：
DFHXR -> TUDDY -> RUTWZ -> WFCVW -> GCVUR (one bin) YSXFJ -> AXVUH -> DEDUC -> ZETCU (another bin)
为什么要保留HashMap中某些条目的顺序。 Map顺序非常糟糕，详见此处或此处 。
维护作为链表实现的箱柜中的订单有两个常见原因：
一个是通过增加（或减少）哈希值来维持秩序。 这意味着在搜索bin时，只要当前项比搜索的哈希值更大（或更少，如果适用），就可以停止。
另一种方法涉及在访问时将条目移动到桶的前面（或更靠近前面）或者仅将它们添加到前面。 这适用于刚访问过元素的概率很高的情况。
我查看了JDK-8的源代码，它似乎（至少在大多数情况下）执行后来的被动版本（添加到前面）：
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java
虽然确实不应该依赖于不保证它的容器的迭代顺序，但这并不意味着如果它是结构性的，它就不能被用于性能。 还要注意，类的实现处于特权位置，以正式方式利用其实现的细节，该类的用户不应该这样做。
如果您查看源代码并了解其实现和利用方式，那么您将承担风险。 如果实施者这样做，那是另一回事！
注意：我有一个算法的实现，它严重依赖于一个名为Hashlife的哈希表。 使用这个模型，有一个2的幂的哈希表，因为（a）你可以通过位屏蔽（＆mask）而不是除法来获得条目，并且（b）简化了重复，因为你只需要每次’解压缩’哈希箱。
基准测试表明，通过在访问时将模式主动移动到其bin的前面，算法获得了大约20％的收益。
该算法几乎利用了细胞自动机中的重复结构，这是很常见的，所以如果你看到一个模式，再次看到它的可能性很高。
地图中的订单真的很糟糕[…]
它不坏，它（在学术术语中）无论如何。 Stuart Marks在您发布的第一个链接上写道：
[…]保留未来实施变更的灵活性[…]
这意味着（据我所知）现在实施恰好保持了订单，但是如果找到更好的实现，将来它将被用于保持订单。