Java Technology Fundamentals Newsletter

Print-friendly Version

Welcome to the Java Developer Connection Java Technology Fundamentals Newsletter.

This monthly newsletter provides a way for you to learn the basics of the Java programming language, discover new resources, and keep up-to-date on the latest additions to the JDC's New to Java Programming Center.

CONTENTS

1. Java Programming Language Basics

Working with Hash Tables

2. Making Sense of the Java Class Libraries

Interface Set and Class TreeMap

3. Program Challenge

Create the Application PhoneList

4. Java Bits

The Difference Between the equals Method and the == Operator

5. For More Information

Read articles, Tech Tips, trails, and tutorials that provide more information on the topics discussed here.

Java Programming Language Basics

Working with Hash Tables

A hash table is a common data structure that offers quick insertion and search capabilities. Hash tables work with key-value pairs: Given some key, check the table to see if the key is present, and if it is, return the associated value.

In the standard libraries, you'll find support for hash tables in five different classes. In this tip, you'll examine two: HashMap and LinkedHashMap.

A common analogy for working with hash tables is the telephone book or the dictionary. Given some name, provide the phone number, or given some word, provide the definition. Hash tables work by looking up the key to find the value.

With an array, you look up a value via the integer index into the array. With a hash table, you don't use an integer directly, but instead use what's called a hash code. Hash codes map words or objects to numbers. Instead of having a table of the keys and sequentially scanning from front to back to check if a specific key is present, the hash table uses an intermediate value--The hash code.

The hash code allows the data structure to check only a single place for existence of a key. If nothing is found after converting a key to the hash code, the key is not present in the hash table.

But if something is found, that doesn't mean the key is present. Hash codes are not unique, and a secondary equality check is required to check the lookup value against the table contents. Only when the equality check passes do you know that the key is present.

When multiple keys map to the same hash code, a collision occurs. To work with hash tables successfully, use a hashing algorithm that results in as few collisions as possible.

For system classes like String and Date, this has already been done for you, but let's take a look at some ways to convert words to numbers by generating an algorithm.

A simple mechanism for converting strings to numbers is to sum up the numerical values for the characters in the string. For instance, to sum up the values, first convert each character to its integer equivalent (J = 74, o = 111, h = 104, n = 110). Next, sum them up (74+111+104+110 = 399). Unfortunately, many other names map to 399 also Cary, Cody, and Omar to name a few-- so this isn't an optimum hashing algorithm.

When using HashMap and related classes, you don't have to worry about the mapping mechanism directly. Mapping happens behind the scenes, and you never see the intermediate hash code values. The mapping can have a performance impact, though, when creating your own classes.

Using the hash table classes is simple. In a typical operation, you create the table, fill it up, then search or fetch. Operations like removal are also supported.

You create by calling the class constructor:

Map map = new HashMap();

Add to the table with the put method, providing the key and value:

map.put("key", "value");

Searching and fetching are two different operations. A search asks "does the key exist in the table?," while the fetch asks "what's the value of the key?"

For searching, you check if the hash table contains the key:

boolean contains = map.containsKey("key");

Fetching uses the search mechanism to see if a key exists before returning the value. That's where the get method comes in handy:

Object value = map.get("key");

The get method returns the value as an Object. If you want to treat the value as its data type, you must cast the value to the appropriate type:

String value = (String)map.get("key");

There is another fetch operation that fetches all the keys to dump out the entire contents of the hash table. This is a two step operation.

Step One: Get the set of all keys with the keySet method, or the set of entries with the entrySet method.

The keySet method fetches each individual key, without the value. If you need the value, look it up for each key. If you want both the key and value, use entrySet. Each key-value pair is stored in a Map.Entry.

Step 2: Use an Iterator to visit each element of the Set.

Here's keySet. After getting the set, you get the Iterator, and loop:

Set keys = map.keySet();
Iterator iterator = keys.iterator();
while (iterator.hasNext()) {
   String entry = (String)iterator.next();
   System.out.println(entry);
}

Here's entrySet. While you could use map.get(key) to look up each individual value, using entrySet is a more efficient mechanism. The process is almost identical:

Set entries = map.entrySet();
Iterator iterator2 = entries.iterator();
while (iterator2.hasNext()) {
   Map.Entry entry = (Map.Entry)iterator2.next();
   System.out.println(entry.getKey() + " : "
     + entry.getValue());
}

Printing out the keys in this manner may not produce the results you desire though. HashMap doesn't remember the order that entries were added. Instead, the entries are ordered by the intermediate hash code.

If you want the keys sorted, TreeMap comes in handy, but if you wish to display the entries in the order they were added, you need to use LinkedHashMap. By just changing the constructor line, the keySet or entrySet iterator is ordered in the manner in which the keys-value pairs were added.

