字符串在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 
    } 
} 

哈希表中的时间复杂度方面要好很多，但对于刚接触数据结构的人来说，坦白说这是一项艰巨的任务。如果散列表真的是这项任务的必要组成部分，那就不要理会这一点，但我只想指出，这不是绝对必要的。