Integer into Linked List in an array

Question

I am working on an assignment where integers are fed into the app, the integers are hashed, then placed into an array. Each position in the array is a Linked List which I have written. My issue is that I cannot seem to specify which position in the array the integers should go. At present, my output is the last five integers to be placed in for every location in the array except position 10, which is null. Any help would be greatly appreciated. Thank you.

public class MyHashTab {
  private static MyList last;
  private static MyList first;

  public MyHashTab(int initialCapacity, MyList[] anArray) {

  }

  public static void insert(int searchKey, MyList[] anArray) {
    int hash = searchKey % anArray.length;
    MyList current = new MyList(searchKey);

    current.next = null;

    if (anArray[hash] == null) {
      current.next = null;
      first = current;
      last = current;
      anArray[hash] = current;
    } else {
      last.next = current;
      last = current;
    }
  }

  public static void printHash(MyList[] anArray) {
System.out.println("The generated hash table with separate chaining is: ");

    for (int i = 0; i < anArray.length; i++) {
      if (anArray[i] == null) {
        System.out.println("\nThe items for index[" + i + "]: ");
        i++;
      }

      System.out.print("\nThe items for index[" + i + "]: ");
      MyList temp = first;

      while (temp != null) {
        System.out.print(temp.iData + "\t");
        temp = temp.next;
      }
    }
  }
}

public class MyList {
  int iData; // This integer is used as a key value, and as a way to see the actual node instead of it's memory address.
  MyList next; // This is a pointer to a nodes right child. 

  public MyList(int searchKey) {
    this.iData = searchKey;
  }
}

I believe the issue lies in the else statement starting at line 26. I am not assigning which linked list to make the new integer part of. Is there a correct way to write,

anArray[hash].last.next = current;
anArray[hash].last = current;

I added print statements to both the if and the else statements and I am using both. Thank you.

Output

The generated hash table with separate chaining is: 
The items for index[0]: 366 976 312 244 655
The items for index[1]: 366 976 312 244 655
The items for index[2]: 366 976 312 244 655
The items for index[3]: 366 976 312 244 655
The items for index[4]: 366 976 312 244 655
The items for index[5]: 366 976 312 244 655
The items for index[6]: 366 976 312 244 655
The items for index[7]: 366 976 312 244 655
The items for index[8]: 366 976 312 244 655
The items for index[9]: 366 976 312 244 655
The items for index[10]: 
The items for index[11]: 366    976 312 244 655 

The expected output should be something like this. The generated hash table with separate chaining is:
The items for index [0]: 36 60 108 312
The items for index [1]: 85
The items for index [2]: 290 422
The items for index [3]: 99 135
The items for index [4]: 76 148 244 568 976
The items for index [5]: 29 173 245
The items for index [6]: 366
The items for index [7]: 619 655 703
The items for index [8]: 56
The items for index [9]: 345
The items for index [10]:
The items for index [11]: 23 47

Each integer placed in the arraylist at the proper position after being hashed.

Answer 1

Disclaimer: I ranted a bit. I'm just trying to put everything down that is relevant. If you're only interested in the solution scroll down to where I have bolded a heading...

Starting from the beginning, like Nathaniel Ford mentioned I believe you have a conceptual misunderstanding of how a HashTable implementation works. Let's start by breaking down the logic.

A HashTable is a construct used to store and quickly retrieve objects by computing a unique (or nearly unique) hash of the object you're storing. When you compute this one way hash and use it to store an object in the table you allow O(1) lookup at ideal cases.

In a perfect world all inputs would hash uniquely and there would never be a collision but we know that is not practical. So when you have more than one object you need to have a collection that allows you to store multiple objects to the same hash value; a LinkedList!

Now with a set array of 12 values you need to have a unique LinkedList for each element. Your expected output if written out would be like this:

hashTable[0] = LinkedList(Node(36) -> Node(60) -> Node(108) -> Node(312))
hashTable[1] = LinkedList(Node(85))
etc...

Currently you're attempting to mash the idea of a single linked list together with the collection of linked lists. We see this misunderstanding here:

private static MyList last;
private static MyList first;

