In this edition of the JavaRanch Journal SCJP Tipline, author Corey McGlone investigates hashCodes, expanding on an April blog entry.

What is a hashCode?

First of all, what the heck are hashcodes for? Well, oddly enough, they're used heavily in Hashtables. Hashtables, along with the other classes that extend the Map interface, are discussed in this Journal article For the purposes of this article, I'm going to assume you know what a Hashtable is and how useful it can be. Needless to say, Hashtables can help you keep a large number of objects organized and allow you to access them very quickly. Of course, to do so, a Hashtable relies on the power of the hashCode method.

In essence, when you invoke the get(Object o) method of a Hashtable, the Hashtable will use the hashCode method of the object you passed to it in order to access an object (or list of objects). As long as the hashCode method is working properly, everything works just fine. If it doesn't, however, you can have some rather serious problems.

So, what makes a valid hashCode? Well, here's what is said about hashCodes in the API Specification for Object:

The general contract of hashCode is:

1. Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
2. If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
3. It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode 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.

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

Study: A Proper hashCode

Let's start by looking at a good program. In this case, we've defined a new object, MyObject, which defines its own equals and hashCode methods. In general, it is good practice to define your own hashCode method any time you override equals (more about this later). Here it is:

import java.util.Hashtable;
import java.util.Date;

public class MyObject
{
    int a;
    
    public MyObject(int val)
    {
        a = val;
    }
    
    public boolean equals(Object o)
    {
        boolean isEqual = false;
        
        if ( o instanceof MyObject )
        {
            if ( ((MyObject)o).a == a )
            {
                isEqual = true;
            }
        }
        
        return isEqual;
    }
    
    public int hashCode()
    {
        return a;
    }
    
    public static void main(String[] args)
    {
        Hashtable h = new Hashtable();
        
        MyObject[] keys = 
        {
            new MyObject(11),
            new MyObject(12),
            new MyObject(13),
            new MyObject(14),
            new MyObject(15),
            new MyObject(16),
            new MyObject(17),
            new MyObject(18),
            new MyObject(19),
            new MyObject(110)
        };
        
        for ( int i = 0; i < 10; i++ )
        {
        	h.put(keys[i], Integer.toString(i+1));
        }
        
        long startTime = new Date().getTime();
        
        for ( int i = 0; i < 10; i++ )
        {
        	System.out.println(h.get(keys[i]));
        }
   
        long endTime = new Date().getTime();
        
        System.out.println("Elapsed Time: " + (endTime - startTime) + " ms");
    }
}

Executing the above code leaves you with this output:

1
2
3
4
5
6
7
8
9
10
Elapsed Time: 0 ms

As you can see, we easily retrieved the objects we had originally put into the Hashtable and it took practically no time at all. How does our hashCode method do? Does it pass all 3 of the criteria laid out earlier? Let's look at each of the criteria one at a a time.

1. Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

