HashTable Java Implementation

Question

I have to implement a hash table which will use an array, however have to follow a guide and create functions for each procedure. I would appreciate if anyone could help out in completing this for me as I am having some trouble.

public class HashTable {

// public for testing purposes
public int buckets[];

public HashTable(long _a, long _c, long _m) {
}

public void insert(int key) {
}

}

What I've got so far:

public class HashTable {

// public for testing purposes
public int buckets[];

public HashTable(long _a, long _c, long _m) {
    table = new Node[];
    
}

public void insert(int key) {
    Node<T> newNode = new Node(key);
    int posPosition = calPosition(key);
    
}

I have included what I have done so far. Maybe I'm going about it the wrong way. I understand the concept but cannot seem to write code for the hash table so far. Would appreciate any help, Thanks Again

Answer 1

• A hash table is simply a list or array of buckets.
• Each bucket holds all items the key that hashes to for that particular bucket.
• those items are entries that contain the key and the value you are seeking.

When putting something in a hash table, you use the key/value pair. If the buckets are in an array, use the hash code of the key to get the proper index of the array. If you use a linked list you might have to count to the location.

Then use another array or linked list to store then entry at that cell. Linked lists are better, imo, because they can be added without worry of exceeding the size of the array. They can just be added to the front like a regular linked list.

When adding a value, create the entry, hash the key and find the bucket. Then add the entry to the bucket.

When retrieving a value, hash the key, get to the bucket and do a linear search on the bucket to find the entry for the key you are looking for. Then return the value for that entry.

Note: As with most hash tables, you cannot have duplicate keys. And any Object which is used as a key must override equals and hashCode for this to work.