468,145 Members | 1,407 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,145 developers. It's quick & easy.

How can Implement a perfect hashed data structure using the four basic operations?

74 64KB
How to implement the perfect hashed data structure using the four basic operations (insert, fetch, delete, and update)? Will I have to use a hashtable to do this?

This is my starting pseudocode below:
Expand|Select|Wrap|Line Numbers
  1. public class HashedClass{ 
  2.  
  3. int ticketNumber; // keyfield 
  4. string purchaserName; 
  5.  
  6. Hashtable hashtable = new Hashtable(); 
  7.  
  8. insert(); 
  9.  
  10. fetch();
  11.  
  12. delete(); 
  13.  
  14. update();
  15.  
  16. }
I started a pseudocode above, but I know it needs more work. Are there any resources that can help guide me to implementing my own java hashed perfect algorithm? I know that you have to use the direct hashed four basic operation for each four methods, right? But how can I do that based on pseudocode?

I want my application to store nodes for a stadium ticket application where the ticket numbers range from 2000 to 100,000 for a 60,000 seat stadium. The ticket number will be the key field and the nodes will also store the purchaser's name.
Oct 15 '17 #1
2 4224
Frinavale
9,735 Expert Mod 8TB
Hashing takes the value of something and translates into a fixed-length key that represents the original value.

You need to implement a hashing algorithm that translates the data you have into a a key.

Once you have that algorithm you will need to use it to insert new items into your structure and for determining if an item exists in your structure (if you are fetching, updating, or deleting something and don't already know the hashed key for the item)

That being said, you may also have to come up with an algorithm that resolves conflicts (or raise appropriate errors to state that an item already exists in that position).

The fun of your exercise is really coming up with the hash algorithm and resolution algorithms. There are many ways to do this.

Start researching the Hashing before you begin.
You could even start with reading through the wikipedia entry for Hash function
Oct 17 '17 #2
dseals22
74 64KB
@Frinavale, @chaarmann,

Could I do something like this or do I need to break up my
code into two different classes and then test the methods from the other class inside of another class's main method:
Expand|Select|Wrap|Line Numbers
  1. import java.util.Scanner; 
  2.  
  3. public class StadiumTickets
  4. {
  5.  
  6.      int ticketNumber; // keyfield
  7.  
  8.      String purchaserName; 
  9.  
  10.  
  11.   public void input()
  12.   {
  13.  
  14.      Scanner input= new Scanner(System.in);
  15.  
  16.       // key values ranges between 2000 to 100,000 
  17.  
  18.  
  19.       System.out.print("Please enter a ticket number between 2000 to 100,000: "); 
  20.  
  21.       // a variable to hold the answer
  22.  
  23.        ticketNumber= input.nextInt(); 
  24.  
  25.  
  26.         // error checking to make sure the user doesn't enter a key outside of the lower or upper ranges
  27.  
  28.        if(ticketNumber < 2000 && ticketNumber > 100000) 
  29.         System.out.println("This number is not a valid entry to input into the structure.");
  30.      }
  31.  
  32.   public StadiumTickets(int ticketNumber, String purchaserName)
  33.   {
  34.  
  35.        this.ticketNumber= ticketNumber; 
  36.        this.purchaserName= purchaserName; 
  37.    } 
  38.  
  39.  
  40.  
  41.    public StadiumTickets deepCopy()
  42.    { 
  43.  
  44.       StadiumTickets clone= new StadiumTickets(ticketNumber, purchaserName); 
  45.        return clone; 
  46.    }  
  47. }
  48.  

Expand|Select|Wrap|Line Numbers
  1. public class PerfectHash
  2. {
  3.  
  4.   private StadiumTickets[] data; 
  5.  
  6.  
  7.   public boolean insert(StadiumTickets newStadiumTicket)
  8.   {
  9.       // the direct insert hashed algorithm 
  10.  
  11.        pseudoKey = preProcessing(targetKey); 
  12.        ip = pseudoKey; // direct hashing function 
  13.  
  14.        // insert the new node
  15.         data[ip] = newStadiumTicket.deepCopy(); 
  16.   }
  17.  
  18.   public StadiumTickets fetch(String targetKey)
  19.   {
  20.  
  21.     // the fetch algorithm 
  22.     // access the primary storage area 
  23.  
  24.      pseudoKey = preprocessing(targetKey); 
  25.      ip = pseudoKey; // direct hashing function 
  26.     if(data[ip]== null)
  27.      { return null; 
  28.  
  29.      } 
  30.      else
  31.      {
  32.         return data[ip].deepCopy(); 
  33.      }
  34.    } 
  35.  
  36.    public boolean delete(String targetKey)
  37.    { 
  38.       // the delete direct hashed algorithm 
  39.  
  40.       // access the primary storage area 
  41.          pseudoKey = preprocessing(targetKey); 
  42.        ip = pseudoKey; // direct hashing function 
  43.  
  44.       if(data[ip]== null)
  45.       { 
  46.          return false; 
  47.        } 
  48.       else 
  49.       { 
  50.         data[ip]= null;                      
  51.         return true; 
  52.       }
  53.     } 
  54.     public boolean update(String targetKey, StadiumTickets newStadiumTicket)
  55.     {
  56.         // the update direct hashed algorithm 
  57.  
  58.        if(delete(targetKey) == false)
  59.            return false; 
  60.        else 
  61.         {
  62.            insert(newStadiumTicket) 
  63.              return true;
  64.          }
  65.      }
  66.  
  67. }
Oct 30 '17 #3

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

1 post views Thread by vivek khurana | last post: by
5 posts views Thread by John | last post: by
6 posts views Thread by herrcho | last post: by
3 posts views Thread by Nagaraj | last post: by
16 posts views Thread by ravi | last post: by
3 posts views Thread by btreddy | last post: by
3 posts views Thread by eisman28 | last post: by
1 post views Thread by gcdp | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.