hashing and using an external file

[rhaylee]

My professor gave us an assignment that I am not entirely sure how to start correctly. She gave us 2 java classes as well to use. Any assistance would be greatly appreciated...

So basically, two things need to be done. I need to create two more classes, ExternalHashing and IndexHashTable...and I have some work so far but I am not sure how to edit it to make it work for this assignment.

I already have some of it...but I had done a previous assignment and used basically that, but I am not sure how to edit it to make it work here.

I also for whatever reason, am unable to post the source code on here and I am not sure why.

Problem to be solved:
Simulate the external hashing structure for a department to store the students’ information by using Java RandomAccessFile class.
Assumptions:
The data structure is implemented by an in-memory hash table and an external file. Assume the file consists of n disc blocks and each block contains r records maximally.
The number of total records is not more than (n * r ) / 2. (The load factor is ½)
Each record is defined as follow:
It consists of one string name and one string id. The id is a key which uniquely represents a record. The mapping integer of an id is in the range of 1 to 200. (the digits given to an id is 4 for extending purpose)
The read operation reads the record from a file
The write operation writes the record into the file
Each element of the in-memory hash table contains an index of a block in the external file. See fig. 11.15 in p. 572.
Once the external block is identified, use the linear probing to find the location for the record (for all operations) in the external blocks. The linear probing here means a sequential search record by record within a block.

Detail guides:
1. Implement an Index Hash Table by a class named IndexHashTable. Each element of the table contains a block number in the range of 0 to n-1. Each block number is an index of the block in the external file. For example, if one block size is 300 bytes and the index is 6, the offset for the block 6 should be 6*300=1800 byte in the file. In another word, the block 6 starts from 1800 byte and ends at 2099 byte in the file.
2. To simulate the randomly distributed block numbers in the hash table, the block number in each cell of the hash table should be a random number. The range of the random numbers is 0 to n-1. The block numbers should be unique in the table. The hash table should be created in the constructor of the IndexHashTable class.
3. The operations in the hash table are insert, delete, and search. You may define a noData record to help for clearing the storage or representing the deleted elements in the external file.
Here is an algorithm for the operation “Insert”:
The possible steps for insert
1) For a given record (input by user), use the id of the record to be the original key. Note that the key is an integer converted from the string id.
2) Apply the hash function (p.536) to the key to obtain an index of the in-memory Index Hash Table.
3) Use the index to retrieve the block index in the table.
4) Calculate the start address of the block in the file: block-index * blockSize. The blockSize is recSize * r.
5) Use the address obtained in 4) to locate the position of the block in the file (use the seek() method showing in RandomFile.java, the sample code given by the instructor.)
6) Use the linear probe approach to insert the record in the block.
During the probing, make sure that there is no redundant key found (no key maps the key of the record for inserting). If find redundancy, stop insertion.
If the number of probes reaches r and the available space is not found in the block, the operation fails and stop (the block is full. This situation indicates that the hash function itself has a poor performance.)
The signature of the insert method is:

   public int  insert (RandomAccessFile file, Record rec)
   It returns 0 for successful, -1 for block full and 1 for redundancy

Start from step 5), the operations of the random access file will be involved.
The students should figure out the algorithms for delete and search.
4. The classes provided by instructor:
1) Record class
This class defines a record required in the problem, includes methods to write the record into a specified random access file and read a record from the file.
Class field:
name – It is String type and limited to 16 chars
id – It is String type and limited to 4 chars

[Note: Each char in Unicode is two bytes. When you search in the object of RandomAccessFile in which the operations are in bytes, counting offset for each record should double the size of the chars in a record. In another word, a record consists of 20 chars which are 40 bytes.]

Constructor: 
public record (String name, String id) – 
create a new record
        Public Methods:
    public void read (RandomAccessFile file) – 
to retrieve the name and id from the file at the current file pointer position
    public void write (RandomAccessFile file) – 
to write name and id in the file at the current position
        public String getId( ) –
            to return the id of a record
        public String getName( ) –
            to return the name in a record
        public String toString( ) – to display the name and id in the record

2) RandomFile class
This is a demo program. It shows how to create a random access file which works as an external disk file, how to use the write and read operations defined in Record class, how to locate a block by seek() in the file, and how to close the file. It is an application class containing main(). You can use it as the base skeleton of your application class.
5. Write an application class named ExternalHashing to supply a menu for users to use the hash table to store the records. The menu should include the Insert, Remove, Search and Quit operations. You should also display a title to this system.
6. Your program should be general to accept any values for n and r. You may test your program by using n = 5 (the size of the in-memory hash table and also the number of blocks in the file) and r = 7 (the maximum number of records in a block)
7. The following classes should be included in your submission (in one zip file):
Record.java – represents one record (from the constructor)
IndexHashTable.java – represents the hash table including the operations of insert, search and delete
ExternalHashing.java – the client class displaying the menu to the user and do all user interactions
8. Write a good documentation to your program.

[rhaylee]

