红石粉更新的数学规律
- 97% 情况下,7 个更新核分为 3 组:
{原点}、{-Y, +Z, +X}、{+Y, -Z, -X},组内顺序固定,组间有 6 种排列。 - 这97% 情况里,
{原点}一组在中间的概率为50%。 - 失效点(3%) 出现在
hashCode低 16 位接近边界(0 或 65535)的位置,沿 X 轴影响范围最广(一千多格),沿 Z 轴最窄(仅 2 格)。 - 更新顺序实际仅有 60 种可能组合(而非理论的 5040 种)。
前言
我们知道红石粉的更新存在空间上的随机性。因此,玩家们通常认为其更新顺序是无法预测的,并且认为没有必要花时间去预测这些变化。不过,实际上,红石粉的变化和更新顺序是有一定的数学规律可循的
数学规律
在粉的更新顺序中,存在着某些数学模式。这些模式可以用于控制红石线的激活顺序,而这些模式的发现要归功于像 EarthComputer 等早期开始研究的玩家。
要了解这些模式,我们需要从 HashSet 的结构来分析。
红石粉的更新利用了 HashSet。HashSet 是一种基于哈希表的数据结构,它能通过键(Key)高效地直接访问相关的值(Value)。其中的存储过程大致如下:
Object(物品)
│
│ hashCode() 计算 哈希值
↓
hash(哈希值)
│
│ 某种转换+扰动
↓
bucket index(哈希桶号)
│
↓
HashTable[bucket index](哈希表)
│
├── 物品A
├── 物品B
└── …想象有一组固定数量的抽屉,桶号(bucket index)就相当于这些抽屉的编号。物品依据其某种特征(hashCode)通过某种计算规则决定应放入哪个抽屉。
如果多个物品被分配到相同的抽屉,较早加入的会排在前面,后加入的则在后面。这种情况可能会导致“哈希冲突”,从而增加查找某个特定物品时所需的时间。因此,我们希望物品的hashCode()结果尽可能分散开来。
HashSet默认有16个“抽屉”,遍历时按序号从低到高进行。当存储的对象过多时,抽屉数量会增加。然而,红石粉的更新核恒定有7个,所以不会触发数量扩充。
这7个更新核按照 O -Y +Y -Z +Z -X +X的顺序依次加入这个HashSet。如果被分配到同一个抽屉,那么这些更新核会按这个加入顺序被激发。每个更新核虽然激发顺序不同,但击发后按照NC更新顺序向毗邻发出更新。
哈希值的计算由游戏决定:
hashCode = x + 31 * (y + 31 * z)通过哈希值计算序号的公式由Java决定:
hash = hashCode ^ (hashCode >>> 16);
bucketIndex = (length - 1) & hash这些特性共同带来了一些规律。
规律1 :
虽然有默认16个“抽屉”但 大约97%的情况下,七个更新核往往仅落在其中三个中。其中,原点O独自成落入一个抽屉,-Y、+Z、+X落入同一个抽屉,而+Y、-Z、-X落入同一个抽屉。
为何会这样呢?
一个粉的7个更新核,分别是 粉位置,与粉周围六个毗邻位置。 其中,相对于粉自身的位置,它们仅在x,y,z轴增减1格。
回顾哈希值算式: hashCode = x + 31 * (y + 31 * z) = x + 31y + 961z
这意味着: 当x轴±1时,哈希值仅± 1; 当y轴±1时,哈希值± 31; 当z轴±1时,哈希值± 961 。
实际上,7个更新核的哈希值是相当接近的。再看哈希桶号的算式前半: hash = hashCode ^ (hashCode >>> 16);
这里的计算含义是:提取哈希值的高16位并与整个哈希值进行异或操作。
一个32位整数的低16位能够代表 65536 种不同的数值。这7个更新核的 hashCode 最大差异仅为 1922。
因此,只要粉自身坐标的 hashCode 距离 65536 和 0 的距离大于 1922, 周围更新核的 hashCode 的增减将不会跨越低16位的界限,这些更新核心的高16位就不会变化。
换句话说,在绝大多数情况下,这7个更新核心的 hashCode 可以看作是:相同的高16位与不同的低16位组合。 而hashCode >>> 16正好是在提取这个相同的高16位。
所以,很多时候,7个更新核心实际上都是用相同的高16位与各自的低16位进行异或操作。 此时,真正导致差异的,仅仅是 hashCode 的低16位。
然后是后半段: bucketIndex = (length - 1) & hash
由于默认16个抽屉且不扩容,length是16。
所以实际上是 bucketIndex = 15 & hash
而15 = 0000 0000 0000 1111,这意味着,桶号实际上只取最终 hash 的最低4位。hash的这最低4位的根基,是hashCode的最低4位。因此我们真正需要关注的,还是hashCode自己的最低4位。
而 hashCode 是由x + 31y + 961z得到的。因为31除以16的余数和-1相同,961除以16的余数和1相同,所以这个 hashCode 的最低4位,实际上只与x - y + z有关。
设中心点x - y + z的结果为A:
+X: A + 1
-X: A - 1
+Y: A - 1
-Y: A + 1
+Z: A + 1
-Z: A - 1致此可以证出3个分组:
原点O独自成落入一个抽屉,-Y、+Z、+X落入同一个抽屉,而+Y、-Z、-X落入同一个抽屉。这三个分组里,按照前文列出的顺序(同样也是7个更新g核加入HashSet时的顺序)依次激发更新核。但3个组谁先谁后仍有3x2x1=6种组合。
那97%的概率又是哪来的呢?
我们先前提到过,7个核高16位相同的前提是:没有刚好跨过低16位的边界。
65535个数字中,多少数字跨越了这个边界呢?既然最极端差距是之前提到的1922,可以确定65535个数字中有1922个数增减时会跨过边界。其出现的概率是1922/65536 ≈3 %。 那么剩下的,“安全”的,出现“原点O独自成落入一个抽屉,-Y、+Z、+X落入同一个抽屉,而+Y、-Z、-X落入同一个抽屉”的情况的概率就是97%了。
文字太多还是难以理解。下图为X-Z平面上,世界零点附近,更新顺序差异的可视化图:
- 图中黑线左侧,颜色越相近的色块,更新顺序越相同。
- 图中黑线右侧,彩色的色块代表该位置符合97%规律,灰色色块代表其不符合。
- 绿色标记①和③为规则生效区,可以看到明显有规律的色块排列。
- 红色框,标记②为规则失效区,可以看到色块顺序明显混乱。
- 可以看到失效区在Z轴仅有2格,但在X轴延续超出画面。
而剩下不满足这个规律的,红石粉的位置称为“失效点”。至此,是红石粉相关的,第一个数学上的规律。
规律2:
失效点有固定的,可预测的区间和踪迹。如果点 A 是失效点,那么与点 A 的
hashCode相差至少 1922 的点 B,就不可能与 A 处于同一个“失效范围”中
但事情还没结束。哪些情况(失效点)会不符合刚刚的结论呢?
结合先前的分析,我们得出以下几点:
- X方向每移动一格,hashCode 变化1;Y方向每移动一格,变化31;Z方向每移动一格,变化961。
- 低16位的边界每隔65536就会出现一次。
- 规律失效的原因在于 hashCode 的低16位在增减961时跨越了65536的边界。
因此,只要 hashCode 足够接近这个边界,就可能成为失效点。
例如,考虑hashCode在最远的两个更新核(+-Z)的变化,它们之间的差为1922。因此,如果某个红石粉的 hashCode 与低16位边界距离不到1922,那么它周围的更新核很可能跨越这个边界,从而导致我们之前提出的“7个核高16位相同”结论失效。
由此可以看出三个方向上的“失效范围”。 (下图中为失效区分布的可视化。灰色为失效区;白色线描述了坐标轴;绿色框为一个失效区的“段落”。失效区群由一个个段落排列而成。)
沿 X 轴: 每移动一格,hashCode 只变化1。 因此,一个宽度约1922的失效区域在 X 方向上持续。一旦进入这个区域,沿 X 方向连续移动上千格,都可能仍然处于失效区之中。
沿 Y 轴: 每移动一格变化31,所以同样的失效区大约只能持续:1922 ÷ 31 ≈ 62格。
沿 Z 轴: 每移动一格变化961,因此危险区域大约只能持续:1922 ÷ 961 ≈ 2 格。
由此还能得出:
如果点 A 是失效点,那么与点 A 的 hashCode 相差至少 1922 的点 B(比如在z轴相差2格以上的点),就不可能与 A 一样处于“失效范围”中。
规律3:
97%规则生效时,3个分组有
6种组合。-Y+X+Z定为G+,中心点为自身,+Y-X-Z为G-。其中,自身一组在顺序中间的概率为50%。
| 顺序 | 占比 |
|---|---|
G+ → 自身 → G- | 25% |
G- → 自身 → G+ | 25% |
自身 → G+ → G- | 12.5% |
自身 → G- → G+ | 12.5% |
G+ → G- → 自身 | 12.5% |
G- → G+ → 自身 | 12.5% |
在前文中,我们提到:
而
15 = 0000 0000 0000 1111,这意味着,桶号实际上只取最终hash的最低4位。hash的这最低4位的根基,是hashCode的最低4位。因此我们真正需要关注的,还是hashCode自己的最低4位。
而 hashCode 是由x + 31y + 961z得到的。因为31除以16的余数和-1相同,961除以16的余数和1相同,所以这个 hashCode 的最低4位,实际上只与x - y + z有关。.
我们继续将x - y + z的结果记A。而在97%的情况下, 因为次数影响hashCode的低4位, 因此此数与hashCode的高16位中的 前4位(此时它们为同一数字,看作B)按位异或的结果决定了原算式的最后4位, 进而决定了最终的 桶号 。
如果两个组的 x - y + z 仅在最低位(bit0)不同,则它们的 桶号 也一定相邻,则它们的排序也相邻。 另外落单的一组因为bit0外的其它位也不同而排到其它地方。
我们假设 u = A^B(自身)、v = (A+1)^B(G+组)、w = (A−1)^B(G-组)。(此处^为XOR)
当
A为偶数时,A与A+1只在 bit0 不同,- 因此
u与v只在 bit0 不同 - 因此
u与v得到的桶号将是相邻整数 - 因此 没有第三个值能插在它们中间
- 因此
w不可能在中间。
- 因此
当
A为奇数时,A与A−1只在 bit0 不同- 同上,因此
u与w的桶号相邻 - 因此
v不可能插在中间。
- 同上,因此
每组出现在中间的可能性可以列为如下:
A
/ \
偶数 奇数
50% 50%
/ \ / \
自身 G+ 自身 G-
50% 50% 50% 50%如图,在中间的只可能是「自身」或「与 A 同奇偶的那一组」,两者各占一半 既:
- 自身中间 50%,
G+在中间 25%(只在A偶数时)G-在中间 25%(只在A奇数时)。
三种情况各自再按排列组合,可得到25%,25%,12.5%,12.5%,12.5%,12.5%的结论。
规律4
尽管7个更新核有 7! 种排列方式,但实际上只有57种会出现。
之前,我们一直专注于“生效区”,也就是97%的规则得以应用的区域。现在让我们来考虑一下失效区内的分布情况。
如果一个位置想要处于失效区,
那么它的 hashCode 低 16 位 (简称为L,表示“低”)在加减961或31或1时,
需要超过16位能表示的范围,即高于65536,或者低于0。
这样一来,它的一些更新核的低16位会“越界”,从而改变自身 hashCode的高16位,这对导致这些更新核被分配到不同的 bucketIndex,最终使得规律不再有效。
因此,我们可以推导出每个方向的进位或借位条件。
正向方向(向上进位):
| 方向 | 计算 | 进位条件 |
|---|---|---|
+Z | L + 961 | 当 L ≥ 64575 |
+Y | L + 31 | 当 L ≥ 65505 |
+X | L + 1 | 当 L = 65535 |
负向方向(向下借位):
| 方向 | 计算 | 借位条件 |
|---|---|---|
-Z | L - 961 | 当 L ≤ 960 |
-Y | L - 31 | 当 L ≤ 30 |
-X | L - 1 | 当 L = 0 |
现在将正向的阈值从小到大排列:
64575 < 65505 < 65535
↑ ↑ ↑
+Z +Y +X负向的阈值从大到小排列:
960 > 30 > 0
↑ ↑ ↑
-Z -Y -X观察阈值的大小关系可以发现:
- 如果L要在X轴增减时超出,则此时Y和Z轴一定也会超出(如果因X坐标增减1都会导致超出,那Y的31和Z的961肯定也会超出);
- 如果L要在Y轴增减时超出,则此时Z轴一定也会超出,但X不一定超出;
- 如果L要在Z轴增减时超出,X和Y均不一定超出。
除此以外还有相当显而易见的一点:
- 当 L ≥ 64575 时,只可能向上进位(L 太大,不可能在减少时 ≤ 960)
- 当 L ≤ 960 时,只可能向下借位(L 太小,不可能在增加时 ≥ 64575)
这几点一结合,排除了相当多的组合。现在唯一剩下的,失效区 里能出现的情况如下列出:
{+Z}进位{+Z,+Y}进位{+Z,+Y,+X}进位{-Z}进位{-Z,-Y}进位{-Z,-Y,-X}进位
那现在就可以考究这6种失效情况各能制造多少组合了。
让我们回到 规律3 时的做法:
我们继续将由
x - y + z影响的,hashCode的低4位记作A,hashCode的高16位中的 前4位 记作B。
在生效区时,
自身: A ^ B
G+组:(A+1) ^ B
G-组:(A-1) ^ B但在失效区内情况不同:G+或者G-组里,某几个更新核的 B 会 +1(L≥64575,某个核发生进位)或者 -1(L<≤960,某个核发生借位)。
进位,借位表
完整的进位表
| 进位模式 | L 范围 | 进位方向 | B 的变化 | 哪些方向进位 |
|---|---|---|---|---|
{} 安全 | 961-64574 | 无 | B → B | 无 |
{+Z} | 64575-65504 | 向上 | B → B+1 | +Z |
{+Z,+Y} | 65505-65534 | 向上 | B → B+1 | +Z, +Y |
{+Z,+Y,+X} | 65535 | 向上 | B → B+1 | +Z, +Y, +X |
{-Z} | 1-960 | 向下 | B → B-1 | -Z |
{-Z,-Y} | 1-30 | 向下 | B → B-1 | -Z, -Y |
{-Z,-Y,-X} | 0 | 向下 | B → B-1 | -Z, -Y, -X |
此时,比如单{+Z}进位时,bucketIndex 分组会变成这样:
u = A ^ B
v = (A+1) ^ B
w = (A-1) ^ B
z = (A+1) ^ (B+1) //+Z在这里{+Z,+Y} 时这样:
u = A ^ B
v = (A+1) ^ B
w = (A-1) ^ B
y = (A-1) ^ (B+1) //+Y在这里
z = (A+1) ^ (B+1) //+Z在这里{+Z,+Y,+X} 时这样:
u = A ^ B
v = (A+1) ^ B
w = (A-1) ^ B
y = (A-1) ^ (B+1) //+Y在这里
xz = (A+1) ^ (B+1) //+Z,+X在这里但对于{+Z,+Y,+X}来说,有一点值得注意:如果3轴都要发生进位,那么此时A必须是1111(+X只会让A增加1,若要在+X进位,A必须是1111,即15。) 而对{+Z}和{+Z,+Y}来说,A可以是0到15的任意数字。
负方向对称,同理。
但由于 bucketIndex 可能在计算方式不同的情况下结果相同,为了最保险的结论。我们可以对它们的组合进行穷举(比如对+Z+Y进行穷举):
Set<String> uniqueOrders = new HashSet<>();
for (int A = 0; A < 16; A++) {
for (int B = 0; B < 16; B++) { // A是4位,B是4位,总共16*16个组合
// 在 {+Z,+Y} 模式下,计算 5 个桶值
int u = A ^ B;
int v = ((A+1) & 15) ^ B;
int w = ((A-1) & 15) ^ B;
int y = ((A-1) & 15) ^ ((B+1) & 15);
int z = ((A+1) & 15) ^ ((B+1) & 15);
// 7 个元素及其桶值
int[] elements = {0, 1, 2, 3, 4, 5, 6};
String[] names = {"自身", "-Y", "+Y", "-Z", "+Z", "-X", "+X"};
int[] buckets = {u, v, y, w, z, w, v};
String order = stableSortByBucket(names, buckets);
uniqueOrders.add(order);
}
}
System.out.println(uniqueOrders.size()); // 输出:14
uniqueOrders.forEach(System.out::println);但下结论前还得再等等,我们上表是分别考虑每种进位模式带来的组合,虽然排除了不同算式得到同 bucketIndex 的情况 。但它们之间仍然可能出现重复:bucketIndex 的变化不一定改变各个更新核的排序。下面列出一个例子:
取 A = 0,B = 8
{+Z}
bucket:
自身 = 8
-Y = 9
+Y = 7
-Z = 7
+Z = 8
-X = 7
+X = 9排序后+Y → -Z → -X → 自身 → +Z → -Y → +X
{+Z,+Y}
自身 = 8
-Y = 9
+Y = 6 ← B+1
-Z = 7
+Z = 8
-X = 7
+X = 9排序,+Y → -Z → -X → 自身 → +Z → -Y → +X,顺序完全一样!
{+Z} → +Y -Z -X 自身 +Z -Y +X
{+Z,+Y} → +Y -Z -X 自身 +Z -Y +X
{+Z} 7 7 7 8 8 9 9
{+Z,+Y} 6 7 7 8 8 9 9这种情况下,+Y 原本就在最前面,所以它的 bucketIndex 从 7 变成 6,并没有改变最终排序关系。这个重复是对称的,它也会出现在{-Z, -Y}和{-Z}中。
全部经过穷举后,得到以下共60种结果:
穷举代码
import java.util.*;
public class Main {
private static final String[] ELEMENTS = {"自身", "-Y", "+Y", "-Z", "+Z", "-X", "+X"};
@FunctionalInterface
interface BucketCalculator {
int[] compute(int A, int B);
}
public static void main(String[] args) {
// 1. 七种进位模式的计算器
//
// u = A ^ B 自身
// v = (A+1) ^ B -Y / +Z / +X 的基准值
// w = (A-1) ^ B +Y / -Z / -X 的基准值
// y = (A-1) ^ (B+1) +Y 进位
// z = (A+1) ^ (B+1) +Z / +X 进位
// yn = (A+1) ^ (B-1) -Y 借位
// zn = (A-1) ^ (B-1) -Z / -X 借位
//
// 数组下标: 0=自身 1=-Y 2=+Y 3=-Z 4=+Z 5=-X 6=+X
Map<String, BucketCalculator> calculators = new LinkedHashMap<>();
calculators.put("{}", (A, B) -> {
int u = A ^ B;
int v = ((A + 1) & 15) ^ B;
int w = ((A - 1) & 15) ^ B;
return new int[]{u, v, w, w, v, w, v};
});
calculators.put("{+Z}", (A, B) -> {
int u = A ^ B;
int v = ((A + 1) & 15) ^ B;
int w = ((A - 1) & 15) ^ B;
int z = ((A + 1) & 15) ^ ((B + 1) & 15);
return new int[]{u, v, w, w, z, w, v}; // idx4 = +Z
});
calculators.put("{+Z,+Y}", (A, B) -> {
int u = A ^ B;
int v = ((A + 1) & 15) ^ B;
int w = ((A - 1) & 15) ^ B;
int y = ((A - 1) & 15) ^ ((B + 1) & 15);
int z = ((A + 1) & 15) ^ ((B + 1) & 15);
return new int[]{u, v, y, w, z, w, v}; // idx2 = +Y, idx4 = +Z
});
calculators.put("{+Z,+Y,+X}", (A, B) -> {
int u = A ^ B;
int v = ((A + 1) & 15) ^ B;
int w = ((A - 1) & 15) ^ B;
int y = ((A - 1) & 15) ^ ((B + 1) & 15);
int z = ((A + 1) & 15) ^ ((B + 1) & 15);
return new int[]{u, v, y, w, z, w, z}; // idx6 = +X 也进位
});
calculators.put("{-Z}", (A, B) -> {
int u = A ^ B;
int v = ((A + 1) & 15) ^ B;
int w = ((A - 1) & 15) ^ B;
int zn = ((A - 1) & 15) ^ ((B - 1) & 15);
return new int[]{u, v, w, zn, v, w, v}; // idx3 = -Z(原先错放在 idx4)
});
calculators.put("{-Z,-Y}", (A, B) -> {
int u = A ^ B;
int v = ((A + 1) & 15) ^ B;
int w = ((A - 1) & 15) ^ B;
int yn = ((A + 1) & 15) ^ ((B - 1) & 15);
int zn = ((A - 1) & 15) ^ ((B - 1) & 15);
return new int[]{u, yn, w, zn, v, w, v}; // idx1 = -Y, idx3 = -Z
});
calculators.put("{-Z,-Y,-X}", (A, B) -> {
int u = A ^ B;
int v = ((A + 1) & 15) ^ B;
int w = ((A - 1) & 15) ^ B;
int yn = ((A + 1) & 15) ^ ((B - 1) & 15);
int zn = ((A - 1) & 15) ^ ((B - 1) & 15);
return new int[]{u, yn, w, zn, v, zn, v}; // idx5 = -X 也借位
});
// 每种模式允许的 A;-1 表示 0~15
Map<String, Integer> fixedA = new LinkedHashMap<>();
fixedA.put("{}", -1);
fixedA.put("{+Z}", -1);
fixedA.put("{+Z,+Y}", -1);
fixedA.put("{+Z,+Y,+X}", 15); // L = 65535
fixedA.put("{-Z}", -1);
fixedA.put("{-Z,-Y}", -1);
fixedA.put("{-Z,-Y,-X}", 0); // L = 0
// 结果收集
Map<String, Set<String>> modeOrders = new LinkedHashMap<>();
Map<String, Map<String, List<int[]>>> orderToABMap = new LinkedHashMap<>();
System.out.println("=== 穷举 ===\n");
int stateCount = 0;
for (Map.Entry<String, BucketCalculator> entry : calculators.entrySet()) {
String mode = entry.getKey();
BucketCalculator calc = entry.getValue();
int only = fixedA.get(mode);
Set<String> orders = new LinkedHashSet<>();
Map<String, List<int[]>> abForOrder = new LinkedHashMap<>();
for (int A = 0; A < 16; A++) {
if (only >= 0 && A != only) continue;
for (int B = 0; B < 16; B++) {
int[] buckets = calc.compute(A, B);
String order = stableSort(buckets);
orders.add(order);
abForOrder.computeIfAbsent(order, k -> new ArrayList<>()).add(new int[]{A, B});
stateCount++;
}
}
modeOrders.put(mode, orders);
orderToABMap.put(mode, abForOrder);
System.out.println(mode + " 模式: (A = " + (only < 0 ? "0~15" : String.valueOf(only)) + ")");
System.out.println(" 排列数量: " + orders.size());
System.out.println(" 排列列表:");
int count = 1;
for (String order : orders) {
System.out.printf(" %2d. %s%n", count++, order);
}
System.out.println();
}
// 并集
Set<String> union = new LinkedHashSet<>();
for (Set<String> set : modeOrders.values()) {
union.addAll(set);
}
System.out.println("=== 结果 ===");
int total = 0;
for (Map.Entry<String, Set<String>> entry : modeOrders.entrySet()) {
int size = entry.getValue().size();
total += size;
System.out.printf(" %-12s %d%n", entry.getKey() + ":", size);
}
System.out.println(" 合计: " + total);
System.out.println(" 并集大小: " + union.size());
System.out.println(" 重复计数 (合计 - 并集): " + (total - union.size()));
System.out.println(" 枚举到的 (A,B,模式) 状态数: " + stateCount);
System.out.println();
Map<String, Set<String>> orderToModes = new LinkedHashMap<>();
for (Map.Entry<String, Set<String>> entry : modeOrders.entrySet()) {
for (String order : entry.getValue()) {
orderToModes.computeIfAbsent(order, k -> new LinkedHashSet<>()).add(entry.getKey());
}
}
Map<String, Set<String>> duplicateOrders = new LinkedHashMap<>();
for (Map.Entry<String, Set<String>> entry : orderToModes.entrySet()) {
if (entry.getValue().size() >= 2) {
duplicateOrders.put(entry.getKey(), entry.getValue());
}
}
}
private static Set<String> bruteForce() {
int[][] offsets = {{0, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0, 0, -1}, {0, 0, 1}, {-1, 0, 0}, {1, 0, 0}};
Set<String> all = new LinkedHashSet<>();
int[] buckets = new int[7];
for (int hi = 0; hi < 16; hi++) {
for (int low16 = 0; low16 < 65536; low16++) {
int h = (hi << 16) | low16;
for (int i = 0; i < 7; i++) {
int hh = h + offsets[i][0] + 31 * offsets[i][1] + 961 * offsets[i][2];
buckets[i] = 15 & (hh ^ (hh >>> 16));
}
all.add(stableSort(buckets));
}
}
return all;
}
/** 稳定排序:按桶值升序,桶值相同则保持原始索引顺序 */
private static String stableSort(int[] buckets) {
Integer[] indices = new Integer[ELEMENTS.length];
for (int i = 0; i < indices.length; i++) {
indices[i] = i;
}
Arrays.sort(indices, (i1, i2) -> {
int cmp = Integer.compare(buckets[i1], buckets[i2]);
return cmp != 0 ? cmp : Integer.compare(i1, i2);
});
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indices.length; i++) {
if (i > 0) sb.append(", ");
sb.append(ELEMENTS[indices[i]]);
}
return sb.toString();
}
}| # | 更新顺序 | 3 组分组 | 占比 |
|---|---|---|---|
| 1 | +Y → -Z → -X → 自身 → -Y → +Z → +X | 第 5 种 | 24.2668% |
| 2 | -Y → +Z → +X → 自身 → +Y → -Z → -X | 第 3 种 | 24.2668% |
| 3 | +Y → -Z → -X → -Y → +Z → +X → 自身 | 第 6 种 | 12.1334% |
| 4 | -Y → +Z → +X → +Y → -Z → -X → 自身 | 第 4 种 | 12.1334% |
| 5 | 自身 → +Y → -Z → -X → -Y → +Z → +X | 第 2 种 | 12.1334% |
| 6 | 自身 → -Y → +Z → +X → +Y → -Z → -X | 第 1 种 | 12.1334% |
| # | 更新顺序 | 进位模式 | 占比 |
|---|---|---|---|
| 7 | +Y → -Z → -X → 自身 → +Z → -Y → +X | {+Z,+Y}, | 0.1831% |
| 8 | -Y → +Z → +X → 自身 → -Z → +Y → -X | {-Z,-Y}, | 0.1831% |
| 9 | 自身 → +Z → -Y → +X → +Y → -Z → -X | {+Z,+Y}, | 0.1831% |
| 10 | 自身 → -Z → +Y → -X → -Y → +Z → +X | {-Z,-Y}, | 0.1831% |
| 11 | +Y → -X → -Z → -Y → +Z → +X → 自身 | 0.1774% | |
| 12 | +Y → -Z → -X → 自身 → -Y → +X → +Z | 0.1774% | |
| 13 | -Y → +X → +Z → +Y → -Z → -X → 自身 | 0.1774% | |
| 14 | -Y → +Z → +X → 自身 → +Y → -X → -Z | 0.1774% | |
| 15 | +Y → -X → 自身 → -Y → +Z → +X → -Z | {-Z,-Y}, | 0.1221% |
| 16 | -Y → +X → 自身 → +Y → -Z → -X → +Z | {+Z,+Y}, | 0.1221% |
| 17 | +Y → -Z → -X → +Z → -Y → +X → 自身 | 0.1218% | |
| 18 | -Y → +Z → +X → -Z → +Y → -X → 自身 | 0.1218% | |
| 19 | 自身 → +Z → +Y → -Z → -X → -Y → +X | 0.1218% | |
| 20 | 自身 → -Z → -Y → +Z → +X → +Y → -X | 0.1218% | |
| 21 | +Z → -Y → +X → 自身 → +Y → -Z → -X | 0.1106% | |
| 22 | -Z → +Y → -X → 自身 → -Y → +Z → +X | 0.1106% | |
| 23 | +Y → -X → 自身 → -Z → -Y → +Z → +X | {-Z,-Y}, | 0.0684% |
| 24 | -Y → +X → 自身 → +Z → +Y → -Z → -X | {+Z,+Y}, | 0.0684% |
| 25 | +Y → -Z → -X → -Y → +X → 自身 → +Z | {+Z,+Y}, | 0.0572% |
| 26 | -Y → +Z → +X → +Y → -X → 自身 → -Z | {-Z,-Y}, | 0.0572% |
| 27 | +Y → -X → -Z → 自身 → -Y → +Z → +X | 0.0556% | |
| 28 | -Y → +X → +Z → 自身 → +Y → -Z → -X | 0.0556% | |
| 29 | 自身 → +Y → -Z → -X → -Y → +X → +Z | 0.0556% | |
| 30 | 自身 → -Y → +Z → +X → +Y → -X → -Z | 0.0556% | |
| 31 | +Y → -X → -Z → +Z → +X → 自身 → -Y | 0.0057% | |
| 32 | +Z → +X → 自身 → -Y → +Y → -X → -Z | 0.0057% | |
| 33 | -Y → +X → +Z → -Z → -X → 自身 → +Y | 0.0057% | |
| 34 | -Z → -X → 自身 → +Y → -Y → +X → +Z | 0.0057% | |
| 35 | +Z → +X → -Z → +Y → -X → 自身 → -Y | 0.0041% | |
| 36 | -Z → -X → +Z → -Y → +X → 自身 → +Y | 0.0041% | |
| 37 | 自身 → +Z → -Z → -X → +Y → -Y → +X | 0.0041% | |
| 38 | 自身 → -Z → +Z → +X → -Y → +Y → -X | 0.0041% | |
| 39 | +Y → +Z → -Y → +X → 自身 → -Z → -X | 0.0038% | |
| 40 | +Y → -X → 自身 → +Z → +X → -Y → -Z | 0.0038% | |
| 41 | -Y → +X → 自身 → -Z → -X → +Y → +Z | 0.0038% | |
| 42 | -Y → -Z → +Y → -X → 自身 → +Z → +X | 0.0038% | |
| 43 | +Y → -X → -Z → -Y → 自身 → +Z → +X | 0.0016% | |
| 44 | +Y → 自身 → -Z → -X → -Y → +X → +Z | 0.0016% | |
| 45 | -Y → +X → +Z → +Y → 自身 → -Z → -X | 0.0016% | |
| 46 | -Y → 自身 → +Z → +X → +Y → -X → -Z | 0.0016% | |
| 47 | +Y → -Z → -X → +Z → +X → 自身 → -Y | 0.0004% | |
| 48 | +Z → +X → 自身 → -Y → +Y → -Z → -X | 0.0004% | |
| 49 | -Y → +Z → +X → -Z → -X → 自身 → +Y | 0.0004% | |
| 50 | -Z → -X → 自身 → +Y → -Y → +Z → +X | 0.0004% | |
| 51 | +Y → -Y → +X → 自身 → +Z → -Z → -X | 0.0003% | |
| 52 | +Y → -Z → -X → -Y → 自身 → +Z → +X | 0.0003% | |
| 53 | +Y → 自身 → -Z → -X → -Y → +Z → +X | 0.0003% | |
| 54 | -Y → +Y → -X → 自身 → -Z → +Z → +X | 0.0003% | |
| 55 | -Y → +Z → +X → +Y → 自身 → -Z → -X | 0.0003% | |
| 56 | -Y → 自身 → +Z → +X → +Y → -Z → -X | 0.0003% | |
| 57 | +Y → -Y → 自身 → +Z → +X → -Z → -X | 0.0001% | |
| 58 | -Y → +Y → 自身 → -Z → -X → +Z → +X | 0.0001% | |
| 59 | 自身 → +Z → +X → -Z → -X → +Y → -Y | 0.0001% | |
| 60 | 自身 → -Z → -X → +Z → +X → -Y → +Y | 0.0001% |
总结
红石粉的更新看似复杂,但其实具有较强的规律性。本篇中,我们通过代码与数学计算深度抛析,且可视化了粉的更新规律,得到以下几个可以利用的结论:
- 红石粉更新顺序由Java的HashSet决定:7个更新核按固定顺序(O→-Y→+Y→-Z→+Z→-X→+X)加入,遍历时先按桶号排序,同桶内按加入顺序输出。桶号由hashCode = x + 31y + 961z经扰动后取最低4位得到,因31≡-1(mod 16)、961≡1(mod 16),桶号只取决于x - y + z的最低4位。
- 7个核最大哈希差仅1922,只要不跨过0或65535边界,它们的高16位完全相同,此时分成三组:{O}单独,{-Y,+Z,+X}同桶,{+Y,-Z,-X}同桶,跨边界概率≈1922/65536≈3%,故97%坐标生效。
- 失效点在X轴连续约1922格,Y轴约62格,Z轴仅约2格,沿Z移2格、Y移62格、X移1922格后必然脱离失效区。
- 设A=x-y+z,A偶数时Self与G+桶号相邻,A奇数时Self与G-桶号相邻,故Self在中间概率50%,G+在中间25%(A偶),G-在中间25%(A奇),完整6种排列概率分别为25%、25%、12.5%、12.5%、12.5%、12.5%。
- 失效区只可能产生6种进位/借位模式,穷举去重后,所有可能出现的更新顺序仅为60种(远少于理论的7!=5040)。
