Reimplementation of a Hashtable and hash function

Question

package com.raja.util;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Hashtable {
    private Object[] slots;
    private int capacity;

    Hashtable(int size) {
        capacity = size;
        slots = new String[size];
        Arrays.fill(slots, "-1");
    }

    // Simple hash function that puts values in the randomly generated index that generated within the limits of the given Hashtable size
    public void myHashFunction(Object[] elements, Object[] slots) {
        Random random = new Random();
        for (int n = 0; n < elements.length; n++) {
            int randomIndex = randomIndex(0, capacity, random);
            if(randomIndex < capacity){
                while((String)slots[randomIndex] != "-1" && randomIndex != capacity){
                    randomIndex = randomIndex(0, capacity, random);
                }
                slots[randomIndex] = elements[n];
            }
        }
    }

    //Generates a random number in the limits of begin and end
    private static int randomIndex(int begin, int end, Random aRandom){
        if (begin > end) {
          throw new IllegalArgumentException("Start cannot exceed End.");
        }
        long range = (long)end - (long)begin + 1;
        long fraction = (long)(range * aRandom.nextDouble());
        int randomNumber =  (int)(fraction + begin);    
        if(randomNumber == end)
            randomNumber--;
        return randomNumber;
      }

    // Returns the value stored in the Hash slots
    public Object getValue(int key) {
        if(getKeys().contains(key)){
            return slots[key];
        } else return null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{ ");
        for(int i = 0; i < slots.length; i++){
            if(slots[i] != "-1")
                sb.append(i+"->" + slots[i] + ", ");
        }
        sb.append("}");
        int lastIndex = sb.lastIndexOf(",");
        sb.replace(lastIndex, lastIndex + 1, "");
        return sb.toString();
    }

    // Returns the key indexes where the elements got stored.
    public Set<Integer> getKeys(){
        Set<Integer> keys = new HashSet<Integer>();
        if(slots != null){
            for(int index = 0; index < slots.length; index++){
                if(slots[index] != "-1"){
                    keys.add(index);
                }
            }
        }
        return keys;
    }

    //Testing : Storing A-Z alphabets in Hashtable
    public static void main(String[] args) {
        Object[] elements = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"};
        Hashtable myHashtable = new Hashtable(1000);  //Big size (i.e. 1000) is used to illustrate the random hash keys
        myHashtable.myHashFunction(elements, myHashtable.slots);
        System.out.println("Keys = "+ myHashtable.getKeys());
        if(myHashtable.getKeys().size() != elements.length) { 
            System.out.println("Oops!, some element(s) were not stored in your hashtable");
        }
        System.out.println("Your Hashtable = " + myHashtable);
    }
}

The output of this program would be something like:

Keys = [611, 954, 199, 406, 892, 25, 214, 633, 265, 391, 759, 102, 307, 236, 990, 36, 432, 918, 433, 40, 435, 522, 591, 775, 250, 726]
Your Hashtable = { 25->O, 36->S, 40->I, 102->H, 199->D, 214->N, 236->X, 250->Y, 265->K, 307->B, 391->F, 406->A, 432->M, 433->Q, 435->C, 522->V, 591->U, 611->G, 633->P, 726->J, 759->W, 775->R, 892->Z, 918->E, 954->T, 990->L }

Answer 1

Your container isn't what most people would call a hash table. It doesn't use a deterministic hash function of its contents, and it doesn't give the expected performance. That said, here are some other comments on your "container".

myHashtable.myHashFunction(elements, myHashtable.slots);

This is a strange name for the function that adds elements to your container.

private Object[] slots;
slots = new String[size];
public void myHashFunction(Object[] elements, Object[] slots)

Your class acts like it can work on any Object, but it will fail if given anything other than a String.

Arrays.fill(slots, "-1")

This is a strange string to use as your empty sentinel. What happens if someone wants to add "-1" to your container? What's wrong with null as an empty marker?

Answer 2

Wikipedia page for Hash function

Determinism

A hash procedure must be deterministic—meaning that for a given input value it must always generate the same hash value.

In this code you are making a new Random() which will have a random seed. If you want to use Random you need to at least give it a specific seed so it behaves deterministically.

Even then though you're not really making hash codes, you're just putting things in a container in an order dependent on the amount being put in. Your hash needs to be based on the things being put in, and it needs to be the same every time for an Object that hasn't been modified.

I don't think you understand what hashes are (I don't mean that in a rude way). I suggest you look up what they are.

You're not using .hashCode() anywhere, which isn't necessarily an issue, it's just a good way to get a hash of an Object. You said you're reinventing the wheel, so I can understand not using .hashCode(), but the thing you've made isn't based on the things being put into the list, so it's like you're reinventing the wheel and coming up with fire and calling it a wheel.

In myHashFunction randomIndex is acting as the hash because you're calling this a hash table, but it's not based at all on the things being put in.

---

Here is a bit of an explanation of hashes and hash lookups to help you out.

Hashing can be thought of like this

Thing -> [Decoder] -> Hash

The [Decoder] takes in a Thing of any size and outputs a Hash of constant size. I will use Strings as an example. In Java, the hashCode() method takes this and returns an int, in my little metaphor above [Decoder] depends on the type.

Here's some examples of what it could look like

"a" -> [Decoder] -> "112343"
"My name is Captain Man and I am typing." -> [Decoder] -> "000000"

Now let's talk about how the [Decoder] part works, you could make a really bad hasher that hashed Strings and just returned the int value of the first char. Even though it's bad it still qualifies as a hasher because it's deterministic and the same input always produces the same output.

If I put in "Cool beans" it'd hash to C. If I put this in a hash table it'd look something like this

C: "Cool beans"

If I put in "Abcdefg", "Cooler beans", and "Dude" it'd look something like this

A: "Abcdefg"
C: "Cool beans", "Cooler beans"
D: "Dude"

Now suppose I want to see if something is in it, if this were a list I'd have to iterate over everything, but since it's a hash table I can hash what I am putting in to get a good "starting point" to look. There's two things at C. In "the real world" your hash function will be (should be) better than looking at a single character. It should be unlikely to have the same hash as something else, but it's impossible to avoid 100%.