Ottieni le chiavi con i valori più alti da una hashmap?

Question

Ho un HashMap definito come questo ...

HashMap<String,Integer> uniqueNames = new HashMap<String,Integer>(); 

Memorizza un nome, e il verificarsi di tale nome. Ad esempio ...

uniqueNames.put("lastname",42); 

Come posso ottenere il nome con l'occorrenza più alta?

Per ulteriori informazioni, sto lavorando con un albero di ricerca binario di "persone", memorizzando i nomi e le frequenze univoci in un HashMap. Quello che voglio fare è stampare i cognomi più comuni e qualcuno mi ha detto di usare HashMap perché volevo memorizzare un String insieme a un Integer. Forse dovrei usare una classe per memorizzare il nome e la frequenza, invece? Qualcuno potrebbe offrire qualche suggerimento.

Answer 1

Se si deve usare un HashMap, quindi il modo più semplice è probabably solo per scorrere la mappa alla ricerca della massima

Entry<String,Integer> maxEntry = null; 

for(Entry<String,Integer> entry : uniqueNames.entrySet()) { 
    if (maxEntry == null || entry.getValue() > maxEntry.getValue()) { 
     maxEntry = entry; 
    } 
} 
// maxEntry should now contain the maximum, 

Answer 2

più evidente, ora consentendo multipla con il più grande valore di occorrenza:

Integer largestVal = null; 
List<Entry<String, Integer>> largestList = new ArrayList<Entry<String, Integer>>(); 
for (Entry<String, Integer> i : uniqueNames.entrySet()){ 
    if (largestVal == null || largestVal < i.getValue()){ 
     largestVal = i.getValue(); 
     largestList .clear(); 
     largestList .add(i); 
    }else if (largestVal == i.getValue()){ 
     largestList .add(i); 
    } 
} 

Un'altra opzione sarebbe utilizzare BiMap di Guava.

BiMap<String, Integer> uniqueNames = ...; 
List<Integer> values = Lists.newArrayList(uniqueNames.values()); 
Collections.sort(values); 
String name = uniqueNames.inverse().get(values.get(0)); 

Answer 3

Ci sono due modi di andare su questo in realtà.

Se lo farai frequentemente, suggerirei di memorizzare la mappatura al contrario, dove la chiave è il numero di volte che un nome è apparso, e il valore è un elenco di nomi che è apparso molte volte . Vorrei anche usare una HashMap per eseguire le ricerche anche nell'altra direzione.

TreeMap <Integer, ArrayList <String>> sortedOccurrenceMap = 
       new TreeMap <Integer, ArrayList <String>>(); 
HashMap <String, Integer> lastNames = new HashMap <String, Integer>(); 
boolean insertIntoMap(String key) { 
    if (lastNames.containsKey(key)) { 
     int count = lastNames.get(key); 
     lastNames.put(key, count + 1); 

     //definitely in the other map 
     ArrayList <String> names = sortedOccurrenceMap.get(count); 
     names.remove(key); 
     if(!sortedOccurrenceMap.contains(count+1)) 
      sortedOccurrenceMap.put(count+1, new ArrayList<String>()); 
     sortedOccurrenceMap.get(count+1).add(key); 
    } 
    else { 
     lastNames.put(key, 1); 
     if(!sortedOccurrenceMap.contains(1)) 
      sortedOccurrenceMap.put(1, new ArrayList<String>()); 
     sortedOccurrenceMap.get(1).add(key); 
    } 
} 

Qualcosa di simile per l'eliminazione ...

E, infine, per la ricerca:

ArrayList <String> maxOccurrences() { 
    return sortedOccurrenceMap.pollLastEntry().getValue(); 
} 

restituisce l'elenco dei nomi che hanno le occorrenze max.

Se lo si fa in questo modo, la ricerca può essere eseguita in O (log n) ma i requisiti di spazio aumentano (solo con un fattore costante).

Se lo spazio è un problema, o le prestazioni non sono un problema, è sufficiente scorrere l'univocoNames.keySet e tenere traccia del valore massimo.

Answer 4

Sembra che tu voglia qualcosa di simile a uno SortedMap ma uno ordinato sul valore, non sulla chiave. Non penso che una cosa del genere esista nell'API standard.

Potrebbe essere preferibile creare una classe di frequenza e memorizzare istanze in un SortedSet.

