I have some code for a assignment where the main marks are awarded based on efficiency. The program uses a given wordgenerator which generates random words and adds them to a user-made data structure. You also have to provide 3 methods, one to add a item, one to remove a item and one to count how many times a word is present in the structure. Here is my code:
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"));
}
}
So far I have written two of the methods, add and count. Whilst my add function is very quick, the count method is rather slower and takes a lot more time to compute. Is there a more efficient way to write this method or change things here to make it quicker?
Also - we arent allowed to use any methods or data structures that are inbuilt Java methods, such as HashMaps.
HashMap
, you could look into aTrie
. It should be faster than theLinkedList
backing (which should also contain a count instead of duplicates). Do note that just increasing the size of theHashMap
may also help with lowering the collision rate \$\endgroup\$String
class has a.hashCode()
method. Are you allowed to use that? \$\endgroup\$