散列搜索程序无尽循环

我的代码在我的散列搜索方法中的第二个while循环中陷入困境。似乎这些条件保持不变，当它们最终会变成假时，如果密钥不在数据集中或者找到了密钥。有人可以帮我找到错误吗？散列搜索程序无尽循环

感谢

////// 这是整个..我一直在努力..仍然无法找出错误。

public void HashedSearch() 
    { 
     HSAverageAccessTime  = 0; 
     HSAverageCompSuc   = 0; 
     HSAverageCompFailed  = 0; 
     HSNumberKeysSuc   = 0; 
     HSNumberKeysFailed  = 0; 

     Initialize(); 

     int SearchKey; 
     int TotalNumberOfComparisons; 
     int address; 
     int M; 
     M = FindPrime(); 


     for(int i=0; i<NumberOfDataItems; i++) 
     { 

      address = OriginalArray[i] % M; 
      if (HashedArray[address]== -1) 
       HashedArray[address]= OriginalArray[i]; 
      else 

      { 
       address = (address+1) % M; 

       while(HashedArray[address]!=-1) 
       { 

        address=(address+1)%M; 

       } 

       HashedArray[address]=OriginalArray[i]; 

      } 

     } 

     System.out.println("after mapping" + M); 
     long startTime = System.nanoTime(); 
     boolean found = false; 

     for (int k = 0; k <NumberOfKeys; k++) 
     { 

      found = false; 
      SearchKey = KeysArray[k]; 
      TotalNumberOfComparisons = 0; 


      address = KeysArray[k] % M;    
      //System.out.println("address" + address); 

       //System.out.println(" inside if 1 --- address" + address); 
      while (HashedArray[address]!= SearchKey && HashedArray[address]!= -1) 
      { 
       if (HashedArray [address] == SearchKey) 
       { 
        found = true; 
        TotalNumberOfComparisons++; 
        HSAverageCompSuc = HSAverageCompSuc + TotalNumberOfComparisons; 
        BSNumberKeysSuC++; 
       } 
       else 
       { 


        System.out.println("Stuck after here"); 
        HSAverageCompFailed = HSAverageCompFailed + TotalNumberOfComparisons; 
        HSNumberKeysFailed ++; 

         //address=(address+1)%M; 
        address++; 
        } 

        System.out.println(" outside while --- found" + found); 

        //if(HashedArray[address] == SearchKey) 
         //found = true; 
        //else found = false; 

        //address=(address+1)%M; 
        //address++; 
       } 

      if(found) 
      { 
       HSAverageCompSuc = HSAverageCompSuc + TotalNumberOfComparisons; 
       BSNumberKeysSuC++; 
      } 
      else 
      { 
       HSAverageCompFailed = HSAverageCompFailed + TotalNumberOfComparisons; 
       HSNumberKeysFailed ++; 
      } 
     } 

     long estimatedTime = System.nanoTime() - startTime; 

     if (NumberOfKeys != 0) 
      HSAverageAccessTime = Math.round((estimatedTime/NumberOfKeys)); 
     else 
      HSAverageAccessTime = 0; 
     if(HSNumberKeysSuc != 0) 
      HSAverageCompSuc  = Math.round (HSAverageCompSuc/HSNumberKeysSuc) ; 
     else 
      HSAverageCompSuc  = 0; 
     if (HSNumberKeysFailed != 0) 
      HSAverageCompFailed  = Math.round (HSAverageCompFailed/HSNumberKeysFailed) ; 
     else 
      HSNumberKeysFailed = 0; 
     System.out.println("time after search" + estimatedTime); 
     return; 
    }

来源

2013-03-13 Lily

M是什么，就不会这样一直循环下去，如果键没有被发现？ – 2013-03-13 21:17:51

您的示例中缺少很多代码。 'HashedArray'，'KeysArray'和'SearchKey'的类型是什么？既然你使用'=='和'！='进行比较，我假设它们是原语，但如果它们不是，那么你应该使用'equals'方法。你能提供一个更完整的例子吗？ – Steinar 2013-03-13 21:33:29

while (HashedArray[address]!= SearchKey && HashedArray[address]!= -1) 
{ 
     address=(address+1)%M; 

}

你的循环永远不会结束。如果你SearchKey或-1不HashedArray。除非您发布完整的代码，否则我无法给您任何澄清。

来源

2013-03-13 22:02:59 Bashir

@Bashir @KevinDiTraglia @Steinar

