metodos - map string string java

Java: cómo obtener un conjunto de claves con el mismo valor en hashmap

Question

Tengo un hashmap como a continuación:

1-> x

2-> y

3-> x

4-> z

Ahora quiero saber todas las claves cuyo valor es x (ans: [1,3]). ¿Cuál es la mejor manera de hacerlo?

La fuerza bruta es simplemente iterar sobre el mapa y almacenar todas las claves en una matriz cuyo valor es x.

¿Hay alguna manera eficiente para esto?

Gracias

Answer 1

Sí, solo fuerza bruta. Puede hacerlo rápido almacenando también un Multimap de Value -> Collection of Key, a expensas de la memoria y el costo del tiempo de ejecución para las actualizaciones.

Answer 2

Si está abierto a usar una biblioteca, use las utilidades Multimaps de Google Guava , específicamente forMap() combinado con invertFrom()

Answer 3

Si está utilizando un hashmap, no hay una manera eficiente de hacerlo, sino de iterar los valores

Answer 4

Si ya tiene un mapa, debería considerar usar la biblioteca de guayaba de Google para filtrar las entradas que le interesan. Puede hacer algo como:

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

Answer 5

Un hashmap es una estructura que está optimizada para el acceso asociativo de los valores que utilizan las teclas, pero de ninguna manera es mejor al hacer lo contrario que una matriz, por ejemplo. No creo que puedas hacer nada mejor que repetirlo. La única forma de mejorar la eficiencia es si también tiene un mapa hash inverso (es decir, hash map donde mantiene una matriz de teclas apuntando a un valor dado para todos los valores).

Answer 6

HashMap calcula el hashcode() de la clave, no de los valores. A menos que almacene algún tipo de información adicional, o considere el uso de una estructura de datos diferente, creo que la única forma en que puede obtener esto es con la fuerza bruta.

Si necesita realizar un funcionamiento eficiente de los valores, debe pensar si está utilizando la estructura de datos adecuada.

Answer 7

Puede usar un MultiMap para obtener fácilmente todos esos valores duplicados.

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());
}

Imprime:

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]

La sugerencia de Per @ noahz , forMap e invertFrom toma menos líneas, pero es posiblemente más compleja de leer:

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

en lugar de:

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

Answer 8

Si Java 8 es una opción, puede intentar un enfoque de transmisión:

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);

Lo que resulta en:

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

Si se prefiere 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);
}

Como un lado interesante, experimenté con el tiempo requerido para cada algoritmo al ejecutar grandes mapas de pares (índice, aleatorio (''a'' - ''z'')).

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

Answer 9

Prueba esto.....

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());

    }

Answer 10

Estoy de acuerdo con George Campbell, pero para Java 8 lo haría un poco más fácil:

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