Целое число в связанный список в массиве

Question

Я работаю над назначением, где целые числа подаются в приложение, целые числа хэшируются, а затем помещаются в массив. Каждая позиция в массиве - это связанный список, который я написал. Моя проблема заключается в том, что я не могу указать, какую позицию в массиве следует использовать целым числам. В настоящее время мой вывод - это последние пять целых чисел, которые должны быть помещены для каждого местоположения в массиве, кроме позиции 10, которая равна нулю. Любая помощь будет принята с благодарностью. Спасибо.

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; 
    } 
} 

Я считаю, что проблема заключается в заявлении еще начиная с линией 26. Я не назначая который связан список, чтобы сделать новую целую часть. Есть правильный способ написать,

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

Я добавил операторы печати на оба КРП и другое заявление и я использую оба. Спасибо.

Выход

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 

Ожидаемый результат должен быть что-то вроде этого. Генерируются хэш-таблица с отдельной цепочкой является:
Элементами для индекса [0]: 36 60 108 312
детали для индекса [1]: 85
детали для индекса [2]: 290 422
элементов, для индекса [3]: 99 135
детали для индекса [4]: ​​76 148 244 568 976
детали для индекса [5]: 29 173 245
элементы для индекса [6]: 366
The предметы для индекса [7]: 619 655 703
Элементы для индекса [8]: 56
Элементы для индекса [9]: 345
Элементов для индекса [10]:
детали для индекса [11]: 23 47

Каждого целого числа помещается в ArrayList в правильном положении после того, как хэшированные.

Answer 1

Отказ от ответственности: я разглагольствовал немного. Я просто пытаюсь поставить все, что имеет значение. Если вас интересует только прокрутка решения до того места, где я выделил заголовок ...

С самого начала, как и Натаниэль Форд, я считаю, что у вас есть концептуальное непонимание того, как работает реализация HashTable. Начнем с нарушения логики.

HashTable - это конструкция, используемая для хранения и быстрого извлечения объектов путем вычисления уникального (или почти уникального) хэша объекта, который вы храните. Когда вы вычисляете этот односторонний хэш и используете его для хранения объекта в таблице, вы разрешаете поиск O (1) в идеальных случаях.

В идеальном мире все входы будут иметь хэш однозначно и никогда не будет столкновения, но мы знаем, что это непрактично. Поэтому, когда у вас есть несколько объектов, вам необходимо иметь коллекцию, которая позволяет хранить несколько объектов в одном и том же значении хэша; a LinkedList!

Теперь с заданным массивом из 12 значений вам нужно иметь уникальный LinkedList для каждого элемента. Ваш ожидаемый результат, если выписана будет выглядеть так:

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

В настоящее время вы пытаетесь смять идею одного связанного списка вместе со списком связанных списков. Мы видим это недоразумение здесь:

private static MyList last; 
private static MyList first; 

Объявив first и last как переменный класса вы, по сути создавая уверенность в том, что существует всегда только одна first и одна last переменных для всей коллекции связанных списков, где каждый список по отдельности должны иметь свои первые/последние указатели. Результат создания вашего кода - это логика, в которой узлы, вставленные в разные позиции в массиве, имеют ссылки на позиции, которые полностью не связаны с ними.

Итак, на самом деле, с чего начать исправление?

Очистите свой метод insert, чтобы вы делали шаг за шагом.

1) Вычислить хэш входящего объекта
2) Взгляд вверх хэш на массиве
3) Если местоположение массива имеет нулевое значение, генерировать новый Linked List и вставить значение в массив
3b) Если массив не пуст, создать новый узел списка и указать конечный узел существующего списка к новому узлу
4) Done

код Натаниэля идеально подходит для этого нужно, но если вы вынуждены использовать MyList реализация будет вести себя примерно так:

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; 
} 

Кроме того, ваш printHash метод нуждается в обновлении из-за двух проблем.

1) Ваша логика для увеличения i в том случае, если arr [i] имеет значение null, может привести к выходу за пределы. В случае, когда последний индекс массива равен нулю, вы увеличили бы i, не проверяя его.Вы лучше делать чек, как это и позволяя петлю сделать работу за вас:

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

или сохранить код более чистым (без случайных скачков в потоке программы)

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

2) Без использования first и last больше вы просто перебирать каждый элемент

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

У вас есть тонкое непонимание того, что такое LinkedList, и как он должен работать.

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; 
    } 
} 

Вы можете вызвать этот код следующим образом:

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

Но обратите внимание, что обычно для такого рода вещи метод insert() не будет статичным. Понимание статических элементов и методов очень важно в ООП. Статический член будет одинаковым для всех экземпляров этого класса. Большинство объектов необходимо создать (new SomeObject()); экземпляр объекта имеет свою собственную копию каждого нестатического элемента. Нестатические функции могут быть вызваны только на реализованным объекта: LinkedList.insert (36, arrayOfLists); // вызова статического метода,

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