递归时的全局变量

Question

我有一个全局变量masterList，它是一个HashMap。

private static HashMap<ArrayList<String>, Integer> masterList = 
     new HashMap<ArrayList<String>, Integer>();

我有一个递归函数 generateAnagram，它将 Anagrams 的 ArrayLists 放入此 HashMap 中，并将列表中的单词数作为值。然而，HashMap 在第一次调用后开始混乱，之前的 ArrayLists 被我试图添加的新 ArrayLists 覆盖，但之前的值仍然存在。这会导致两个键具有相同的值。这是结果的屏幕截图 - 单击 [此处] http://tinypic.com/r/ka1gli/8

    private static void generateAnagram(Set<String> subsets, ArrayList<String> currList, letterMap wordMap) {
            if (wordMap.count() == 0) {
                System.out.println("Adding: " + currList);
                masterList.put(currList, currList.size());
                System.out.println("Current Master: " + masterList.toString());
            } else {
                for (String word : subsets) {
                    if (word.length() <= wordMap.count() && wordMap.isConstructionPossible(word)) {
                        //System.out.println("Word: " + word + "    "  + wordMap.isConstructionPossible(word));
                        wordMap.remove(word);
                        currList.add(word);
                        generateAnagram(subsets, currList, wordMap);
                        currList.remove(word);
                        wordMap.addBack(word);
                    }
                }
            }
}

Answer 1

使用 ArrayList 作为 HashMap 的键不是一个好主意。每次更改 ArrayList 的内容（通过添加或删除元素）时，它的 hashCode 都会更改，因此即使它已经在 HashMap、get() 和 containsKey()不会找到，put()会重新添加。

您只有 ArrayList 的一个实例，您将其保留在 masterList 地图中 put，因此如果您不这样做，您的地图中将只有一个条目'不要一直更改该列表的内容。

Answer 2

这个需要从参数的角度来看。 ArrayList 引用每次都作为参数传递给您的递归调用，但它仍然指向相同的 ArrayList。当您将它放入哈希图中时，您将存储对同一个原始 ArrayList.

的多个引用

因此在将其添加到主列表之前使用 ArrayList.clone()。更好的是，存储一个不可变的集合以确保您的哈希不会在 HashMap 中混乱：

HashMap<List<String>, Integer> masterList = 
      new HashMap<List<String>, Integer>();
...

ArrayList<String> tmp = (ArrayList<String>)currList.clone();
List<String> imm = Collections.unmodifiableList(tmp);
masterList.put(imm, imm.size());

Answer 3

"previous ArrayLists are overriden with the new one I'm trying to add, but the previous value remains."

如果您不想要以前的值，您可能需要这样做

场景之前：

        final ArrayList<Integer> arrayList = new ArrayList<Integer>();
        final HashMap<ArrayList<Integer>, Integer> hashmap = new HashMap<ArrayList<Integer>, Integer>();

        arrayList.add(1);
        hashmap.put(arrayList, 1);

        arrayList.add(2);
        hashmap.put(arrayList, 1);
        System.out.println(hashmap);

输出：{[1, 2]=1, [1, 2]=1}

场景之后：

ArrayList<Integer> arrayList = new ArrayList<Integer>();
final HashMap<ArrayList<Integer>, Integer> hashmap = new HashMap<ArrayList<Integer>, Integer>();

arrayList.add(1);
hashmap.put(arrayList, 1);

arrayList = new ArrayList<Integer>();
arrayList.add(2);
hashmap.put(arrayList, 1);

System.out.println(hashmap);

输出：{[1]=1，[2]=1}

递归时的全局变量

Global variable during recursion

java

recursion

hashmap

anagram