import javax.swing.*; 
//File-related imports 

import java.io.IOException; 
import java.util.Scanner; 
import java.io.File; 
import java.util.Arrays; 
import java.math.*; 

public class ArrayOperations 
{ 
    // File Parameters 
    String DataFilePath; 
    String DataFileName; 

    String KeysFilePath; 
    String KeysFileName; 

    int NumberOfDataItems; 
    int NumberOfKeys  ; 
    int N    ; 
    int BucketHashArraySize; 
    int NoBuckets; 
    //Array 

    int[] OriginalArray = new int[1000000]; 
    int[] SortedArray = new int[1000000]; 
    int[] HashedArray = new int[2000000]; 
    int[] BucketHashedArray = new int[2000000]; 
    int[] KeysArray = new int[1000000]; 

    long SSAverageAccessTime; 
    long SSAverageCompSuc ; 
    long SSAverageCompFailed; 
    long SSNumberKeysSuc ; 
    long SSNumberKeysFailed ; 

    long BSAverageAccessTime; 
    long BSAverageCompSuc ; 
    long BSAverageCompFailed; 
    long BSNumberKeysSuc ; 
    long BSNumberKeysFailed ; 

    long HSAverageAccessTime; 
    long HSAverageCompSuc ; 
    long HSAverageCompFailed; 
    long HSNumberKeysSuc ; 
    long HSNumberKeysFailed ; 




    public ArrayOperations() 
    { 
     // File Parameters 
     DataFilePath = null; 
     DataFileName = null; 

     KeysFilePath = null; 
     KeysFileName = null; 

     NumberOfDataItems=0; 
     NumberOfKeys  =0; 
     N    =0; 
     BucketHashArraySize = 0; 
     NoBuckets =0; 
     // Statistics 

     SSAverageAccessTime  = 0; 
     SSAverageCompSuc   = 0; 
     SSAverageCompFailed  = 0; 
     SSNumberKeysSuc   = 0; 
     SSNumberKeysFailed  = 0; 




     BSAverageAccessTime  = 0; 
     BSAverageCompSuc   = 0; 
     BSAverageCompFailed  = 0; 
     BSNumberKeysSuc   = 0; 
     BSNumberKeysFailed  = 0; 


     HSAverageAccessTime  = 0; 
     HSAverageCompSuc   = 0; 
     HSAverageCompFailed  = 0; 
     HSNumberKeysSuc   = 0; 
     HSNumberKeysFailed  = 0; 




    } 


