Java:当包含在哈希映射中时，对同一对象的多个引用将无法更新，这是有原因的吗

Question

这是为了回答leetcode上的日常挑战。问题的链接在这里。你可以运行代码来查看会发生什么

我在O(n(解决方案中的尝试包括将所有数字添加到以游程长度为值的哈希图中，新条目将从其预先存在的邻居那里获得对象引用。如果一个条目位于两个不同的连续运行之间，它只需将其中一个的值引用替换为另一个。然而，合并并没有按预期进行。我发现了下面的不当行为。

val1表示大于的游程，val2表示小于的游程。我不得不在两层数组中包含Integer对象，以使引用按预期工作(Integer对象似乎是按值分配的，而不是按对象引用分配的(。代码现在可以一直工作到测试用例66。以另一种方式进行分配在测试用例40多岁时失败。在问题行1中递增的引用在其连续运行的所有数字中保持同步，正如预期的那样，但在第2行中重新分配的引用似乎只更新了与当前数字相邻的一个条目，在其运行的另一端，Integer引用由于某种原因仍指向旧值，尽管它们都应该指向同一个嵌套数组。

这就是我想象问题示例中hashmap中发生的事情的方式。(他们应该都指向合并后的9。(

在
之前。[[4]]。[[4]]
..___ |____|_
/……\……/………\
-6-5-4-3-2-1 0 1 2
…………|……||
…………|……|。val 1
。val2。新密钥

之后
。[[9]。[[4]]
..________ |________|
/…………..\\
-6-5-4-3-2-1 0 1 2
…………|……||
…………|……|。val 1
。val2。新密钥

为什么对同一对象的多个引用应该在哈希映射中去同步？

class Solution {
public int longestConsecutive(int[] nums) {
HashMap<Integer, Integer[][]> map = new HashMap<>();
for (int num : nums) {
if (!map.containsKey(num)) {
Integer[][] val1 = map.get(num+1);
Integer[][] val2 = map.get(num-1);
if (val1 == null && val2 == null) {
map.put(num, new Integer[][] {new Integer[] {1}});
System.out.println(num + " " + map.get(num)[0]);
} else if (val1 != null && val2 != null) { //problem clause
System.out.print(num + " val1: " + val1[0] + " val2: " + val2[0]);
val2[0][0] += val1[0][0] + 1; // line 1
val1[0] = val2[0]; // line 2
map.put(num, val2);
System.out.println("  new val1: " + val1[0] + "  new val2: " + val2[0]);
} else if (val1 != null) {
System.out.print(num + " val1: " + val1[0]);
val1[0][0] += 1;
map.put(num, val1);
System.out.println("  new val1: " + val1[0]);
} else if (val2 != null) {
System.out.print(num + " val2: " + val2[0]);
val2[0][0] += 1;
map.put(num, val2);
System.out.println("  new val2: " + val2[0]);
}
}
}
Iterator<Integer[][]> it = map.values().iterator();
int max = 0;
while (it.hasNext()) {
int temp = it.next()[0][0];
max = Math.max(max, temp);
}
return max;
}
}

Answer 1

看起来您正在尝试实现Union查找结构，但这样实现它是行不通的。

问题是，如果您有一组{a, b, c, d}。然后可以将a和b合并，然后将c和d合并为一个赋值。但是，当您尝试将{a,b}和{c,d}的组合值合并时，使用一个赋值并不能更改所有原始元素的值。这将需要总共3个赋值来更改4个值的值。

添加额外的数组不会改变任何事情，因为您仍然需要更改每个元素所引用的数组，哪个数组有相同的问题。就好像你在做：

int a = 1, b = 2, c = 3, d = 4;
a = b;
c = d;
b = c;
System.out.println(a+","+b+","+c+","+d); // [2,4,4,4]