用于计数单词出现次数的数据结构

Question

我有一些代码的分配，其中主要的评分是基于效率的。该程序使用给定的字生成器，生成随机单词并将它们添加到用户创建的数据结构中。您还必须提供3种方法，一种是添加项，一种是删除项，另一种是计算一个单词在结构中出现的次数。这是我的代码：

public class WordStoreImp implements WordStore{

public class Node{
   public String data;
   public Node next;
   public Node(String addingWord, Node theNext){
        data = addingWord;
        next = theNext;
   }
}

private Node[] array;
int usedAmount=0;


public WordStoreImp(int n){
    array = new Node[n];
}

public void add(String word){
    int position = hashFunction(word);
    array[position]=new Node(word,array[position]);
}

public int count(String word){
    int number = 0;
    int position = hashFunction(word);
    Node temp = array[position];
    while(temp!=null){
        if(temp.data.equals(word)){
            number++;
        }
        temp=temp.next;
    }
    return number;
}

    public int hashFunction(String a){
    int sum = 1;
        for(int i = 0; i<a.length(); i++){
            char b = a.charAt(i);
            int value = (int) b;
            sum *= value;
     }
     sum = sum % array.length;
     if(sum<0){
         return -sum;
     }
     return sum;
 }

public void addthings(String word, int n){
    for(int i = 0; i<n; i++){
        add(word);
    }
}

public int printSize(){
    int count = 0;
    for(int i = 0; i<array.length; i++){
        if(array[i] != null){
            count++;
        }
    }
    System.out.println(count);
    return count;
}

public static void main(String[] args) {
    WordStoreImp a = new WordStoreImp(100);
    a.addthings("abc", 100);
    System.out.println(a.count("abc"));
    System.out.println(a.count("abc"));
}
}

到目前为止，我已经编写了两个方法，add和count。虽然我的add函数非常快，但计数方法非常慢，计算时间也要长得多。是否有一种更有效的方法来编写这个方法，或者在这里进行更改以使它更快？

此外，我们不允许使用内置的任何方法或数据结构，例如HashMaps。

Answer 1

因此，您需要一个数据结构来执行三个操作：

• 添加字符串
• 移除字符串
• 计数串

目前，您的addItems()和count()操作都具有O(n)复杂性--添加100个单词所需的时间是添加一个单词的100倍；同样地，计算一个100次的单词比计算一个有一次出现的单词所花费的时间长100倍。

为提高业绩：

• 考虑一下，你是否真的需要存储100次完全相同的单词？

为进一步改进：

• 当两个不同的单词产生相同的哈希码时会发生什么？