实现自己的哈希集

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时，它将进入infinite循环。。第一次它正确通过。。。

Answer 1

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

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

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