import java.util.Set; 
import java.util.TreeSet; 

public class Frequency implements Comparable<Frequency> { 

    private String name; 
    private int freq; 

    public Frequency(String name, int freq) { 
    this.name = name; 
    this.freq = freq; 
    } 

    public static void main(String[] args) { 
    Set<Frequency> set = new TreeSet<Frequency>(); 

    set.add(new Frequency("fred", 1)); 
    set.add(new Frequency("bob", 5)); 
    set.add(new Frequency("jim", 10)); 
    set.add(new Frequency("bert", 4)); 
    set.add(new Frequency("art", 3)); 
    set.add(new Frequency("homer", 5)); 

    for (Frequency f : set) { 
     System.out.println(f); 
    } 
    } 

    @Override 
    public boolean equals(Object o) { 
    if (o == null) return false; 
    if (o.getClass().isAssignableFrom(Frequency.class)) { 
     Frequency other = (Frequency)o; 
     return other.freq == this.freq && other.name.equals(this.name); 
    } else { 
     return false; 
    } 
    } 

    @Override 
    public int compareTo(Frequency other) { 
    if (freq == other.freq) { 
     return name.compareTo(other.name); 
    } else { 
     return freq - other.freq; 
    } 
    } 

    @Override 
    public String toString() { 
    return name + ":" + freq; 
    } 

} 

uscita:

fred: 1
art: 3
bert: 4
bob: 5
Homer: 5
jim: 10

Answer 5

List<String> list= new ArrayList<String>(); 
    HashMap<String, Integer> map=new HashMap<String,Integer>(); 

    for(String string: list) 
    { 
    if(map.containsKey(string)) 
    { 
     map.put(string, map.get(string)+1); 
    } 
    else { 
     map.put(string, 1); 
    } 
    } 


    Entry<String,Integer> maxEntry = null; 

    for(Entry<String,Integer> entry : map.entrySet()) { 
     if (maxEntry == null || entry.getValue() > maxEntry.getValue()) { 
      maxEntry = entry; 
     } 
    } 

Answer 6

Se vuoi solo il valore che puoi ottenere per questo. In questo esempio ho dovuto ottenere il frequenza massima di un numero fra una serie di numeri 'n'

 { 
     int n = sc.nextInt(); 
     int arr[] = new int[n]; 
     int freq = 1; 
     int i; 
     Map<Integer,Integer> myMap = new HashMap<Integer,Integer>(); 

     for(i=0;i<n;i++){ 

      arr[i] = sc.nextInt(); 
      if(!myMap.containsKey(arr[i])){ 

       myMap.put(arr[i],freq); 

      } 
      else 
       { 

       myMap.put(arr[i],(myMap.get(arr[i])+1)); 

      } 

     } 

     int max = 0; 
     for(i=0;i<n;i++){ 

      if(myMap.get(arr[i])>max)  
      max = myMap.get(arr[i]); 

     } 
     System.out.println(max); 
    } 

Answer 7

Questo è il mio approccio.

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.HashMap; 
import java.util.Map; 
import java.util.Map.Entry; 

public class FindWordCounter { 

public static void main(String[] args) { 
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); 

    try { 

     System.out.println("Enter the sentence: "); 
     String sentence = bufferedReader.readLine(); 
     FindWordCounter.countWord(sentence); 

    } catch (IOException e) { 

     System.out.println(e); 

    } 
} 

public static void countWord(String sentence) { 

    Map<String, Integer> hashMap = new HashMap<String, Integer>(); 
    String[] word = sentence.toLowerCase().split(" "); 

    for (int i=0; i<word.length; i++) { 

     if (hashMap.containsKey(word[i])) { 

      int count = hashMap.get(word[i]); 
      hashMap.put(word[i], count + 1); 

     } 
     else { 
      hashMap.put(word[i], 1); 
     } 
    } 

    Entry<String,Integer> maxCount = null; 

    for(Entry<String,Integer> entry : hashMap.entrySet()) { 

     if (maxCount == null || entry.getValue() > maxCount.getValue()) { 
      maxCount = entry; 

     } 
    } 

    System.out.println("The word with maximum occurence is: " + maxCount.getKey() 
          + " and the number of occurence is: " + maxCount.getValue()); 
} 

}