[keisenpai]

Hello,

First off, this is a homework assignment. I am having some difficulty adding a new item to the HashTable when a collision occurs. We can only use the basic utilities to code this, so we are coding a HashTable by hand. We have an array of length of 10, which each index holds or will hold a Node for a Linked List.
The code hashes fine, adds the item, but the problem exists when adding items that already been hashed. The project is much bigger, but this is the engine behind the rest, and I figured I would tackle this first.
The items we are adding are objects which are states containing different information, we hash based on the ASCII sum % tableSize.

Here is the code I am testing with to add items:

        HashTable ht = new HashTable(10);
        State az = new State("Arizona","AZ","W",2,"Y",2);
        State fl = new State("Florida", "FL", "F", 2, "X", 2);
        State hi = new State("Hawaii", "HI", "H", 3, "Z", 1);
        State al = new State("Alabama", "AL", "A", 5, "W", 0);
        ht.insert(hi);
        ht.insert(az);
        ht.insert(al);
        ht.insert(fl);
        ht.insert(hi);
        ht.insert(fl);
        ht.display();
        ht.insert2(fl);
    }

Here is the insertion method:

    public void insert(State state) {
        int hash = getHash(state.getName());
        Node n = new Node(state);
        Node temp = hashTable[hash];

        if (isEmpty(hash)) { // Check to see if the hashed index of the array is empty
            hashTable[hash] = n;
        } else if (n.getState().getName().compareTo(temp.getState().getName()) <= 0) {
            n.setNext(temp.getNext());
            temp.setNext(n);
        } else {
            n.setNext(temp);
            hashTable[hash] = n;

        }
    }

Appreciate any help!

[g00se]

Have you been told to sort entries in the same bucket?
fyi, the JRE HashMap doesn't

[keisenpai]

g00se, on 21 April 2015 - 02:41 AM, said:

Have you been told to sort entries in the same bucket?
fyi, the JRE HashMap doesn't

Thank you for replying g00se!

Our instructions say in the driver portion to:
3. Insert the State object in to the hash table
a. Calculate the hash value of the state name using a hash function
b. Store the State object in a Node object
c. Insert the Node object into the hash table using the hash value as an index
d. If a collision occurs (a Node object is already stored at that index in the array)
1. Link the Node object to the existing Node object(s) using the Next pointers
a. Node objects should be ordered by the state name

Though it would make sense to order it when inserting it because we could traverse the array. We are also limited on the HashTable class to:
a. Only methods implemented for the interface can be used (a constructor is necessary)

Thanks for the reply!

[g00se]

So the question at this point boils down to: "how do I maintain a sorted singly-linked list". I can't write the code for you to do that but this might point you in the right direction:
http://www.sanfoundr...ly-linked-list/

Check out the insert method

[keisenpai]

g00se, on 21 April 2015 - 03:53 AM, said:

So the question at this point boils down to: "how do I maintain a sorted singly-linked list". I can't write the code for you to do that but this might point you in the right direction:
http://www.sanfoundr...ly-linked-list/

Check out the insert method

Thanks g00se! I will take a look at this. I appreciate the help.

[keisenpai]

g00se, on 21 April 2015 - 03:53 AM, said:

So the question at this point boils down to: "how do I maintain a sorted singly-linked list". I can't write the code for you to do that but this might point you in the right direction:
http://www.sanfoundr...ly-linked-list/

Check out the insert method

Sorry for replying again, but I could not find the [edit] button.
I have this code now, and seems to be adding correctly. I think maybe the error is with in my display method for the hash table.

Here is my insert method:

public void insert(State state) {
        int hash = getHash(state.getName());
        Node n = new Node(state);
        Node temp = hashTable[hash];
        boolean added = false;
        System.out.println("Hashing " + n.getState().getName() + " with an hash of: " +hash);
        if (isEmpty(hash)) {
            System.out.println("add " + n.getState().getName() +" to front");
            hashTable[hash] = n;
            added = true;
        }
        else if (n.getState().getName().compareTo(temp.getState().getName()) <= 0) {
            System.out.println("add " +n.getState().getName() + " before " + temp.getState().getName());
            n.setNext(temp);
            temp = n;
        }
        else {
                Node after = temp.getNext();
                Node before = temp;
                while (after != null && added == false) {
                    if (n.getState().getName().compareTo(after.getState().getName()) < 0) {
                        added = true;
                    }
                    before = after;
                    after = after.getNext();
                }
                n.setNext(before.getNext());
                before.setNext(n);
                System.out.println("add " +n.getState().getName() + " after " + before.getState().getName());
        }
        
    }

