java - Java：ハッシュマップで同じ値を持つキーのセットを取得する方法

Question

私は以下のようなハッシュマップを持っています：

1-> x

2-> y

3-> x

4-> z

ここで、値がx（ans：[1,3]）であるすべてのキーを知りたいです。最善の方法は何ですか？

強引な方法は、マップを繰り返し処理し、値がxである配列にすべてのキーを格納することです。

これを効率的に行う方法はありますか？

ありがとう

Answer 1

ハッシュマップは、キーを使用して値に関連付けてアクセスするために最適化された構造ですが、たとえば配列よりも逆の操作を行うのに優れているわけではありません。私はあなたがただ繰り返すよりも良いことはできないと思います。効率を向上させる唯一の方法は、逆ハッシュマップ（つまり、すべての値に対して特定の値を指すキーの配列を保持するハッシュマップ）もある場合です。

Answer 2

を使用して、MultiMapこれらの重複する値をすべて簡単に取得できます。

Map<Integer, String> map = new HashMap<Integer, String>();
map.put(1, "x");
map.put(2, "y");
map.put(2, "z");
map.put(3, "x");
map.put(4, "y");
map.put(5, "z");
map.put(6, "x");
map.put(7, "y");

System.out.println("Original map: " + map);

Multimap<String, Integer> multiMap = HashMultimap.create();
for (Entry<Integer, String> entry : map.entrySet()) {
  multiMap.put(entry.getValue(), entry.getKey());
}
System.out.println();

for (Entry<String, Collection<Integer>> entry : multiMap.asMap().entrySet()) {
  System.out.println("Original value: " + entry.getKey() + " was mapped to keys: "
      + entry.getValue());
}

プリントアウト：

Original map: {1=x, 2=z, 3=x, 4=y, 5=z, 6=x, 7=y}

Original value: z was mapped to keys: [2, 5]
Original value: y was mapped to keys: [4, 7]
Original value: x was mapped to keys: [1, 3, 6]

@ noahzの提案によるforMapと、invertFrom必要な行数は少なくなりますが、おそらく読むのがより複雑になります。

HashMultimap<String, Integer> multiMap =
    Multimaps.invertFrom(Multimaps.forMap(map), 
        HashMultimap.<String, Integer> create());

代わりに：

Multimap<String, Integer> multiMap = HashMultimap.create();
for (Entry<Integer, String> entry : map.entrySet()) {
  multiMap.put(entry.getValue(), entry.getKey());
}

Answer 3

Java 8がオプションの場合は、ストリーミングアプローチを試すことができます。

Map<Integer, String> map = new HashMap<>();
map.put(1, "x");
map.put(2, "y");
map.put(3, "x");
map.put(4, "z");

Map<String, ArrayList<Integer>> reverseMap = new HashMap<>(
    map.entrySet().stream()
        .collect(Collectors.groupingBy(Map.Entry::getValue)).values().stream()
        .collect(Collectors.toMap(
                item -> item.get(0).getValue(),
                item -> new ArrayList<>(
                    item.stream()
                        .map(Map.Entry::getKey)
                        .collect(Collectors.toList())
                ))
        ));

System.out.println(reverseMap);

その結果：

{x=[1, 3], y=[2], z=[4]}

Java 7が推奨される場合：

Map<String, ArrayList<Integer>> reverseMap = new HashMap<>();

for (Map.Entry<Integer,String> entry : map.entrySet()) {
    if (!reverseMap.containsKey(entry.getValue())) {
        reverseMap.put(entry.getValue(), new ArrayList<>());
    }
    ArrayList<Integer> keys = reverseMap.get(entry.getValue());
    keys.add(entry.getKey());
    reverseMap.put(entry.getValue(), keys);
}

興味深いことに、（index、random（'a'-'z'）ペアの大きなマップを実行するときに各アルゴリズムに必要な時間を実験しました。

              10,000,000        20,000,000
Java 7:         615 ms            11624 ms         
Java 8:        1579 ms             2176 ms

Answer 4

ライブラリを使用することに慣れている場合は、GoogleGuavaのマルチマップユーティリティforMap()を使用してください。invertFrom()

Answer 5

うん、ブルートフォースだけ。更新のメモリと実行時のコストを犠牲にして、[値]-> [キーのコレクション]からマルチマップを保存することで、高速化できます。

Answer 6

HashMaphashcode()値ではなく、キーのを計算します。ある種の追加情報を保存するか、別のデータ構造の使用を検討しない限り、これを取得できる唯一の方法はブルートフォースだと思います。

値に対して効率的な操作を実行する必要がある場合は、適切なデータ構造を使用しているかどうかを検討する必要があります。

Answer 7

ハッシュマップを使用している場合、それを実行する効率的な方法はありませんが、値を反復処理します

Answer 8

すでに地図をお持ちの場合は、GoogleのGuavaライブラリを使用して、関心のあるエントリをフィルタリングすることを検討してください。次のように実行できます。

final Map<Integer, Character> filtered = Maps.filterValues(unfiltered, new Predicate<Character>() {
    @Override
    public boolean apply(Character ch) {
        return ch == 'x';
    }
});

Answer 9

私はGeorgeCampbellに同意しますが、Java8の場合は少し簡単になります。

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

Answer 10

これを試して.....

public static void main(String[] args) {
        HashMap<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("cust_tenure", "3_sigma");
        hashMap.put("cust_age", "3_sigma");
        hashMap.put("cust_amb_6m_sav", "3_sigma");
        hashMap.put("cust_amb_6m_chq", "3_sigma");
        hashMap.put("cust_total_prod_6m", "3_sigma");

        HashMap<String, ArrayList<String>> result = new LinkedHashMap<String, ArrayList<String>>();

        for (String key : hashMap.keySet()) {
            ArrayList<String> colName = null;
            if (!result.containsKey(hashMap.get(key))) {
                colName = new ArrayList<String>();
                colName.add(key);
                result.put(hashMap.get(key), colName);
            } else {
                colName = result.get(hashMap.get(key));
                colName.add(key);
                result.put(hashMap.get(key), colName);
            }

            System.out.println(key + "\t" + hashMap.get(key));
        }

        for (String key : result.keySet()) {
            System.out.println(key + "\t" + result.get(key));
        }

        System.out.println(hashMap.size());

    }