CODEWITHSUNDEEP
javahashhashtable
Harrison Bergman
Harrison Bergman

Reputation: 169

Amount of times a String appears in a Java hash table

I am trying to input thousands of Strings from a text file, and then be able to rank the most popular Strings. I'm lost on how to keep track of how many of each String there are.

Do I need to implement another ADT, like linkedlist? I am not allowed to use the java libraries except for ArrayList.

Here is what I have so far.

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

And here is the interface I need to implement. Not vital for the post, but it can be used to better understand what I am trying to do.

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

};

Upvotes: 2

Views: 337

Answers (2)

Radiodef
Radiodef

Reputation: 37845

You don't have to write a hash table for this. You could just have something like this:

class Entry {
    String key;
    int count;
}

List<Entry> entries;

And then when you want to find an entry, just loop over the list:

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

A hash table is a lot better in terms of time complexity, but it's frankly a really daunting task for somebody who's new to data structures. If the hash table is really a necessary part of the assignment, then disregard this, but I just wanted to point out that it's not otherwise strictly necessary.

Upvotes: 1

Jacob G.
Jacob G.

Reputation: 29680

If the only Java ADT you're allowed to use is an ArrayList, I suggest you use one and call Collections#sort on it with a custom Comparator, and then Collections#frequency to find the frequency of the most common element.

Assuming list is already initialized with each 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)));

Seeing as you're only allowed to use an ArrayList, this method will most likely be too advanced for you. There are ways that you can do it with nested for-loops, but it would be very messy.

Upvotes: 1

Related Questions