Java Map.containsValue 在列表中的第 15000 项之后不起作用

Question

我有两个 HashMap，每个列表中有 30000 个不同顺序的相同单词。虽然我可以将来自第二个列表的搜索值与第一个列表进行比较，但是在第 15000 个项目之后比较不起作用。我知道哈希图中没有保证，但我不需要顺序，我只是通过列表映射检查搜索图中的单词并删除已创建的单词。如果列表包含搜索中的所有单词，则要 return true。有没有漏掉的地方？

//Sample values (30000 same words with different order):
//list: hooef dalwm vuitg enewb xcbfy ...
//search: dalwm xcbfy hooef enewb dalwm ...

Map<Integer, String> list = new HashMap<Integer, String>();
Map<Integer, String> search = new HashMap<Integer, String>();
boolean check = true;

for(int i=0; i<search.size(); i++) {
    if(list.containsValue(search.get(i)))
        list.remove(i);
    else
        check = false; //when i=15000 the code hits to here
}
return check; //returns false

Answer 1

如果映射的键是顺序，那么 list.remove(i); 会从 list 中删除一个随机值，这似乎不正确。

这是一个可能的解决方案：

Collection<String> values = list.values(); 

for(int i=0; i<search.size(); i++) {
    if(!values.remove(search.get(i))) {
        check = false;
    }
}

Answer 2

containsValue 似乎不起作用的原因是您已经无意中删除了它正在寻找的值。

Assume Search -> 1:A, 2:B, 3:C
         List -> 3:B, 1:C, 2:A

List 检查键 1 是否包含 Search's 值。确实如此。它位于 List 中的 key 2。但是您在 List 处删除了键 1，认为它是值 A。但它的价值C。现在，当 List 检查值 C 时，它将失败。

据我所知，您需要解决三个问题。

您正在尝试关联两个本质上具有不同键值映射的映射（尽管它们具有相同的键和值集）。
您想根据值而不是键搜索和删除。
并且您可以有重复的值。

这是我的方法。第一部分是构建用于测试的数据结构。

Stream<String> stream = null;
try {
    stream = Files.lines(Path.of("f:/linux.words"));
} catch (Exception e) {
    e.printStackTrace();
}

// limit to 100_000 word
int count = 100_000;

现在确保单词的顺序不同。

String[] words1 = stream.limit(count).toArray(String[]::new);
String[] words2 = words1.clone();
Collections.shuffle(Arrays.asList(words2)); // shuffle the array.

现在构建两个不同的地图search和list

Map<Integer, String> list = new HashMap<>();
Map<Integer, String> search = new HashMap<>();
for (int i = 0; i < words1.length; i++) {
    list.put(i + 1, words1[i]);
    search.put(i + 1, words2[i]);
}

现在创建一个 valueToKeyMap 将所有值映射到它们各自的键。由于值可以重复，因此键包含在 List

中

Map<String, List<Integer>> valueToKeyMap = list.entrySet().stream()
        .collect(Collectors.groupingBy(Entry::getValue,
                Collectors.mapping(Entry::getKey,
                        Collectors.toList())));

现在遍历地图删除重复项。 valueToKeyMap 中的列表将需要迭代但预期（可能不正确）任何给定字符串的重复次数将很小（例如，单词 cow 可能只出现 10 次）。

这似乎工作得相当快。包括文件读取等在内的整个工作大约需要 1 秒。该速度的部分原因是没有重复项，因此 keys 的每个 List<Integer> 的长度为 1。

count = 0;
int size = list.size();
for (int i = 1; i <= size; i++) {
    String value = search.get(i);
    if (valueToKeyMap.containsKey(value)) {
        // no need to verify if list contains value, valueToKeyMap was
        // created from it.
        for (int vkm : valueToKeyMap.get(value)) {
            list.remove(vkm);
            count++;
        }
    }
}
System.out.println(list);
System.out.println(list.size());
System.out.println(count);

Java Map.containsValue 在列表中的第 15000 项之后不起作用

Java Map.containsValue doesn't work after 15000th item in the list

java

hashmap