    public void ReadDataFile() throws IOException 
    { 
     JFileChooser chooser = new JFileChooser(); 
     chooser.setDialogType(JFileChooser.OPEN_DIALOG); 
     chooser.setDialogTitle("Open Data File"); 

     int returnVal = chooser.showOpenDialog(null); 
     if(returnVal == JFileChooser.APPROVE_OPTION) 
     { 
      DataFilePath = chooser.getSelectedFile().getPath(); 
      DataFileName = chooser.getSelectedFile().getName(); 
     } 

     // read data file and copy it to original array 
     if (DataFilePath != null) 
     { 
      try 
      { 

       int index = 0; 
       Scanner integerTextFile = new Scanner(new File(DataFilePath)); 
       while (integerTextFile.hasNext()) 
       { 
        // read the next integer 
        OriginalArray[index] = integerTextFile.nextInt(); 
        index++; 
       } 
       // end of file detected 
       integerTextFile.close(); 
       NumberOfDataItems = index; 
      } 
      catch (IOException ioe) 
      { 
       System.exit(0); 
      }  

     } 
     else 
      NumberOfDataItems = 0; 
    } 
    public void ReadKeysFile() throws IOException 
    { 
     JFileChooser chooser = new JFileChooser(); 
     chooser.setDialogType(JFileChooser.OPEN_DIALOG); 
     chooser.setDialogTitle("Open Keys File"); 

     int returnVal = chooser.showOpenDialog(null); 
     if(returnVal == JFileChooser.APPROVE_OPTION) 
     { 
      KeysFilePath = chooser.getSelectedFile().getPath(); 
      KeysFileName = chooser.getSelectedFile().getName(); 
     } 
     // read data file and copy it to original array 
     if (KeysFilePath != null) 
     { 
      try 
      { 
       int index = 0; 
       Scanner integerTextFile = new Scanner(new File(KeysFilePath)); 
       while (integerTextFile.hasNext()) 
       { 
        // read the next integer 
        KeysArray[index]= integerTextFile.nextInt(); 
        index++; 
       } 
       // end of file detected 
       integerTextFile.close(); 
       NumberOfKeys = index; 
      } 
      catch (IOException ioe) 
      { 
       System.exit(0); 
      }  

     } 
     else 
      NumberOfKeys = 0; 
    } 
    public void SequentialSearch() 
    { 
     SSAverageAccessTime  = 0; 
     SSAverageCompSuc  = 0; 
     SSAverageCompFailed  = 0; 
     SSNumberKeysSuc   = 0; 
     SSNumberKeysFailed  = 0; 
     int SearchKey; 
     int TotalNumberOfComparisons; 
     long startTime = System.nanoTime(); 
     boolean found = false; 

     for (int k=0; k<NumberOfKeys; k++) 
     { 
      found = false; 
      SearchKey = KeysArray[k]; 
      TotalNumberOfComparisons = 0; 
      for (int d=0; d<NumberOfDataItems; d++) 
      { 
       TotalNumberOfComparisons++; 
       if (SearchKey == OriginalArray[d]) 
       { 
        found = true; 
       } 
       if (found)break; 
      } 
      if(found) 
      { 
       SSAverageCompSuc = SSAverageCompSuc + TotalNumberOfComparisons; 
       SSNumberKeysSuC++; 
      } 
      else 
      { 
       SSAverageCompFailed = SSAverageCompFailed + TotalNumberOfComparisons; 
       SSNumberKeysFailed ++; 
      } 
     } 
     long estimatedTime = System.nanoTime() - startTime; 

     if (NumberOfKeys != 0) 
      SSAverageAccessTime = Math.round((estimatedTime/NumberOfKeys)); 
     else 
      SSAverageAccessTime = 0; 
     if(SSNumberKeysSuc != 0) 
      SSAverageCompSuc  = Math.round (SSAverageCompSuc/SSNumberKeysSuc) ; 
     else 
      SSAverageCompSuc  = 0; 
     if (SSNumberKeysFailed != 0) 
      SSAverageCompFailed  = Math.round (SSAverageCompFailed/SSNumberKeysFailed) ; 
     else 
      SSNumberKeysFailed = 0; 
     return; 
    } 


    public void BinarySearch() 
    { 
     BSAverageAccessTime  = 0 ; 
     BSAverageCompSuc  = 0 ; 
     BSAverageCompFailed  = 0 ; 
     BSNumberKeysSuc   = 0 ; 
     BSNumberKeysFailed  = 0 ; 
     int SearchKey; 
     int TotalNumberOfComparisons; 

     boolean found = false; 

     for (int i=0; i<NumberOfDataItems; i++) 
     { 
      SortedArray[i] = OriginalArray[i]; 
     } 

     Arrays.sort(SortedArray); 

     long startTime = System.nanoTime(); 

     for (int k=0; k<NumberOfKeys; k++) 
     { 
      found = false; 
      SearchKey = KeysArray[k]; 
      TotalNumberOfComparisons = 0; 


      //binary starts 

      int start = 0; 
      int end = SortedArray.length - 1; 
      int middle; 

      while (end >= start) 
      { 
       middle = (start + end)/ 2;      // element in middle of array 


       if (SortedArray[middle] == SearchKey) 

       { 
        TotalNumberOfComparisons++; 
        found = true; 

       } 
       else 
        if (SortedArray[middle] > SearchKey) 
        { TotalNumberOfComparisons++; 
        end = middle - 1; 


        }       // search left side of array 
        else 
        { TotalNumberOfComparisons++; 
        start = middle + 1; }       // search right side of array 

       if (found) 
        break; 
       //binaryends 
      } 

      if(found) 
      { 
       BSAverageCompSuc = BSAverageCompSuc + TotalNumberOfComparisons; 
       BSNumberKeysSuC++; 
      } 
      else 
      { 
       BSAverageCompFailed = BSAverageCompFailed + TotalNumberOfComparisons; 
       BSNumberKeysFailed ++; 
      } 
     } 

     long estimatedTime = System.nanoTime() - startTime; 

     if (NumberOfKeys != 0) 
      BSAverageAccessTime = Math.round((estimatedTime/NumberOfKeys)); 
     else 
      BSAverageAccessTime = 0; 
     if(BSNumberKeysSuc != 0) 
      BSAverageCompSuc  = Math.round (BSAverageCompSuc/BSNumberKeysSuc) ; 
     else 
      BSAverageCompSuc  = 0; 
     if (BSNumberKeysFailed != 0) 
      BSAverageCompFailed  = Math.round (BSAverageCompFailed/BSNumberKeysFailed) ; 
     else 
      BSNumberKeysFailed = 0; 
     return; 
    } 





