Nombre de fois qu'une chaîne apparaît dans une table de hachage Java

Question

J'essaie d'entrer des milliers de chaînes à partir d'un fichier texte, puis de classer les chaînes les plus populaires. Je suis perdu sur la façon de garder une trace du nombre de chaînes qu'il y a. Dois-je implémenter un autre ADT, comme linkedlist? Je ne suis pas autorisé à utiliser les bibliothèques Java à l'exception de ArrayList.

Voici ce que j'ai jusqu'à présent.

public class StudentTrends implements Trends { 
    int entries = 0; 
    //ArrayList<Integer> list; 
    String[] table; 
    int arraySize; 

public StudentTrends() { 
    //this.list = new ArrayList<Integer>(); 
    this.table = new String[10]; 
    Arrays.fill(table, "-1"); 
} 

//Method I'm having trouble with 
@Override 
public void increaseCount(String s, int amount) { 
    int key = horner(s); 

    if(table[key] == null){ 
     entries++; 
     //table[key] = table[key]; 
    } 
    else{ 
     amount += 1+amount; 
    } 
} 


/** 
* The hashing method used 
* @param key 
*   Is the String inputed 
* @param size 
*   Size of the overall arraylist 
* @return 
*   The int representation of that string 
*/ 
private int horner(String key){ 
    int val = 0; 

    for(int a = 0; a < key.length(); a++){ 
     val = ((val << 8) | (a)) % table.length; 
    } 
    table[val] = key; 
    return val; 
} 

Et voici l'interface que je dois implémenter. Pas essentiel pour le poste, mais il peut être utilisé pour mieux comprendre ce que je suis en train de faire.

public interface Trends { 

/** 
* Increase the count of string s. 
* 
* @param s   String whose count is being increased. 
* @param amount  Amount by which it is being increased. 
*/ 
public void increaseCount(String s, int amount); 

/** 
* Return the number of times string s has been seen. 
* @param s  The string we are counting. 
* @return int The number of times s has been seen thus far. 
*/ 
public int getCount(String s); 


/** 
* Get the nth most popular item based on its count. (0 = most popular, 1 = 2nd most popular). 
* In case of a tie, return the string that comes first alphabetically. 
* @param n   Rank requested 
* @return string nth most popular string. 
*/ 
public String getNthMostPopular(int n); 

/** 
* Return the total number of UNIQUE strings in the list. This will NOT be equal to the number of 
* times increaseCount has been called, because sometimes you will add the same string to the 
* data structure more than once. This function is useful when looping through the results 
* using getNthPopular. If you do getNthPopular(numEntries()-1), it should get the least popular item. 
* @return Number of distinct entries. 
*/ 
public int numEntries(); 

};

Answer 1

Si le seul Java ADT vous êtes autorisé à utiliser est un ArrayList, je vous suggère d'utiliser un et appelez Collections#sort sur elle avec une coutume Comparator, puis Collections#frequency pour trouver la fréquence de l'élément le plus commun.

En supposant list est déjà initialisés avec chaque String:

Collections.sort(list, Comparator.comparing(s -> Collections.frequency(list, s)).reversed()); 

// Frequency of most common element 
System.out.println(Collections.frequency(list, list.get(0))); 

Voyant que vous êtes autorisé à utiliser un ArrayList, cette méthode sera très probablement trop avancé pour vous. Il y a des façons de le faire avec des boucles for-imbriquées, mais ce serait très compliqué.

Answer 2

Il n'est pas nécessaire d'écrire une table de hachage pour cela. Vous pourriez avoir quelque chose comme ceci:

class Entry { 
    String key; 
    int count; 
} 

List<Entry> entries; 

Et puis quand vous voulez trouver une entrée, boucle un peu plus de la liste:

for (Entry e : entries) { 
    if (e.key.equals(searchKey)) { 
     // found it 
    } 
} 

Une table de hachage est beaucoup mieux en termes de complexité de temps , mais franchement, c'est une tâche vraiment décourageante pour quelqu'un qui est nouveau dans les structures de données. Si la table de hachage est vraiment une partie nécessaire de l'assignation, alors ne tenez pas compte de cela, mais je voulais juste faire remarquer que ce n'est pas strictement nécessaire.