文字列が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であれば、私はあなたが最も一般的な要素の周波数を見つけるために、いずれかを使用し、カスタムComparatorでそれにCollections#sortを呼び出し、その後、Collections#frequency示唆しています。 listを想定し

はすでに各Stringで初期化されています。あなただけArrayList使用を許可しているよう

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

を見て、この方法が最も可能性の高いあなたのためにあまりにも高度になります。ネストされたfor-loopsで行うことができる方法がありますが、非常に面倒です。

Answer 2

このためにハッシュテーブルを作成する必要はありません。あなたがリストの上にエントリー、ちょうどループを見つけたいときに

class Entry { 
    String key; 
    int count; 
} 

List<Entry> entries; 

そして：あなたはこのようなものを持っている可能性が

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

ハッシュテーブルは、多くの優れている時間複雑さの点でしかし、データ構造を初めて知った人にとっては、率直に言って本当に大変な作業です。ハッシュテーブルが実際に割り当ての必要な部分である場合は、これを無視してください。ただし、厳密には必要ではないことを指摘したかっただけです。