    public void HashedSearch() 
    { 
     HSAverageAccessTime  = 0; 
     HSAverageCompSuc   = 0; 
     HSAverageCompFailed  = 0; 
     HSNumberKeysSuc   = 0; 
     HSNumberKeysFailed  = 0; 

     Initialize(); 

     int SearchKey; 
     int TotalNumberOfComparisons; 
     int address; 
     int M; 
     M = FindPrime(); 


     for(int i=0; i<NumberOfDataItems; i++) 
     { 

      address = OriginalArray[i] % M; 
      if (HashedArray[address]== -1) 
       HashedArray[address]= OriginalArray[i]; 
      else 

      { 
       address = (address+1) % M; 

       while(HashedArray[address]!=-1) 
       { 

        address=(address+1)%M; 

       } 

       HashedArray[address]=OriginalArray[i]; 

      } 

     } 

     System.out.println("after mapping" + M); 
     long startTime = System.nanoTime(); 
     boolean found = false; 

     for (int k = 0; k <NumberOfKeys; k++) 
     { 

      found = false; 
      SearchKey = KeysArray[k]; 
      TotalNumberOfComparisons = 0; 


      address = KeysArray[k] % M;    
      //System.out.println("address" + address); 

       //System.out.println(" inside if 1 --- address" + address); 
      while (HashedArray[address]!= SearchKey && HashedArray[address]!= -1) 
      { 
       if (HashedArray [address] == SearchKey) 
       { 
        found = true; 
        TotalNumberOfComparisons++; 
        HSAverageCompSuc = HSAverageCompSuc + TotalNumberOfComparisons; 
        BSNumberKeysSuC++; 
       } 
       else 
       { 


        System.out.println("Stuck after here"); 
        HSAverageCompFailed = HSAverageCompFailed + TotalNumberOfComparisons; 
        HSNumberKeysFailed ++; 

         //address=(address+1)%M; 
        address++; 
        } 

        System.out.println(" outside while --- found" + found); 

        //if(HashedArray[address] == SearchKey) 
         //found = true; 
        //else found = false; 

        //address=(address+1)%M; 
        //address++; 
       } 

      if(found) 
      { 
       HSAverageCompSuc = HSAverageCompSuc + TotalNumberOfComparisons; 
       BSNumberKeysSuC++; 
      } 
      else 
      { 
       HSAverageCompFailed = HSAverageCompFailed + TotalNumberOfComparisons; 
       HSNumberKeysFailed ++; 
      } 
     } 

     long estimatedTime = System.nanoTime() - startTime; 

     if (NumberOfKeys != 0) 
      HSAverageAccessTime = Math.round((estimatedTime/NumberOfKeys)); 
     else 
      HSAverageAccessTime = 0; 
     if(HSNumberKeysSuc != 0) 
      HSAverageCompSuc  = Math.round (HSAverageCompSuc/HSNumberKeysSuc) ; 
     else 
      HSAverageCompSuc  = 0; 
     if (HSNumberKeysFailed != 0) 
      HSAverageCompFailed  = Math.round (HSAverageCompFailed/HSNumberKeysFailed) ; 
     else 
      HSNumberKeysFailed = 0; 
     System.out.println("time after search" + estimatedTime); 
     return; 
    } 



    public int FindPrime() 
    { 
     boolean prime = true; 

     for(int i=NumberOfDataItems * 2-1; i>=0; i--) 
     { 
      System.out.println(" i = " +i); 

      prime = true; 
      for(int J =2; J< Math.sqrt(i); J++) 
      { 
       if (i % J == 0) 
       { 
        prime = false; 

       } 
       if (prime == false) break; 
      } 
      if (prime == true) 
      { 
       System.out.println(i); 
       return i; 
      } 
     } 
     return -1; 
    } 

    public void Initialize() 
    { 

     for (int i=0; i<NumberOfDataItems; i++) 
     { 
      HashedArray[i] = -1; 
     } 

    } 
    public void BHSearch() 
    { 


    } 

}

来源

2013-03-14 06:27:46 Lily

散列搜索程序无尽循环

回答

相关问题