Here is my display method, where I think the problem is, I don't think it is searching through the nodes in the linklist on the array.

    public void display() {
        Node temp = null;
        for (int x = 0; x < hashTable.length; x++) { // Traverse the array
            temp = hashTable[x];
            while (temp != null) { // Traverse the linked list
                System.out.format("%d: %d =  %s\n", 1, x, hashTable[x].getState().getName());
                temp = temp.getNext();
            }
        }
    }

Any help would be appreciated, even pointing me in the right direction!

[g00se]

Quote

System.out.format("%d: %d =  %s\n", 1, x, hashTable[x].getState().getName());

Have a look at that carefully and tell me what you think it's displaying, naming all the parameters to that format call

[keisenpai]

g00se, on 21 April 2015 - 03:47 PM, said:

Quote

System.out.format("%d: %d =  %s\n", 1, x, hashTable[x].getState().getName());

Have a look at that carefully and tell me what you think it's displaying, naming all the parameters to that format call

Now looking at it, it would only be displaying the first node, because hashTable[x] refers to the initial node.
I think I may have figured out, let me redo something and I will repost back.

[keisenpai]

keisenpai, on 21 April 2015 - 03:54 PM, said:

g00se, on 21 April 2015 - 03:47 PM, said:

Quote

System.out.format("%d: %d =  %s\n", 1, x, hashTable[x].getState().getName());

Have a look at that carefully and tell me what you think it's displaying, naming all the parameters to that format call

Now looking at it, it would only be displaying the first node, because hashTable[x] refers to the initial node.
I think I may have figured out, let me redo something and I will repost back.

Or I thought I did. I see that during the while loop I referenced hashTable and not temp, I changed that and I ensured I did temp = temp.getNext(); Weird, I am missing something...

Thanks again!

[g00se]

But you didn't answer my question ... Keep looking if you haven't got it

[keisenpai]

g00se, on 21 April 2015 - 03:47 PM, said:

Quote

System.out.format("%d: %d =  %s\n", 1, x, hashTable[x].getState().getName());

Have a look at that carefully and tell me what you think it's displaying, naming all the parameters to that format call

Sorry.
It is displaying three parameters, one static integer of 1.
The second parameter is the counter variable, integer of x that is increased every time the for loop loops.
The last parameter is the hashTable[x].getState().getName() which returns a string name of the State Object.
Which, I changed to temp.getState().getName() because to me it would always refer to the starting node.

[g00se]

Quote

It is displaying three parameters, one static integer of 1.

I don't get that - what is it? You've got the right idea anyway - is the displaying method now working?

btw the correct way to make a linefeed in a format string is %n

[keisenpai]

g00se, on 21 April 2015 - 04:16 PM, said:

Quote

It is displaying three parameters, one static integer of 1.

I don't get that - what is it? You've got the right idea anyway - is the displaying method now working?

btw the correct way to make a linefeed in a format string is %n

Sorry, I didn't explain why the static integer was there. I put it in as a filler. Our professor gave us some code to display the position, hash, and the value, using his variables pos, hash, and val. The first one should be the position that it is in the linked list. I have a idea how to implement this, but since he only gave us a snip of the code, I just had this in as a filler. My main thing was to get the insertion method working, which now led to the display method. I since changed my display method:

    public void display() {
        Node temp = null;
        for (int x = 0; x < hashTable.length; x++) { // Traverse the array
            temp = hashTable[x];
            if (temp != null) {
                System.out.println(x + " - " + temp.getState().getName());
            }
            while (temp != null) { // Traverse the linked list
                System.out.println(x + " - " + temp.getState().getName());
                temp = temp.getNext();
            }
        }
    }

Which displays:
1 - Alabama
1 - Alabama
4 - Arizona
4 - Arizona
5 - Hawaii
5 - Hawaii

It should display Florida as well since it was stored in that hash as well. Here is the output displayed before from the insertion method.

Hashing Hawaii with an hash of: 5
add Hawaii to front
Hashing Arizona with an hash of: 4
add Arizona to front
Hashing Alabama with an hash of: 1
add Alabama to front
Hashing Florida with an hash of: 5
add Florida before Hawaii
Hashing Hawaii with an hash of: 5
add Hawaii before Hawaii
Hashing Florida with an hash of: 5
add Florida before Hawaii