字符串在Java哈希表中出現的次數

Question

我試圖從文本文件輸入數千個字符串，然後能夠對最流行的字符串進行排名。 我迷失在如何跟蹤每個字符串有多少。

我是否需要實現另一個ADT，如鏈表？ 我不允許使用除ArrayList之外的java庫。

這是我到目前爲止。

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

這裏是我需要實現的接口。 對帖子不重要，但它可以用來更好地理解我正在嘗試做什麼。

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

如果只有Java的ADT你被允許使用的是ArrayList，我建議你使用一個並呼籲它Collections#sort一個自定義Comparator，然後Collections#frequency找到最常見的元素的頻率。

假設list已初始化每個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))); 

看到，因爲你只允許使用一個ArrayList，這種方法很可能是對你太先進。有些方法可以用嵌套的for循環來完成，但這會非常麻煩。

Answer 2

你不必爲此寫一個散列表。你可能只是有這樣的事情：

class Entry { 
    String key; 
    int count; 
} 

List<Entry> entries; 

然後當你想找到一個入口，只是環比列表：

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

哈希表中的時間複雜度方面要好很多，但對於剛接觸數據結構的人來說，坦白說這是一項艱鉅的任務。如果散列表真的是這項任務的必要組成部分，那就不要理會這一點，但我只想指出，這不是絕對必要的。