java - 实现自己的哈希集

Question

我正在研究 Java 中的哈希集，为此我正在编写创建我自己的哈希集，每次达到阈值时它的大小都会加倍。在这里我将阈值保持为原始大小的 0.75。但是我的代码陷入了无限循环。我尝试调试它但无法找到我的错误...

这是代码

package drafta;

import java.util.Iterator;
import java.util.NoSuchElementException;


public class HashSet
{
private Node[] buckets;
private int currentSize;
private int current;

public HashSet(int bucketsLength)
{
 buckets=new Node[bucketsLength];
 currentSize=0;
}

 public boolean contains(Object x)
{
return false;
  // don't implement for the draft
}


 public boolean add(Object x)
 {
  int key=gethashcode(x);
  Node node = buckets[key];
  while(node!=null){
      if(node.data.equals(x)){
          return false;
      }

  }

  if(buckets[current]==null){
  node = new Node(x);
  current=key;
  buckets[key]=node;
  currentSize++;
  }else{
      node = new Node(x);
      node.next=buckets[current];
      current=key;
      buckets[key]=node;
      currentSize++;
  }
  System.out.println("add successful "+ x);
  System.out.println(" size "+currentSize+" rehash "+buckets.length*0.75);

  if(currentSize>(buckets.length*0.75)){
     rehash();
  }
  return true;
 }

private void rehash() {
   Node temp=buckets[current];
   Object s[]=new Object[buckets.length];
   buckets=new Node[2*buckets.length];
currentSize=0;
int i=0;
while(temp!=null){
    s[i]=temp.data;
    temp=temp.next;
    i++;
}
while(i>0){

    add(s[--i]);

}
}


public boolean remove(Object x)
{
return false;
  // don't implement for draft
}

public int gethashcode(Object x){
   int hc = x.hashCode();
   if(hc<0)
       hc=-hc;
   return (hc%buckets.length);
  } 

public Iterator<Object> iterator()
{
   Iterator <Object> i=new HashSetIterator();
return i;
//
 }

 public int size()
 {
return currentSize;
  //
 }

 private void resize(int newLength)
 {
    }

  public int getlength()
 {
return buckets.length;
  //
  }


 class Node
{

    public Object data;
    public Node next;
    public Node(Object x) {
        data=x;
    }
    public String toString(){
        return data.toString();
    }
}

  class HashSetIterator implements Iterator<Object>
 {
  private int bucket=0;
  private Node currentnode;

   public HashSetIterator()
   {
    currentnode=buckets[current];
  }

  public boolean hasNext()
  {
    if(currentnode.next!=null)
        return true;
    else 
        return false;
     //
  }

  public Object next()
  {
    return currentnode.next;
     //
  }

@Override
public void remove() {
    currentnode.next=currentnode.next.next;

}



   }
}

这是我用来测试代码的主类

package drafta;

import java.util.Iterator;

public class HashSetTester
{
public static void main(String[] args)
{
  HashSet names = new HashSet(5);

  names.add("Harry");
  names.add("Sue");
  names.add("Nina");

  System.out.println(names.size() + " " + names.getlength());


  names.add("Susannah");
  System.out.println(names.size() + " " + names.getlength());



  System.out.println();
  names.add("Larry");
  names.add("Juliet");
  names.add("Katherine");
  names.add("Romeo");
  names.add("Maria");


  System.out.println(names.size() + " " + names.getlength());

  names.add("Ann");
  names.add("Taylor");
  System.out.println(names.size() + " " + names.getlength());




}
}

有人可以指出我的错误吗..代码在第二次调用 rehash 时进入无限循环..第一次正确通过...

Answer 1

您没有在 add 方法中更改 while 循环中的任何条件 - 因此它没有理由中断。

while(node!=null){
      if(node.data.equals(x)){
          return false;
      }
  }

您将继续循环，直到节点为空(永远不会被设置)或节点数据永远等于 x，但数据值也永远不会被设置。