Solved

Understanding Java's Hashtable: how does it work when the keys are primitive types that hold a relationship to the values being stored?

Posted on 2003-10-23
11
930 Views
Last Modified: 2012-05-04
In the java implementation of Hashtable, why is the key an object and not a hashcode (hashcode being a primitive type int)?  Furthermore, in Hashtable's comments it states:

* To successfully store and retrieve objects from a hashtable, the
 * objects used as keys must implement the <code>hashCode</code>
 * method and the <code>equals</code> method. <p>

How does this apply when the key is assumed to be an int ?  Can one assume that for a key, of primitive type int, that hashcode and equals methods need "not" be implemented?  

Is not a non-java specific Hashtable normally assumed to take a key that is the hashcode of the related value to be stored/retrieved?  

In my case I want the hashcode to hold a relationship to the value being stored/retireved (i.e. a checksum).    



0
Comment
Question by:Taurus
11 Comments
 
LVL 86

Expert Comment

by:CEHJ
ID: 9610317
Java simply implements its keys as objects. You simply need to override hashCode of the key object to return the checksum and equals to return true if same checksum.
0
 
LVL 3

Expert Comment

by:savalou
ID: 9610442
In reply to your question of "why not hashcode as key", how would you differentiate between two objects whose hashcodes were equal?  Hashtable does internally use hashcodes, but if two keys have the same hashcode then it can still retrieve the object and do a deeper comparison.  
0
 

Author Comment

by:Taurus
ID: 9611041
CEHJ,

I don't think what you suggest will work.   I may in rare circumstances have tables that produce identical checksums.  Savalou seems to alude to this but I don't think he comment is 100% correct either.

Given the method from Java's Hashtable source:

  public synchronized Object get(Object key) {
      Entry tab[] = table;
      int hash = key.hashCode();
      int index = (hash & 0x7FFFFFFF) % tab.length;
      for (Entry e = tab[index] ; e != null ; e = e.next) {
          if ((e.hash == hash) && e.key.equals(key)) {
            return e.value;
          }
      }
      return null;
    }

The deep comparison, if I read this correctly, is performed on the key, if the hashcodes (ints) are found equivalent.  The Hashtable authors seem to make a presumption that the keys will always be unique.   I'm making the case that my tables must be unique but my hashcodes (checksums) may not always be.  

My keys are to be equivalent to the hashcode which is in turn equivalent to the checksum of the "value object" (table).  The reason for this is that my tables are a shared resource that is to be stored both in a Persistant Object Store on disk and in memory.  I do not want duplicate tables.



0
 

Author Comment

by:Taurus
ID: 9611056
I hope the above comment is clear, enough.  I wrote it in a hurry as it was the second try.  I spent more time on the first try and then submitted it only to have the server cough and lose it.
0
 

Author Comment

by:Taurus
ID: 9611357
Per the requirements already expressed above, here are two classes that I'd request comments about:


public class key {

value Value; //the Value object stored in Hashtable (in my case Value objects hold a table)
int checksum; //checksum of Value object's data

public boolean equals(Object obj) {
    if(this == obj){ return true; } //returns true if references are to same object (identity)
 
    if( (obj != null)  && (obj instanceof key) ){
         if( checksum != ((key)obj).checksum )  { return false; }  
         else return Value.equals(obj.Value); // checksums are equivalent but are tables?  
     }
 
  }

}




public class value {

int [] aTable;

...

public boolean equals(Object obj) {
    if(this == obj){ return true; } //returns true if references are to same object (identity)
 
    if( (obj != null)  && (obj instanceof value) ){
        return java.util.Arrays.equals(aTable,((value)obj).aTable);
      }
    else return false;

     }
 
  }
0
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 86

Accepted Solution

by:
CEHJ earned 100 total points
ID: 9613437
If all you're worried about is a checksum collision for two different tables, then all you need to do is the following in your equals method (after your other tests)

if ((this.checksum ==((key)obj).checksum)
&& ((key)obj).value.equals(this.value))
  return true;

Then checksum collisions will not matter if 'value' is different. If 'value' *is* equal then of course checksums should be equal and equals returns true as expected.
0
 

Author Comment

by:Taurus
ID: 9638482
CEHJ,

I think what I had earlier, with a minor correction, was basically what you are suggesting.  Although I believe your code is slightly easier to read.  I've included both below for reference.   Per your version, I assume that the if statement is evaluated left to right and will continue when the condition "this.checksum ==((key)obj).checksum" is false and before the "((key)obj).Value.equals(this.Value))" is evaluated???  


Another question I have is: Do you know if the contract for the Hashcode class make any presumptions that two objects used as keys, but containing different data, are not to have the same hashcode?  I have a book on Java (Learning Java pg. 174) that states "the hashcode should always be different for instances of the class that contain different data..."  However the contract for hashcode() states otherwise.

//CEHJ version
public boolean equals(Object obj) {
    if(this == obj){ return true; } //returns true if references are to same object (identity)
 
    if( (obj != null)  && (obj instanceof key) ){
         if ((this.checksum ==((key)obj).checksum)
            && ((key)obj).Value.equals(this.Value))
            return true;
        //if ((this.checksum ==((key)obj).checksum))
         //   return true;
     }
    return false;
 
  }

 //My version
