0

我正在做一个分配，其中整数被输入到应用程序中，整数被散列，然后放入一个数组中。数组中的每个位置都是我编写的链接列表。我的问题是我似乎无法指定整数应该在数组中的哪个位置。目前，我的输出是数组中每个位置的最后五个整数，除了位置 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 行开始的 else 语句。我没有分配哪个链表来使新整数成为其中的一部分。有没有正确的写法，

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

我在 if 和 else 语句中都添加了 print 语句，并且我都在使用它们。谢谢你。

输出

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
索引 [7] 的项目：619 655 703
索引 [8] 的项目]：56
索引 [9] 的项目：345
索引 [10]
的项目：索引 [11] 的项目：23 47

每个整数在经过哈希处理后放置在适当位置的数组列表中。

4

2 回答 2

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()方法不会是静态的。了解静态成员和方法在 OOP 中非常重要。该类的所有实例的静态成员都是相同的。大多数对象必须被实例化（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
于 2013-04-10T18:20:56.013 回答
2

免责声明：我咆哮了一下。我只是想把所有相关的东西都记下来。如果您只对解决方案感兴趣，请向下滚动到我加粗标题的位置...

从一开始，就像 Nathaniel Ford 提到的那样，我相信您对 HashTable 实现的工作原理存在概念上的误解。让我们从分解逻辑开始。

HashTable 是一种结构，用于通过计算所存储对象的唯一（或几乎唯一）散列来存储和快速检索对象。当您计算这种单向哈希并使用它在表中存储对象时，您允许在理想情况下进行 O(1) 查找。

在一个完美的世界中，所有输入都会唯一地散列并且永远不会发生冲突，但我们知道这是不切实际的。因此，当您拥有多个对象时，您需要有一个集合，允许您将多个对象存储到同一个哈希值；一个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) 如果数组位置为空，则生成一个新的链表并将值插入数组
3b) 如果数组不为空，则为列表并将现有列表的最后一个节点指向新节点
4) 完成

Nathaniel 的代码非常适合这种需求，但如果您被迫使用该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) 如果 arr[i] 为 null，您增加的逻辑i可能会导致您超出范围。在数组的最后一个索引为 null 的情况下，您将i在不检查它的情况下增加。您最好进行这样的检查并让循环为您完成工作：

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

或保持代码更干净（程序流程中没有随机跳转）

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

2）不再使用firstand 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 + " ");
    }
  }
}
于 2013-04-10T19:14:31.737 回答