Does our hashCode meet that criteria? Does our hashCode continually return the same value (assuming that our variable, a, hasn't changed)? Certainly, it does - it returns the value of a. Okay, next criteria.

2. If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

How about this one? Does our hashCode method still work here? Sure, it does. If two object have the same value for a, they will be equal (by the equals method). In such a situation, they would also return the same hashCode value. Our hashCode method works here. Okay, on to the final criteria.

3. It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode 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.

Well, this isn't really a requirement at all - it's more of a suggestion, if anything. It is best if the hashCodes for unequal objects are different, but it's not required. We'll look at this a little more in a few minutes.

So, there you have it - we've successfully overridden the hashCode method. So, how do you know when you should do such a thing? Well, in general, it's considered good practice to override hashCode any time you override equals. The reason for this is due to the default behavior of the equals and hashCode methods.

When Should you Override hashCode()?

In Java, the default equals method (as defined in Object) compares the two objects to see if they are, in fact, the same object. That implementation does not take into account any data that might be contained by the object. For example, had we not overridden the equals method in our class, MyObject, we'd see that the following code:

MyObject obj1 = new MyObject(1);
MyObject obj2 = new MyObject(1);
System.out.println(obj1.equals(obj2));

...would produce the output "false." The reason for this is that, even though the two objects contain the same data, they are different objects - two separate objects on the heap. Fortunately, we overrode the equals method and, given the MyObject class as defined originally, we'd get the output "true" from this example. However, what about the hashCode?

Well, the default hashCode method works in a similar fashion to the default equals method. It converts the internal address of the object into an int and uses that as the hashCode. Well, that won't work so well here. We just defined a way in which two distinct objects (which will, necessarily, have distinct memory addresses) to be considered "equal." The default hashCode implementation, however, will return different hashCodes for the two objects. That violates the second rule defined above - any objects that are considered equal (by their equals method) must generate the same hashCode value. Therefore, whenever you override the equals method, you should also override the hashCode method.

Study: Faulty hashCodes

What happens if we override the hashCode method poorly? Let's violate one of the rules, shall we? Let's change our hashCode method to look like this:

public int hashCode()
{
    return (int)(Math.random() * 5);
}

This one actually violates a couple rules. Not only does it not guarantee that two objects that are equal have the same hashCode, it doesn't even guarantee that the same object will keep the same hashCode from one invocation to the next. Any idea what havoc this might wreak on a poor, unsuspecting Hashtable? If I execute the main method again, as I did before, I get this output:

null
2
null
4
null
6
null
null
null
null
Elapsed Time: 0 ms

Eek! Look at all of the objects I'm missing! Without a properly functioning hashCode function, our Hashtable can't do its job. Objects are being put into the Hashtable but we can't properly get at them because our hashCode is random. This is certainly not the way to go. If you were to run this, you might even get different output than I got!

Even if the hashCode that is returned is always the same for a given object, we must ensure that the hashCodes that are returned for two objects that are equal are identical (Rule #2). Let's modify our MyObject class so that we hold true to Rule #1 but not to Rule #2. Below is the modified parts of our class:

public class MyObject
{
    int a;
    int b;
    
    public MyObject(int val1, int val2)
    {
        a = val1;
        b = val2;
    }
    
    ...
    
    public int hashCode()
    {
        return a - b;
    }
    
    ...
    
    public static void main(String[] args)
    {
        ....
        MyObject[] keys = 
        {
            new MyObject(11, 0),
            new MyObject(11, 1),
            new MyObject(11, 2),
            new MyObject(11, 3),
            new MyObject(11, 5),
            new MyObject(11, 5),
            new MyObject(11, 6),
            new MyObject(11, 7),
            new MyObject(11, 8),
            new MyObject(11, 9)
        };
        ...
    }
}

Executing this code gives us some more disturbing results, although they may not appear that way at first. Here's my output:

1
2
3
4
5
6
7
8
9
10
Elapsed Time: 0 ms

So what's wrong with that, you ask? Well, what should the put method do? If you first put an object into a Hashtable using a specific key and then put a new value into the Hashtable using a key that is equal to that one, the original value should be replaced with this new one. That's not what's happening here. Instead, our Hashtable is treating our keys as if they're all unequal. Eek! This is the same result you could expect if you were to override equals without overriding hashCode. Here's the output we should get, assuming we have a good hashCode method:

10
10
10
10
10
10
10
10
10
10
Elapsed Time: 0 ms

Inefficient hashCodes

Okay, one more thing to go over. What happens if we have a valid hashCode, but the values aren't very distinct. In this case, I'm going to hold to requirements 1 and 2, but I'm going to ignore requirement 3 entirely. Let's modify MyObject.hashCode() and our main method to look like this:

public int hashCode()
{
    return 0;
}

public static void main(String[] args)
{
    Hashtable h = new Hashtable();
    
    MyObject[] keys = new MyObject[10000];
    for ( int i = 0; i < 10000; i++ )
    {
        keys[i] = new MyObject(i);
    }
    
    for ( int i = 0; i < 10000; i++ )
    {
    	h.put(keys[i], Integer.toString(i+1));
    }
    
    long startTime = new Date().getTime();
    
    for ( int i = 0; i < 10000; i++ )
    {
    	h.get(keys[i]);
    }

    long endTime = new Date().getTime();
    
    System.out.println("Elapsed Time: " + (endTime - startTime) + " ms");   
}

Note that this is a valid hashCode method. It always returns the same value for a given object, assuming that nothing used in the equals method changes (not that it cares anything about that). It also returns the same value for two objects that are "equal." What it doesn't do is return a different value for objects that are not equal. It always returns the same value. This is a valid hashCode but, as this example will show, an inefficient one. Executing this 5 times using this new hashCode method, I get this output:

Elapsed Time: 7016
Elapsed Time: 7125
Elapsed Time: 7297
Elapsed Time: 7047
Elapsed Time: 7218

That gives me an average time of 7140.6 - roughly 7 seconds. By executing my original hashCode method and execute the same main method, I got this output:

Elapsed Time: 16
Elapsed Time: 16
Elapsed Time: 16
Elapsed Time: 15
Elapsed Time: 16

That's an average of about 16 millseconds - a far cry from the 7 seconds we saw earlier! We're seeing a dramatic increase in the amount of time required to retrieve objects from our Hashtable using the poor hashCode method. The reason for this is that, with every key object having the same hashCode, our Hashtable has no choice but to index every value under the same hashCode. In such a case, we've got everything in one long list and our Hashtable does us no good at all - we might as well have stored the objects in an ArrayList.

Summary

Hopefully you see the importance of creating a valid hashCode for any objects you're using. Whenever creating your own hashCode method, it's important to remember the 3 rules. I've listed them here in a summarized format; refer to the API Spec for full details.

1. The hashCode method must always return the same value (assuming the object has not changed) from one invocation to the next.
2. The hashCode for multiple "equal" objects must be identical.
3. The hashCodes for multiple "unequal" objects should be different, but it is not required.

With that knowledge, you should have a firm grasp on how to override hashCodes and make the most out of the Hashtable (and other Map classes) in Java. Remember to tune in to The SCJP Tipline for more updates.

Discuss this article in The Big Moose Saloon!


Return to Top

Lego^TM meets Java^TM : RoboJDE vs. LeJOS

by Jessica Sant

Introduction

I recently took a Robot Building Lab as part of my Master's degree program. The class was a mix of graduate and undergraduate Computer Science students. The majority of the course was taught using the HandyBoard controller programmed with a C derivative called IC4. Being the Java geek that I am, I was thrilled when my professor mentioned there was a Java product out there that you could use to program the HandyBoard. Enter RoboJDE. All the graduate students had an additional requirement to program an RCX robot using leJOS. This article is based on my experience of the two platforms. This is by no means a definitive comparison of the two platforms.

Every language has its purpose, and this may have not been the ideal application of Java due to the extremely limited memory on the platforms (~12k for the JVM, program, and the execution space), but trying to code java small was a very interesting (albeit sometimes frustrating) exercise. Plus, I always get a kick out of writing a program that "does something cool". And getting a robot to do stuff like following a flash light, avoiding obstacles it encounters, and determining where it is along a wall based on what it sees with its sonar definitely qualify as "cool".

Highlights

Hardware comparison

The RCX controller. Source: O'ReillyNet.com	The HandyBoard controller. Source: HandyBoard.com

Software comparison

• java.lang
  leJOS implements more of the java.lang package than implemented by RoboJDE. However the only significant piece of functionality I found missing from RoboJDE was java.lang.Math.random(), a simple random number generator. In order to simulate a random number generator in RoboJDE when we needed to randomly choose from three different actions (turn left, turn right, go straight) we performed a modulus operation on the current system time. This method worked for our purposes, but one should note that it is only effective if the call itself is made at random intervals.
• java.util
  One significant piece of the standard Java API that is implemented by leJOS and is missing from RoboJDE is the java.util package. The Collection classes are the most useful parts of the java.util package for the purposes of programming a robot. These data types are quite useful when developing significant programs such as trying to find the optimal path through a set of obstacles based on the sonar input. Because RoboJDE does not implement any of these data types, simple arrays must be used to hold the necessary data.

//initialize the sonar      
   Sensor.S2.setTypeAndMode (3, 0x80);       
   Sensor.S2.activate();
//read the raw value of the sonar      
   float value = Sensor.S2.readValue();
//manually convert sonar reading to distance in centimeters      
   float distance = (float)(12f+.53*a*2.54);

//initialize the sonar     
   RangeFinder sonar = new DevantechSRF04(...);     
   float distance = 0.0f;
//send out a ping and read the value within 100 milliseconds     
   sonar.ping();    
   long timeout = System.currentTimeMillis() + 100;   
   do {
//RoboJDE automatically converts sensor reading to distance   
      result = sonar.getDistanceCentimeters();  
   } while ((result < 0.0f) && (System.currentTimeMillis() < timeout));

//Performs a left turn by moving the left motor (A) slowly     
    Motor.A.setPower(1);
    Motor.A.forward();  
//moving the right motor (C) quickly     
    Motor.C.setPower(7);
    Motor.C.forward();
//pausing     
    Thread.sleep (1000);
//stopping both motors     
    Motor.A.stop();     
    Motor.C.stop();	

//initializes the motors     
    Motor leftMotor = HandyBoard.getMotor(0);    
    Motor rightMotor = HandyBoard.getMotor(1);
//performs the turn by moving the left motor slowly 
    leftMotor.setPower( Motor.FORWARD );
//moving the right motor quickly    
    rightMotor.setPower( Motor.FORWARD/10 );
//pausing    
    Thread.sleep(1000);
//stopping both motors     
    leftMotor.setPower( Motor.STOP );  
    rightMotor.setPower( Motor.STOP );

Sensor.S2.setTypeAndMode (SensorConstants.SENSOR_TYPE_TOUCH,
    SensorConstants.SENSOR_MODE_BOOL);
if( Sensor.S2.readBooleanValue() ) {   
    // avoids obstacle
}

DigitalInput leftBumper = HandyBoard.getDigitalInput(15);
DigitalInput leftBumper = HandyBoard.getDigitalInput(13);
if( leftBumper.isSet() && rightBumper.isSet() ) {
    //center hit avoid obstacle
} 
else if( leftBumper.isSet() && !rightBumper.isSet() ) {   
    // left hit avoid obstacle
} 
else if( !leftBumper.isSet() && rightBumper.isSet() ) {   
    // right hit, avoid obstacle
}

What I think

Links

• Ridgesoft, maker of RoboJDE
• LeJOS (sourceforge)
• Robot Building Lab at Drexel University
• This thread has a summary of the labs in the course
• HandyBoard.com
• LEGO Mindstorm

Discuss this article in The Big Moose Saloon!


Return to Top

Whizlabs SCMAD Exam Simulator (CX-310-110) Review

by Valentin Crettaz

When some big corporation's educational services announces the release of a new certification exam, you can be certain that the Whizlabs team won't be that far away. After many successful simulator releases in 2003 and before (SCBCD, SCJP 1.4, etc), Whizlabs now wants to make you MAD (that is, a Mobile Application Developer ) by complementing their product suite with another exam simulator for Sun's new certification exam targeted at the Micro Edition of the Java 2 Platform (J2ME). Whizlabs' simulators essentially pursue the following goals:

1. to provide a huge question bank in order to best train the exam taker, and
2. to closely mimic real exam conditions.

Basically, the user interface hasn't change much compared to what I have experienced with other simulators from Whizlabs' product line. While some display bugs have been eliminated, a few ones are still on the edge eargerly waiting to be terminated. Furthermore, when looking back at Lasse Koskela's review of their SCJP 1.4 simulator last December, it appears that Whizlabs has done much of its homework:

• I haven't experienced any problems during the installation process, and
• the code is well indented (even though monospace font is still not used for displaying code snippets.)

Moreover, I have to admit that I have specially liked the way Drag-n-Drop questions have been implemented. They are even better than in the real exam since after you have answered a question you can reopen the Drag-n-Drop box without having to answer the question again. This is, in my opinion, one of the big limitations in Sun's certification exam software. Actually, as most of you, every time I take a Sun certification exam, I have to write down my answer to a Drag-n-Drop question before closing the dialog box, which is a little annoying.

Regarding the content itself, you will find a total of 490 questions evenly distributed across 5 mock exams (68 questions each) and 1 quiz (150 questions). You can even create your own mock exams with the built-in test customizer that allows you to select any questions in the bank to help you focus on a specific area of your choice. Besides, all questions come with very exhaustive explanations and links to sections of the relevant specifications. Once you finish an exam you are offered the opportunity to review some answers you were unsure about or to directly go to the exam report and see if you have passed or failed. On the reports you will find a good deal of very comprehensive information. For each question, you will be able to see the objective to which the question relates, the level of difficulty, the type of the question (i.e., multiple choice, DnD, fill-in, etc) and whether you answered it correctly or not. Wait, that's not all!! The help menu will direct you to a complete user guide and some help content on how to use the tool itself. As always, Whizlabs has also bundled a Tips'N'Trick cheat sheet and quick revision notes for you to read just before taking the exam. On the downside, it's just unfortunate that you can't print out these helpful notes from the tool and take them with you to the test center to do some last minute brush up... Maybe, they'll consider adding that to future versions of their tools. Who knows...

A cool new feature has been added to the simulator: If you ever have a doubt about a question or an explanation or if you want to report some problem you experienced, you can do it by clicking on the "Discuss it" button and you will be forwarded to a dedicated SCMAD forum on Whizlabs website. Once you have logged in, you will just have to write your message. Of course, a live Internet connection is required in order to take advantage of this feature.

Finally, I think that this new exam simulator is well worth the money spent ($79.95 for new customers and $63.95 for existing ones) for the reasons enumerated below:

• The simulator is very efficient and is of great support for exam takers
• You get free upgrades for 6 months
• You get free technical support from the authors
• There are very few SCMAD mock exams out there yet (check out this link)
• And... (drum rolls) You'll get your money back if you don't pass the exam anyway

Don't hesitate to download the free trial edition to get a feeling of the exam simulator before buying it. I definitely recommend this outstanding resource to any respectful J2ME developer willing to tackle the SCMAD exam.

Resources
Whizlabs homepage
Whizlabs SCMAD exam simulator
SCMAD Certification Primer

Discuss this article in The Big Moose Saloon!


Return to Top

The Coffee House

An Agile Excursion

by Solveig Haugland

Discuss this article in The Big Moose Saloon!


Return to Top

Not yet posted. Check back soon.

Mosey on in and pull up a stool. The JavaRanch Big Moose Saloon is the place to get your Java questions answered. Our bartenders keep the peace, and folks are pretty friendly anyways, so don't be shy!

Question: Use OOP to design database tables schema?

Over in the OO, Patterns, UML and Refactoring forum, Edward Chen opened a bottle of worms with this thread starter:

This question has haunted a while.

Usually, we firstly check the porject requirements and set up tables, and then do 1/2/3-NF normaliztion.

I don't like this way, because it is not Object-oriented way. So any body could share exprience how we use OOP to design complicate table schema/relationship?

Now, mosey on o'er, see what folks are saying and chime in with some thoughts of your own.

Join this discussion in The Big Moose Saloon!


Return to Top

Following are the scheduled book promotions coming in July and August. Be sure to check our book promotions page often for changes and new promotions.

July 13	XSLT 2.0 Web Development	Dmitry Kirsanov	Prentice Hall PTR	XML and Related Technologies
July 20	J2EE 1.4: The Big Picture	Solveig Haugland, Mark Cade, Anthony Orapallo	Prentice Hall PTR	EJB and Other J2EE Technologies
July 27	Pro Jakarta Struts, Second Edition	John Carnell	Apress	Web Application Frameworks
August 3	Whizlabs SCMAD Certification Exam Simulator	Sathyanarayanan Srinivasan and Sivasundaram Umapathy	Whizlabs	Mobile Application Certification (SCMAD)
August 10	JavaServer Faces in Action	Kito D. Mann	Manning	Web Application Frameworks
August 10	JUnit Recipes: Practical Methods for Programmer Testing	J. B. Rainsberger	Manning	Testing
August 17	Whizlabs SCDJWS Certification Exam Simulator		Whizlabs	Web Services Certification (SCDJWS)
August 24	Java 2 v1.5 (Tiger) New Features	Herbert Schildt	McGraw-Hill Osborne Media	Java in General (intermediate)
August 31	Hibernate in Action	Christian Bauer, Gavin King	Manning	Object Relational Mapping
August 31	Explorer's Guide to the Semantic Web	Thomas B. Passin	Manning	General Computing

Return to Top