Map map = new LinkedHashMap();

To find out how many elements are in the table, use the size method:

int size = map.size();

Now you can test your knowledge about hash tables with this online quiz.

Making Sense of the Java Class Libraries

Interface Set and Class TreeMap

A collection represents a group of objects that are known as its elements. Some collection implementations allow duplicate elements and others do not. Some are ordered while others are not. You can't provide a direct implementation of the Collection interface. Instead, use specific subinterfaces like Set or TreeMap, which are included the java.util package.

A Set interface extends Collection. It is a collection that can't contain duplicate elements.

A TreeMap implements the SortedMap interface by using a tree and extends AbstractMap. TreeMap provides an efficient way of storing key/value pairs, and allows quick retrieval. A tree map guarantees that its elements are sorted in a logical key order, such as alphabetically.

import java.util.*;

public class DemoTreeMap
 {
   public static void main (String args[])
    {
     //Create a tree map
     TreeMap tm = new TreeMap(); 
     
     // Put elements in the map
     tm.put("Carrots", new Integer(12));
     tm.put("Potatoes", new Integer(30));
     tm.put("Onions", new Integer(15));
     tm.put("Apples", new Integer(40));
     tm.put("Cherries", new Integer(300));
     
     //Check size of tree map
     System.out.println("The size of this tree map is " + tm.size() +
                                          " element pairs.");
     
     //     
     Set entries = tm.entrySet();
     Iterator i = entries.iterator();
     while (i.hasNext()) {
       Map.Entry entry = (Map.Entry)i.next();
       System.out.println(entry.getKey() + " : "
         + entry.getValue());
      }
     System.out.println();
     }
  } 

This application results in:

The size of this tree map is 5 element pairs.
Apples : 40
Carrots : 12
Cherries : 300
Onions : 15
Potatoes : 30 

Program Challenge

• Create a program that maintains a phone list of your friends to show the differences when traversing the entries based upon insertion order, hash code order, and sorted order.
• Print out the hash table keys and values.

See a possible solution to Challenge.

Java Bits

The Difference Between the equals Method and the == Operator

Run the following application:

public class EqualTest
 {
   public static void main(String args[]) 
    {
      Double Obj1 = new Double(2.43);
      Double Obj2 = new Double(2.43);
      Double Obj3 = Obj1;
      System.out.println("These objects are equal: ");
      System.out.println(Obj1 == Obj2);
      System.out.println(Obj1 == Obj3);      
      System.out.println(Obj1.equals(Obj2));
     }
 }

Note that the first comparison of objects Obj1 and Obj2, using the == operator, returns false. The second comparison of those same objects, using the equals method, returns true. In addition, the comparison of Obj1 with Obj3 returns true.

Both the == operator and the equals method compare for equality, but == is used with data types while the equals method compares objects.

In the example above, objects 1 and 2 hold the same value, but because a new instance is created, two objects with the same value exist. Two different objects have different memory addresses. On the other hand, Obj3 simply points at, or makes a reference to, an already existing object, so Obj1 == Obj3 return true.

To compare the values of objects, use the equals method. In the example above, Obj1.equals(Obj2) compares the values of Obj1 and Obj2, and returns true because the value of both objects is 2.43.

In summary, use the == to compare data types, and use the equals method to compare object values.

For More Information

Introduction to the Collections Framework

Lesson: Interfaces

Class HashMap

Interface Map

Using the LinkedHashMap

Class LinkedHashMap

Collections Framework Enhancements

Relational and Conditional Operators

Building an Application Introduction

Program Challenge Solution

See one possible solution to the July Program Challenge.

Downloading the Java 2 Platform

For most Java development, you need the class libraries, compiler, tools, and runtime environment provided with the J2SE development kit.

• Download J2SE
• Bookmark the specifications
• New to Java Programming Center

IMPORTANT: Please read our Terms of Use and Privacy policies:

• sun.com Terms of Use
• Sun Microsystems, Inc.: Privacy Policy
• System Maintenance

Copyright 2002 Sun Microsystems, Inc. All rights reserved.
901 San Antonio Road, Palo Alto, California 94303 USA

FEEDBACK

Tell us what you think of this supplement.

Have a question about programming? Use Java Online Support.

- Note -

Sun respects your online time and privacy. The Java Developer Connection mailing lists are used for internal Sun Microsystems purposes only. You have received this email because you elected to subscribe.

- Subscribe/Unsubscribe -

To subscribe, go to the subscriptions page, choose the newsletters you want to subscribe to and click Update

To unsubscribe, go to the subscriptions page, uncheck the appropriate check box, and click Update

This document is protected by copyright.

Java Technology Fundamentals
July 2002

Sun, Sun Microsystems, Java, J2SE are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.