public boolean equals(Object obj) {
    if(this == obj){ return true; } //returns true if references are to same object (identity)
 
    if( (obj != null)  && (obj instanceof key) ){
         if( checksum != ((key)obj).checksum )  { return false; }  
         else return Value.equals( ((key)obj).Value ); // checksums are equivalent but are tables?  
     }
    return false;
 
  }

}

0
 

Author Comment

by:Taurus
ID: 9653642
CEHJ,

I'm just waiting for any last comment before I accept your comment as an answer and close this.
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 9653743
Your code is equivalent to mine although I think mine gets over the fact that you require both the checksums and the significant object fields to be equal

>>However the contract for hashcode() states otherwise.

Not quite sure what you're getting at there...

0
 

Author Comment

by:Taurus
ID: 9654725
I'm not sure what you mean by "significant object fields"?  These two functions look to me to be identical.  They both return false immediately if checksums are not equal and go on to compare values if they are equal.

Per the contract for hashcode it states:

"It is not required that if two objects are unequal
according to the {@link java.lang.Object#equals(java.lang.Object)}
method, then calling the <tt>hashCode</tt> method on each of the
two objects must produce distinct integer results.  However, the
programmer should be aware that producing distinct integer results
for unequal objects may improve the performance of hashtables."

The book mentioned says that if the objects are unequal they must produce unequal hashcodes.  The contract says they don't have to be.  That's all.  

What I'm doing seems a little out of the ordinary, in that my key's equals() method calls value's equals(),  so I ran some tests to try and understand better Java hashtable's behaviour (without having to put my mind around all the HT source).  Here are cases & conclusions:


Case 1:  Attempt to store multiple, unequivalent value objects, wherein these objects ARE distinct objects, using keys which too are distinct objects but have equivalent HCs.  

Result: since key's equals() calls value's equals(), multiple value objects are stored at one time & retrieved using the same HC for each.

Case 2: Attempt to store multiple, unequivalent value objects, wherein these value objects ARE NOT distinct objects (but their data is changed each time they are stored), using (as in case1) keys which are distinct but have equivalent Key HCs.

Result: value is stored and overwritten, so only 1 value can be stored/retrieved.  


Case 3: Attempt to store multiple unequivalent but distinct value objects but use only 1 key (unequivalent because values referenced are unequivalent but still with equiv. HCs)

Result: value is stored and overwritten, so only 1 value can be stored/retrieved.  Same as 2


CEHJ, I think there is a subtle distinction between these cases of inserting into the HT, distinct value objects, each holding non equiv. data or inserting the same object multiple times, but changing it's data each time (and assuming that for whatever reason the HC remains unchanged) .  I am interested in the results obtained from Case 1 as the result is that Hashtable is performing more or less, I guess similar to multimap or multiset.  I don't know if I've described this clearly enough, but I'm am just wanting to understand the implications of designing the key class's equals() the way I have, and avoid subtle bugs.  Here is the source code for the test cases which may make more sense:

/* case 1:
                tHashTable tHash = new tHashTable();
               
                //create 3 unequivalent but distinct value objects
                value value1 = new value(new int[] {1,2,3,4});      
                value value2 = new value(new int[] {1,2,3,5});
                value value3 = new value(new int[] {1,2,3,6});
               
                //create 3 distinct keys, unequivalent because values referenced are unequivalent, but keys have same HC
                key key1 = new key(value1,10);
                key key2 = new key(value2,10);
                key key3 = new key(value3,10);
               
                //store values in HT
                tHash.addObject(key1, value1);
                tHash.addObject(key2, value2);
                tHash.addObject(key3, value3);
               
               
                int numberofvalues = tHash.getNumofValues();
               
                 //when ran numberofvalues = 3;
           
  //case 2:
                tHashTable tHash = new tHashTable();

                //create 3 distinct keys, with same value object, "Value", holding unequivalent data (data that is changed)
                //and store in HT.  Note: keys have same HC
               
                value Value = new value(new int[] {1,2,3,4});      
                key key1 = new key(Value,10);
                tHash.addObject(key1, Value);
               
                Value.aTable[3]=5;
                key key2 = new key(Value,10);
                tHash.addObject(key2, Value);
               
                Value.aTable[3]=6;
                key key3 = new key(Value,10);
                tHash.addObject(key3, Value);
               
               
                int numberofvalues = tHash.getNumofValues();
               
                 //when ran numberofvalues = 1;
               
               
//case3:
                tHashTable tHash = new tHashTable();
               
                //create 3 unequivalent but distinct value objects
                value value1 = new value(new int[] {1,2,3,4});      
                value value2 = new value(new int[] {1,2,3,5});
                value value3 = new value(new int[] {1,2,3,6});
               
                //create only 1 key, unequivalent because values referenced are unequivalent
                key Key = new key(value1,10);
                tHash.addObject(Key, value1);
               
                Key.Value = value2;
                tHash.addObject(Key, value2);
               
                Key.Value = value3;
                tHash.addObject(Key, value3);
               
                int numberofvalues = tHash.getNumofValues();
               
                 //when ran numberofvalues = 1;




0
 
LVL 92

Expert Comment

by:objects
ID: 10215238
No comment has been added lately, so it's time to clean up this TA.
I will leave a recommendation in the Cleanup topic area that this question is:

Accept CEHJ's comment as answer

Please leave any comments here within the next seven days.

PLEASE DO NOT ACCEPT THIS COMMENT AS AN ANSWER!

objects
EE Cleanup Volunteer
0

Featured Post

Highfive Gives IT Their Time Back

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…

746 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now