0

我的代码卡在哈希搜索方法的第二个 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; 
    }
4

2 回答 2

0

@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-14T06:27:46.250 回答
0 
while ( HashedArray[address]!= SearchKey && HashedArray[address]!= -1)
{
        address=(address+1)%M; 

}

如果您的SearchKey或-1不在HashedArray中，则您的循环永远不会终止。除非您发布完整的代码，否则我无法为您提供更多说明。

于 2013-03-13T22:02:59.567 回答