HashTable implementation

Implementing a hash table

This hash table implementation is a bit limited: it supports only String keys and int values. It would be good to generalize it.

When getting a value of a key not in the table, the common expected behavior is null. Since you're using int as the type of values, this is not possible, but -1 just doesn't seem special enough to be commonly understood as "missing value".

The toAscii method is very bad:

• It's only used internally, so it shouldn't be public
• The name doesn't describe very well what it does: converting a string to ascii sounds more like an encoding transformation than a hash code calculation. It would have been better to call it calculateHashCode, and make it return a BigInteger
• Even better would have been to use String's very own hashCode, rather than reimplementing your own

Naming

    HashMap entry = new HashMap();

"entry" is an inappropriate name for a map. "map" would seem the obvious choice.

General coding issues

The HashEntry class is an implementation detail of your hash table. As such, it would be best to hide this class, by making it a private static class inside the hash table.

Instead of this:

new BigInteger(((Integer)TABLE_SIZE).toString());

A much better and simpler way:

BigInteger.valueOf(TABLE_SIZE);

Limit variables to the smallest scope possible, to prevent accidental changes outside their intended purpose. For example in this code:

      long asciiInt;
      // loop through all values in the string, including blanks
      for (int i = 0; i < s.length(); i++){
          //getting Ascii value of character and adding it to the string.
          char c = s.charAt(i);
          asciiInt = (int)c; 
          sb.append(asciiInt);
      }

asciiInt should have been declared inside the loop.

This code looks very confused: you get a char, cast it to an int to store in a long variable. This could have been simply:

    for (int i = 0; i < s.length(); i++){
        sb.append((int) s.charAt(i));
    }

And even simpler with a for-each loop:

    for (char c : s.toCharArray()) {
        sb.append((int) c);
    }

        table = new HashEntry[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++)
              table[i] = null;

When iterating over all elements of an array, I recommend using the array's length as the limit. It's safer. Like this:

        table = new HashEntry[TABLE_SIZE];
        for (int i = 0; i < table.length; i++) { ... }

But since you're only using this loop to assign the values to null, the entire loop is pointless, you can safely delete it.

It's highly suspicious when you compare objects using != like you do for the keys in this code:

    while (table[hash] != null && table[hash].getKey() != key)
        hash = (hash + 1) % TABLE_SIZE;

For example, what do you think this code will print:

    String key1 = new String("Jack");
    String key2 = new String("Jack");
    entry.put(key1, 11);
    entry.put(key2, 21);
    System.out.println(entry.get(key1));
    System.out.println(entry.get(key2));

It will print 11 and 21. I suggest to replace != on objects everywhere with .equals(...). Then these two keys will be considered equal, as usually expected from a hash map, and the print statements will return 21 and 21.

Other coding style issues

• I suggest using braces { ... } even for single-statement blocks

• Instead of comments like /* function to retrieve value from the table according to key */, use proper JavaDoc, for example:

  /**
   * Retrieve value from the table according to key
   * 
   * @param key the key to look for
   * @return the value of the key, or null if doesn't exist
   */
  

• Since the fields of HashEntry never change, you can make them final

• This code block appears twice:

  while (table[hash] != null && !table[hash].getKey().equals(key)) 
      hash = (hash + 1) % TABLE_SIZE;
  

  Avoid code duplication. Extract to a private helper method, or refactor your implementation in a way that you don't have to duplicate code.

  Same note for this code:

  int hash = new BigInteger(toAscii(key)).mod(new BigInteger(((Integer)TABLE_SIZE).toString())).intValue();
  

Improved implementation

Taking some of the suggestions above, the implementation can be simplified and improved:

private int calculateHashCode(String key) {
    int mod = key.hashCode() % TABLE_SIZE;
    return mod < 0 ? mod + TABLE_SIZE : mod;
}

private int findIndex(String key) {
    int index = calculateHashCode(key);
    while (table[index] != null && !table[index].getKey().equals(key)) {
        index = (index + 1) % TABLE_SIZE;
    }
    return index;
}

public int get(String key) {
    int index = findIndex(key);
    return table[index] == null ? -1 : table[index].getValue();
}

public void put(String key, int value) {
    table[findIndex(key)] = new HashEntry(key, value);
}

In addition to @janos's comments and suggestions, I have some other issues to point out.

Infinite loops

Your code will enter an infinite loop when the table is full. Putting in the 33rd value will enter this loop:

        while (table[hash] != null && table[hash].getKey() != key)
              hash = (hash + 1) % TABLE_SIZE;

Even in @janos's suggested code

int index = calculateHashCode(key);
while (table[index] != null && !table[index].getKey().equals(key)) {
    index = (index + 1) % TABLE_SIZE;
}

The loop will not terminate. You need a way to identify and handle a hash-full situation. The most common way to do this 'in real life', is to convert each position in the table in to a linked list of values that all have the same hash. Thus, you can identify index in the table, then just scan the unlimited-size list for the value you need. This makes the HashTable have an unlimited capacity, too, but the performance is impacted when the lists become long, and a rebalance is needed to correct the problem.

Hash using Modulo

You are calculating the index from hash using the modulo by the table size. Since your table-size is 32, the modulo is the remainder when dividing by 32. Since 32 is a power-of-2 (\$2^5\$), you can do simple bit-masking to calculate the remainder. For example, the value 12345 in binary is 0011000000111001. The 'low' 5 bits are: 11001 which is 25. The remainder of 12345/32 is 25 (check it yourself... if you want).

If we do some binary arithmetic, we find the following:

    decimal ->  binary
      12345 ->  0011000000111001
         32 ->  0000000000100000
     32 - 1 ->  0000000000011111

 12345 & 31 ->  0000000000011001
         25 ->  0000000000011001

The bottom line is that power-of-2 sizes for hash tables are very, very convenient. It means we can do a very fast bitwise AND-operation, instead of an expensive Modulo operation.

Sicne this is a common operation in computing, it is worth learning that it is there, and how to do it. In Java, there are language details to help, as well. So for example, if you want a table to have a size of about 50.... we convert that to a power of 2 as follows:

1. find the highest-set bit in the value with Integer.highestOneBit(50) (which will be '32'). Note that this value will always be a power-of-two.
2. find the power-of-2 larger than this value using the left-shift operator: << 1 (left shift by 1 bit, to get 64.
3. get a mask from this value by subtracting 1.

The code would look like:

private final int tableSize = Integer.highestOneBit(approxSize) << 1;
private final int tableMask = tableSize - 1;

Now, wherever you currently have a modulo operation, like:

      hash = (hash + 1) % TABLE_SIZE;

you can instead have:

      hash = (hash + 1) & tableMask;

Also, you can easily calculate the size you want from an input parameter, or something.