/* [Prepared by the instructor]
 * Record class
This class defines a record which is specifically for storing in
a Java random access file. See API of RandomAccessFile class in Java.

Attributes:
    name - String, the max length is 16 chars
    id - String, the number of digits in id is 4.
 *
*/

import java.util.*;
import java.io.*;

public class Record
{
    private String name;
    private String id;
    private int NAMELENGTH=16;
    private int IDLENGTH=4;

//Constructors
    public Record()
    {
        name = " ";
        id = " ";
    }

    public Record(String newName, String newId)
    {
        name = newName;
        id = newId;
    }

//Read and write methods
    //Read a 'name' and the related 'id' from the current position of
    //the given file
    public void read(RandomAccessFile file) throws IOException
    {
        name = readString(file, NAMELENGTH);
        id = readString(file, IDLENGTH);
    }

    //Write the value of 'this' object to the given file
    public void write(RandomAccessFile file) throws IOException
    {
        writeStr(file, name, NAMELENGTH);
        writeStr(file, id, IDLENGTH);
    }

//get methods
    public String getId()
    {
        return id;
    }

    public String getName()
    {
        return name;
    }

//readString and Writestr methods
    //Help method: read a string with length of strLength from the file
    //             Return the string to the caller
    private String readString (RandomAccessFile file, int strLength) throws IOException
    {
        char[] chs = new char[strLength];

        for (int i = 0; i < chs.length; i++)
        {
            chs[i] = file.readChar();
        }

        String theStr = new String(chs);

        return theStr;
    }

    //Help method: write a string with length of strLength to the file
    private void writeStr( RandomAccessFile file, String str, int strLength ) throws IOException
    {
        StringBuffer buffer = null;

        if ( str != null )
            buffer = new StringBuffer( str );
        else
            buffer = new StringBuffer( strLength );

        buffer.setLength( strLength );
        file.writeChars( buffer.toString() );

    } // end method writeName

//toString method
    public String toString()
    {
        return "\nName: " + name + "\nID: " + id;
    }
}

/* [Prepared by the instructor]
 This is a demo program to show the following operations of a random access file
 1) Creates a random-access file
 2) write one record to the file
 3) read one record from the file
*/

import java.io.*;
import java.io.RandomAccessFile;

public class RandomFile
{
    public static void main( String args[] )
    {

        Record rec = new Record("  ", "  ");
        Record rec1 = new Record();
        RandomAccessFile f = null;

        try
        {
            f = new RandomAccessFile("newfile.txt", "rw");
            f.seek(0);
            rec.write(f);
        }
        catch (IOException e)
        {
            System.out.println("Cannot Write\n" + e);
        }

        try
        {
            if (f != null)
            {
                f.seek(0);
                rec1.read(f);
                f.close();
            }
        }
        catch (EOFException ee)
        {
            System.out.println("End of File");
        }
        catch (IOException e)
        {
            System.out.println("Cannot Read\n" + e);
        }

        System.out.println(rec1);
    } // end main
} // end class RandomFile

This is what she gave us

[rhaylee]

/*
IndexHasTable.java
*/

import java.io.*;
import java.util.*;

public class IndexHashTable
{
    private int[] hashTable;
    private int sizeOfBlock;
    private int recsInBlock;
    private int lengthOfBlock;
    private int randomNumber = 0;

    private int[] blockCount;
    private final Record DELETED_RECORD = new Record("D", "-1");

    public IndexHashTable(int numberOfBlocks, int numRecordsPerBlock)
    {
        hashTable = new int[numberOfBlocks];
        populateHashTable();

        recsInBlock = numRecordsPerBlock;
        lengthOfBlock = 40 * recsInBlock;
        blockCount= new int[hashTable.length];
    }

    public int hashFunc(int key)
    {
        return key % hashTable.length;
    }

    public int insert(RandomAccessFile file, Record rec)
    {
            int recordId = Integer.parseInt(rec.getId());
            int hashedId = hashFunc(recordId);
            int hashedIndex = hashTable[hashedId];

            if(blockCount[hashedIndex] < recsInBlock)
            {
                try
                {
                    Record fileReader = new Record();

                    file.seek(hashedIndex * lengthOfBlock);

                    for(int i = 0; i < recsInBlock; i++)
                    {
                            fileReader.read(file);

                            if(fileReader.getId().equals("    ") || fileReader.getId().equals(DELETED_RECORD.getId( )))
                            {
                                    file.seek(file.getFilePointer() - 40);

                                    rec.write(file);

                                    blockCount[hashedIndex]++;

                                    return 0;
                            }
                            else if(fileReader.getId().equals(rec.getId()))

                                return 1;
                    }
                }
                catch(IOException ioe)
                {
                    return -2;
                }
            }
            return -1;
        }

    public boolean search(RandomAccessFile file, String id)
    {

        int recordId = Integer.parseInt(id);
        int hashedId = hashFunc(recordId);
        int hashedIndex = hashTable[hashedId];

        if(blockCount[hashedIndex] != 0)
        {
            try
            {

                Record fileReader = new Record();

                file.seek(hashedIndex * lengthOfBlock);

                for(int i = 0; i < recsInBlock; i++)
                {
                    fileReader.read(file);

                    if(fileReader.getId().equals(id))
                            return true;
                }
            }

            catch(Exception e)
            {

            }
        }
        return false;
    }

