Implementing a Hash Table

[John Molloy]

Alright so we have to implement a basic hash table for an assignment. It seems so simple but it's kicking my ass.
Basically what we have is an input file that contains the amount of entries on the first line and a dns record on each subsequent line.
So we are meant to make 3 classes: DNSKey, Record and HashTable.
These are the outlines they've given us

1. DNSkey
           methods: k = DNSkey.new(domain name, source address)
                                creates a new DNSkey
                          h = k.hashfn()
                                returns a hash value for k; use the sum of ASCII values for
                                all characters in domain_name and source_address.
                                Caller must reduce h modulo the hash table size.
                          b = k.equal(key)
                                true if key matches k.key, false otherwise
                          k.toString
                                returns a string containing {components of k's key}
2. Record
           methods: r = Record.new(key, value)
                               creates a new Record; with `count', an integer instance variable.
                               [For this assignment key is simply stored in the Record.]
                          r.update()
                               increments count by 1
                          r.toString
                               returns a string containing {components of r},
                               i.e. {key, value, count}
3. HashTable
           methods: ht = HashTable.new(m)
                              creates a new hash table which can hold at most
                              m elements. Your table must use the OALP
                              algorithm, searching down the array to resolve
                              hash collisions
                          r = ht.search(k)
                             returns null if ht has no Record with key k,
                             or Record r that has key k
                          r = ht.insert(key, value)
                             inserts a Record, r, into the hash table
                         ht.summary()
                             prints summary information about ht described in question 2 below.

I have been trying to use an array of DNSKey's which are placed into a position decided by the hash function. I am however unsure if I even need an array of DNSKey's or if they should be hashed. So I'm basically wondering how I would map those DNSKey's to a record and placing that record
into the hashtable, while keeping track of the duplicates. The rest of the code basically follows the specification although I am a little unsure on how I would go about the HashTable class.

Here is the code I'm using to do what I explained:

	public void start() {
		try {
			sc = new Scanner(new File("a3smallsampleinput.txt"));
			sc.useDelimiter(Pattern.compile("(\\n)"));
		} catch (FileNotFoundException e) {
			System.out.println("File not found");
		}
		size = sc.nextInt();
		HashTable ht = new HashTable(size);
		DNSKey[] dnsKeys = new DNSKey[size];
		
		while (sc.hasNext()) {
			String temp = sc.next();
			String[] halves = temp.split("\\s+");
			String name = halves[0];
			String ipAddress = halves[1];
			DNSKey initialKey = new DNSKey(name, ipAddress);
			int key = initialKey.hashFn() % size;
			ht.insert(key,0);
			while (dnsKeys[key] != null){
				if (key > 0) {
					key = key - 1;
				}
				else {
					key = dnsKeys.length - 1;
				}
			}
			dnsKeys[key] = initialKey;
		}

And HashTable class

import java.util.ArrayList;


public class HashTable {

    ArrayList<Record> data;
    private int size;
    int index;

    public HashTable(int size) {

        this.size = size; 
        data = new ArrayList<>();
    }

    public int size() {

        return size;
    }

    public Record search(int key) {

    	Record temp = null;
        for (int i = 0; i < data.size(); i++) {
        	if (data.get(i) != null && data.get(i).getKey() == key) {
        		temp = data.get(i);
        		index = i;
        	}
        }
        return temp;
    }

    public void insert(int key, int value) {
    	
    	Record testRecord = search(key);

            if (testRecord != null) {
            	data.get(index).update();
            }
            else {
            	data.add(new Record(key,value));
            }
    }
	
	public void highestCount(DNSKey[] keys) {
		int j = 0;
		Record temp;
		while (data.get(j) == null) { 
			j++;
		}
		temp = data.get(j);
		for (int i = j + 1; i < data.size(); i++){
			if (data.get(i) != null && data.get(i).getCount() > temp.getCount()) {
				temp = data.get(i);
			}
		}
		System.out.println(keys[temp.getKey()] + " " + temp.getCount());
	}

At the end I basically have to output the DNS key that occured the most and the amount of times it occured.

Thanks a ton if anyone can help/\.

[Jelle Klap]

John Molloy wrote:
I have been trying to use an array of DNSKey's which are placed into a position decided by the hash function. I am however unsure if I even need an array of DNSKey's or if they should be hashed. So I'm basically wondering how I would map those DNSKey's to a record and placing that record
into the hashtable, while keeping track of the duplicates. The rest of the code basically follows the specification although I am a little unsure on how I would go about the HashTable class.

Maintaining an array to store the elements in your HashTable class would be good choice. Alternatively you could use a Collection that implements the RandomAccess interface, of which ArrayList would be most suitable. I'd go for an array, though. A general purpose HashTable would likely use an inner class that represents an entry in the HashTable that wraps both the key and the value, however, if all you're going to store are Record objects that does not seem necessary as: "For this assignment key is simply stored in the Record". So your HashTable can simply maintain an array of Record objects, right? Well, if you could be absolutely sure that the hashing algorithm would always return a unique value, then yes, however the algorithm description is as follows: "use the sum of ASCII values for all characters in domain_name and source_address. Caller must reduce h modulo the hash table size". So there's quite a good chance of duplicate hash code's for different values. Such an occurence is called a "collision". That means keeping track of an array of Record objects directly is not good enough, as a Record in the array would be overwriten by adding another Record wo's key happens to hash to the same index position, but which is otherwise unequal. One of the simplest conceptual ways to deal with this problem would be to maintain an array of an array of Record objects. That way a key's hash value would always represent an array of Record objects, which means you could keep track of more than one Record for a given hash value. That nested array would represent what's known as a "bucket". However, implementing a bucket using an array is not really ideal, because an array's size is not dynamic. A linked list would probably be more efficient bucket implementation. See if you can work out a solution like this.