What to do about empty indices within a Hash Table in Java?

0

For a CS project I'm working on, my goal is to create a separate-chained hash table that can be resized if the number of nodes becomes too great. My hash() method is as follows:

private int hash(String key) {
    int hashCode = key.hashCode();
    return (hashCode & 0x7fffffff) % arraySize;
}

arraySize is the size of my Hash Table. My problem is that, after resize() is called, the hash table resizes correctly, but does not utilize one of the hash table indices when rehashing all of the Nodes. Resize() is as follows:

private void alternateResize() {
    Node [] holderTable = hashTable.clone();
    arraySize = 1 + (tableSize/4);
    hashTable = new Node[arraySize];
    tableSize = 0;
    for (int index = 0; index < holderTable.length; index++) {
        if (holderTable[index] == null) {
            continue;
        }
        else {
            Node currentNode = holderTable[index];
            put(currentNode.entry.getKey(), currentNode.entry.getValue());
            while (currentNode.next != null) {
                currentNode = currentNode.next;
                put(currentNode.entry.getKey(), currentNode.entry.getValue());
            }
        }
    }
}

The output, after resize is called, for a hashTable of random Strings in a separate-chain format, is this:

Key: indian Value: 8
Linked List Av Length 4.25
Array Size 13
(0): null
(1):  -> [globular : 49] -> [tejas : 19] -> [apple : 0] -> [underneath : 20]
(2):  -> [louise : 11] -> [asdf : 44] -> [susie : 18] -> [manos : 12] -> [nbnbj : 46]
(3):  -> [indian : 8] -> [fake : 5] -> [bb : 28] -> [gas : 6] -> [winning : 22]
(4):  -> [bc : 29] -> [huhit : 45] -> [hit : 7] -> [klark : 10] -> [banana : 1]
(5):  -> [quizzical : 16]
(6):  -> [finn : 40] -> [gf : 32] -> [cockaroach : 30]
(7):  -> [ortiz : 14] -> [yu : 38]
(8):  -> [giddy : 42] -> [jamie : 9] -> [bpbbu : 43] -> [qw : 35]
(9):  -> [cranberry : 2] -> [xxxtentation : 23] -> [yolanda : 24]
(10):  -> [cd : 31] -> [nob : 50] -> [oi : 39] -> [plmk : 48] -> [he : 37] -> [aa : 26]
(11):  -> [vox : 21] -> [zt : 33] -> [nb : 36] -> [noreaga : 13] -> [ab : 27] -> [qoru : 47] -> [portly : 15] -> [dichotomy : 3] -> [earl : 4]
(12):  -> [ty : 34] -> [zack : 25] -> [lomi : 41] -> [rational : 17]

As you can see, index 0 is empty. Here is another example, after another resize to array size 16 (to maintain short separate chains):

Put
Key: rational Value: 17
Linked List Av Length 4.066666666666666
Array Size 16
(0):  -> [aa : 26] -> [yolanda : 24] -> [winning : 22] -> [bb : 28] -> [globular : 49]
(1):  -> [qoru : 47] -> [ab : 27] -> [nob : 50] -> [cd : 31] -> [bc : 29]
(2):  -> [jamie : 9] -> [ortiz : 14] -> [nbnbj : 46]
(3):  -> [nobody : 56] -> [finn : 40] -> [hit : 7]
(4):  -> [nb : 36] -> [asdf : 44]
(5):  -> [ty : 34] -> [chicken : 55] -> [banana : 1] -> [fake : 5]
(6):  -> [earl : 4] -> [plumstar : 54] -> [xxxtentation : 23] -> [qw : 35] -> [wrxs : 52] -> [interception : 59] -> [huhit : 45] -> [dictionary : 57] -> [underneath : 20]
(7):  -> [noreaga : 13] -> [bpbbu : 43] -> [giddy : 42] -> [indian : 8]
(8): null
(9):  -> [fob : 51] -> [klark : 10] -> [gas : 6] -> [louise : 11]
(10):  -> [zt : 33] -> [plmk : 48] -> [oi : 39] -> [cranberry : 2] -> [quizzical : 16] -> [apple : 0] -> [abox : 58]
(11):  -> [eibbdk : 53] -> [tejas : 19]
(12):  -> [dichotomy : 3] -> [yu : 38] -> [cockaroach : 30]
(13):  -> [he : 37] -> [susie : 18]
(14):  -> [rational : 17] -> [portly : 15] -> [todayshow : 60] -> [manos : 12]
(15):  -> [lomi : 41] -> [zack : 25] -> [vox : 21] -> [gf : 32]

In this case, index 8 is left null. Is it normal for hash() to skip a certain index, or is this an issue with my code? put() is listed below for reference.

public void put(String key, Integer value) {

    Node searchResult = findEntry(key);

    if (searchResult != null){ //if the node is in the table
        searchResult.entry.setValue(value);
        return;
    }

    Entry newEntry = new Entry(key, value);
    Node newNode = new Node(newEntry);

    int index = hash(key);
    if (hashTable[index] != null)
        newNode.next = hashTable[index];

    hashTable[index] = newNode;
    tableSize++;

    System.out.println("Put");
    System.out.println("Key: " + key + " Value: " + value);
    System.out.println("Linked List Av Length " + linkedListAvLength());
    System.out.println("Array Size " + arraySize);
    toString();

    if (linkedListAvLength() > 5) alternateResize();

}
java
hash
hashtable
asked on Stack Overflow Nov 29, 2017 by markiv189

0 Answers

Nobody has answered this question yet.


User contributions licensed under CC BY-SA 3.0