    public boolean delete(RandomAccessFile file, String id)
    {

            int recordId = Integer.parseInt(id);
            int hashedId = hashFunc(recordId);
            int hashedIndex = hashTable[hashedId];

            Record fileReader = new Record();
            Record deletedRecord;

            try
            {
                file.seek(hashedIndex * lengthOfBlock);

                for(int i = 0; i < recsInBlock; i++)
                {
                        fileReader.read(file);

                        if(fileReader.getId().equals(id))
                        {
                                deletedRecord = fileReader;
                                file.seek(file.getFilePointer() - 40);
                                DELETED_RECORD.write(file);
                                blockCount[hashedIndex]--;
                                return true;
                        }
                }
            }
            catch(Exception e)
            {

            }

            return false;
    }


    private void populateHashTable()
    {
            Random random = new Random();
            int randomNumber;

            for(int i = 0; i < hashTable.length; i++)
            {
                    boolean numberAlreadyEntered = true;

                    while(numberAlreadyEntered)
                    {
                        numberAlreadyEntered = false;

                        randomNumber = random.nextInt(hashTable.length);

                        for(int j = 0; j < i && !numberAlreadyEntered; j++)
                        {
                            if(hashTable[j] == randomNumber)
                            {
                                numberAlreadyEntered = true;
                            }
                        }
                    }

            hashTable[i] = randomNumber;
            }
    }
}
/*
ExternalHashing.java
*/
import java.util.InputMismatchException;
import java.util.*;

public class ExternalHashing
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);

        IndexHashTable iData = new IndexHashTable();


        String listOfCommands = "Enter number to run command:"
                + " 0: terminates program"
                + " 1: displays commands"
                + " 2: adds a new record"
                + " 3: removes a record"
                + " 4: searches for a record";


        boolean userWouldLikeToContinue = true;
                while(userWouldLikeToContinue)
                {
                    System.out.println(listOfCommands);


                    boolean userStillWorking = true;
                    while(userStillWorking)
                    {
                        System.out.print("Enter a new command: ");

                        try
                        {
                            int in = input.nextInt();
                            input.nextLine();//flushes the scanner buffer
                            switch(in)
                            {

                                case 0:
                                        userStillWorking = false;
                                        userWouldLikeToContinue = false;
                                        break;

                                //displays list of commands
                                case 1:
                                        System.out.println(listOfCommands);
                                        break;


                                case 2:
                                        String name = "";
                                        int id = 0;
                                        boolean nameNotEntered = true;
                                        while(nameNotEntered)
                                        {
                                            try
                                            {
                                                System.out.print("Enter student's name: ");
                                                name = input.nextLine();
                                                nameNotEntered = false;
                                            }
                                            catch(Exception e)
                                            {
                                                System.out.println(" Name was invalid. Please enter a valid name.");
                                                input.next();
                                            }
                                        }

                                        boolean idNotEntered = true;
                                        while(idNotEntered)
                                        {
                                            try
                                            {

                                                System.out.println("Enter student's id:");
                                                id = input.nextInt();
                                                idNotEntered = false;
                                            }
                                            catch(Exception e)
                                            {
                                                System.out.println(" Id was invalid. Please enter a valid id.");
                                                input.next();
                                            }
                                        }
                                        System.out.println("Record added to table.");
                                        iData.add(new Record(name,id));

                                    break;

                                //removes student
                                case 3:

                                        if(!iData.isEmpty())
                                        {
                                            System.out.print("Enter id of student you want to remove: ");
                                            System.out.print("\n"+ iData.remove(input.nextInt()).iData.toString() + "\n\n...was removed from the list.");
                                        }
                                        else
                                            System.out.println("The Table is empty.");

                                        break;

                                //searches for a student
                                case 4:
                                        if(!iData.isEmpty())
                                        {
                                            System.out.println("Enter id of the student you want to find: ");
                                            Record searchResults = iData.search(input.nextInt());

                                            if(searchResults != null)
                                                System.out.print(searchResults.iData.toString());
                                            else
                                                System.out.print("The id was not found in the list.");
                                        }
                                        else
                                            System.out.println("The List is empty.");
                                        break;

                                //Displays elements in the list
                                case 5:
                                        if(!iData.isEmpty())
                                            System.out.println(iData.toString());
                                        else
                                            System.out.println("List is empty.");
                                        break;

                                //invalid command entered not part of command list
                                default:
                                        System.out.println(" An invalid command was entered. Please enter a valid command.");
                                        break;
                            }
                        }
                        catch(InputMismatchException ime)
                        {
                            System.out.println(" An invalid command was entered. Please try again.");
                            input.next();
                        }
                    }
                }
                System.out.println("End of Program.");
            }
}

And this is what I have

[JamesCherrill]

Nobody has the time to read all that and try to understand what it is you need. Please ask specific questions, backup up by details of what you have already done youself to try to answer them.