By declaring first and last as class variables you're essentially creating the belief that there is ever only one first and one last variable for the entire collection of Linked Lists where each list individually should have its own first/last pointers. What the result of your code creates is logic where Nodes inserted to various positions in the array have references to positions that are entirely unrelated to them.

So in reality, where to start fixing?

Clean up your insert method in such you take things step by step.

1) Compute the incoming object's hash
2) Lookup the hash on the array
3) If the array location is null, generate a new Linked List and insert the value into the array
3b) If the array is not null, create a new node for the list and point the final node of the existing list to the new node
4) Done

Nathaniel's code is perfect for this need but if you're forced to use the MyList implementation it would behave something like this:

int hash = searchKey % arr.length;
MyList newNode = new MyList(searchKey);
MyList arrIndex = arr[hash];

if (arrIndex == null) {
  arr[hash] = newNode;
} else {
  while (arrIndex.next != null) { 
    arrIndex = arrIndex.next;
  }
  arrIndex.next = newNode;
}

Additionally your printHash method has need of updating due to two issues.

1) Your logic for increasing i in the event arr[i] is null can cause you to go out of bounds. In the case where the last index of the array is null you would increase i without ever checking it. You're better off doing a check like this and letting the loop do the work for you:

if (anArray[i] == null) {
  continue;
}

or to keep code more clean (no random jumps in program flow)

for (...) {
  if (anArray[i] != null) {
    //Code to print that array
  }
}

2) Without using first and last anymore you just iterate over each element

for (int i = 0; i < anArray.length; i++) {
  System.out.print("\nThe items for index[" + i + "]: ");

  if (anArray[i] != null) {
    MyList tmp = anArray[i];
    while ((tmp = tmp.next) != null) {
      System.out.print(tmp.iData + " ");
    }
  }
}

Answer 2

You have a subtle misunderstanding of what a LinkedList is, and how it should operate.

public class LinkedList {
  //These should NOT be static
  private Node last;
  private Node first;

  public LinkedList(Node initialNode) {
    this.last = initialNode;
    this.first = initialNode;
  }

  public static void insert(int searchKey, LinkedList[] arr) {
    int hash = searchKey % arr.length;

    Node newNode = new Node(searchKey);

    if (arr[hash] == null) {
      arr[hash] = new LinkedList(newNode);
    } else {
      LinkedList list = arr[hash];
      list.add(newNode);
    }
  }

  public void add(Node node) {
    //here you should add this node to the end of this linked list
    this.last.addNext(node); //tell the current last node about the new last node
    this.last = node; //point the last pointer of this list to the new node
  }

  public static void printHash(LinkedList[] arr) {
    System.out.println("The generated hash table with separate chaining is: ");

    for (int idx = 0; idx<arr.length; idx++) {
      System.out.println("\nThe items for index[" + idx + "]: ");
      if (arr[idx] != null) {
        arr[idx].print();
      }
    }
  }

  public void print() {
    Node node = this.first;
    System.out.print(temp.iData + "\t");
    while (node.hasNext()){
      node = node.getNext();
      System.out.print(temp.iData + "\t");
    }
  }
}

public class Node {
  int iData; 
  Node next = null; // This is a pointer to a nodes right child. 

  public MyList(int searchKey) {
    this.iData = searchKey;
  }

  public Node getNext() {
    return this.getNext();//Note this might be null!
  }

  public boolean hasNext() {
    if (this.next == null) { return false; }
    return true;
  }

  public void addNext(Node node) {
    this.next = node;
  }
}

You can call this code as follows:

LinkedList[] arrayOfLists = new LinkedList[12];//sets up an array of 12 linked lists
LinkedList.insert(36, arrayOfLists);
arrayOfLists.printHash();

But note that normally for this sort of thing the insert() method would not be static. Understanding static members and methods is very important in OOP. A static member will be the same for all instances of that class. Most objects must be instantiated (new SomeObject()); an instantiated object has it's own copy of each non-static member. Non-static functions can only be called on an instantiated object: LinkedList.insert(36, arrayOfLists);//calling a static method

LinkedList list = new LinkedList(Node someNode);//Instantiating a new LinkedList object
list.print();//calling a non-static function on an instantiated object