Types of collections

Bruce Eckel's Thinking in Java Contents | Prev | Next

Vector

Crashing Java

//: CrashJava.java
// One way to crash Java
import java.util.*;
 
public class CrashJava {
  public String toString() {
    return "CrashJava address: " + this + "\n";
  }
  public static void main(String[] args) {
    Vector v = new Vector();
    for(int i = 0; i < 10; i++)
      v.addElement(new CrashJava());
    System.out.println(v);
  }
} ///:~ 

It turns out that if you simply create a CrashJava object and print it out, you’ll get an endless sequence of exceptions. However, if you place the CrashJava objects in a Vector and print out that Vector as shown here, it can’t handle it and you don’t even get an exception; Java just crashes. (But at least it didn’t bring down my operating system.) This was tested with Java 1.1.

BitSet

//: Bits.java
// Demonstration of BitSet
import java.util.*;
 
public class Bits {
  public static void main(String[] args) {
    Random rand = new Random();
    // Take the LSB of nextInt():
    byte bt = (byte)rand.nextInt();
    BitSet bb = new BitSet();
    for(int i = 7; i >=0; i--)
      if(((1 << i) &  bt) != 0)
        bb.set(i);
      else
        bb.clear(i);
    System.out.println("byte value: " + bt);
    printBitSet(bb);
 
    short st = (short)rand.nextInt();
    BitSet bs = new BitSet();
    for(int i = 15; i >=0; i--)
      if(((1 << i) &  st) != 0)
        bs.set(i);
      else
        bs.clear(i);
    System.out.println("short value: " + st);
    printBitSet(bs);
 
    int it = rand.nextInt();
    BitSet bi = new BitSet();
    for(int i = 31; i >=0; i--)
      if(((1 << i) &  it) != 0)
        bi.set(i);
      else
        bi.clear(i);
    System.out.println("int value: " + it);
    printBitSet(bi);
 
    // Test bitsets >= 64 bits:
    BitSet b127 = new BitSet();
    b127.set(127);
    System.out.println("set bit 127: " + b127);
    BitSet b255 = new BitSet(65);
    b255.set(255);
    System.out.println("set bit 255: " + b255);
    BitSet b1023 = new BitSet(512);
// Without the following, an exception is thrown
// in the Java 1.0 implementation of BitSet:
//    b1023.set(1023);
    b1023.set(1024);
    System.out.println("set bit 1023: " + b1023);
  }
  static void printBitSet(BitSet b) {
    System.out.println("bits: " + b);
    String bbits = new String();
    for(int j = 0; j < b.size() ; j++)
      bbits += (b.get(j) ? "1" : "0");
    System.out.println("bit pattern: " + bbits);
  }
} ///:~ 

The random number generator is used to create a random byte, short, and int, and each one is transformed into a corresponding bit pattern in a BitSet. This works fine because a BitSet is 64 bits, so none of these cause it to increase in size. But in Java 1.0, when the BitSet is greater than 64 bits, some strange behavior occurs. If you set a bit that’s just one greater than the BitSet’s currently-allocated storage, it will expand nicely. But if you try to set bits at higher locations than that without first just touching the boundary, you’ll get an exception, since the BitSet won’t expand properly in Java 1.0. The example shows a BitSet of 512 bits being created. The constructor allocates storage for twice that number of bits. Then if you try to set bit 1024 or greater without first setting bit 1023, you’ll throw an exception in Java 1.0. Fortunately, this is fixed in Java 1.1, but avoid using the BitSet if you write code for Java 1.0.

Stack

//: Stacks.java
// Demonstration of Stack Class
import java.util.*;
 
public class Stacks {
  static String[] months = { 
    "January", "February", "March", "April",
    "May", "June", "July", "August", "September",
    "October", "November", "December" };
  public static void main(String[] args) {
    Stack stk = new Stack();
    for(int i = 0; i < months.length; i++)
      stk.push(months[i] + " ");
    System.out.println("stk = " + stk);
    // Treating a stack as a Vector:
    stk.addElement("The last line");
    System.out.println(
      "element 5 = " + stk.elementAt(5));
    System.out.println("popping elements:");
    while(!stk.empty())
      System.out.println(stk.pop());
  }
} ///:~ 

Each line in the months array is inserted into the Stack with push( ), and later fetched from the top of the stack with a pop( ). To make a point, Vector operations are also performed on the Stack object. This is possible because, by virtue of inheritance, a Stack is a Vector. Thus, all operations that can be performed on a Vector can also be performed on a Stack, such as elementAt( ).

Hashtable

//: AssocArray.java
// Simple version of a Dictionary
import java.util.*;
 
public class AssocArray extends Dictionary {
  private Vector keys = new Vector();
  private Vector values = new Vector();
  public int size() { return keys.size(); }
  public boolean isEmpty() {
    return keys.isEmpty();
  }
  public Object put(Object key, Object value) {
    keys.addElement(key);
    values.addElement(value);
    return key;
  }
  public Object get(Object key) {
    int index = keys.indexOf(key);
    // indexOf() Returns -1 if key not found:
    if(index == -1) return null;
    return values.elementAt(index);
  }
  public Object remove(Object key) {
    int index = keys.indexOf(key);
    if(index == -1) return null;
    keys.removeElementAt(index);
    Object returnval = values.elementAt(index);
    values.removeElementAt(index);
    return returnval;
  }
  public Enumeration keys() {
    return keys.elements();
  }
  public Enumeration elements() {
    return values.elements();
  }
  // Test it:
  public static void main(String[] args) {
    AssocArray aa = new AssocArray();
    for(char c = 'a'; c <= 'z'; c++)
      aa.put(String.valueOf(c),
             String.valueOf(c)
             .toUpperCase());
    char[] ca = { 'a', 'e', 'i', 'o', 'u' };
    for(int i = 0; i < ca.length; i++)
      System.out.println("Uppercase: " +
             aa.get(String.valueOf(ca[i])));
  }
} ///:~ 

The first thing you see in the definition of AssocArray is that it extends Dictionary . This means that AssocArray is a type of Dictionary, so you can make the same requests of it that you can a Dictionary. If you make your own Dictionary, as is done here, all you need to do is fill in all the methods that are in Dictionary. (And you must override all the methods because all of them – with the exception of the constructor – are abstract.)

The Vectors keys and values are linked by a common index number. That is, if you call put( ) with a key of “roof” and a value of “blue” (assuming you’re associating the various parts of a house with the colors they are to be painted) and there are already 100 elements in the AssocArray, then “roof” will be the 101 element of keys and “blue” will be the 101 element of values. And if you look at get( ), when you pass “roof” in as the key, it produces the index number with keys.indexOf( ), and then uses that index number to produce the value in the associated values vector.

The test in main( ) is simple; it’s just a map of lowercase characters to uppercase characters, which could obviously be done in a number of more efficient ways. But it shows that AssocArray is functional.

The standard Java library contains only one embodiment of a Dictionary, called Hashtable.[34] Java’s Hashtable has the same basic interface as AssocArray (since they both inherit Dictionary), but it differs in one distinct way: efficiency. If you look at what must be done for a get( ), it seems pretty slow to search through a Vector for the key. This is where Hashtable speeds things up. Instead of the tedious linear search for the key, it uses a special value called a hash code . The hash code is a way to take some information in the object in question and turn it into a “relatively unique” int for that object. All objects have a hash code, and hashCode( ) is a method in the root class Object. A Hashtable takes the hashCode( ) of the object and uses it to quickly hunt for the key. This results in a dramatic performance improvement. [35] The way that a Hashtable works is beyond the scope of this book [36] – all you need to know is that Hashtable is a fast Dictionary, and that a Dictionary is a useful tool.

//: Statistics.java
// Simple demonstration of Hashtable
import java.util.*;
 
class Counter { 
  int i = 1; 
  public String toString() { 
    return Integer.toString(i); 
  }
}
 
class Statistics {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i < 10000; i++) {
      // Produce a number between 0 and 20:
      Integer r = 
        new Integer((int)(Math.random() * 20));
      if(ht.containsKey(r))
        ((Counter)ht.get(r)).i++;
      else
        ht.put(r, new Counter());
    }
    System.out.println(ht);
  }
} ///:~ 

In main( ), each time a random number is generated it is wrapped inside an Integer object so that handle can be used with the Hashtable. (You can’t use a primitive with a collection, only an object handle.) The containsKey( ) method checks to see if this key is already in the collection. (That is, has the number been found already?) If so, the get( ) methods gets the associated value for the key, which in this case is a Counter object. The value i inside the counter is then incremented to indicate that one more of this particular random number has been found.

{19=526, 18=533, 17=460, 16=513, 15=521, 14=495,
 13=512, 12=483, 11=488, 10=487, 9=514, 8=523,
 7=497, 6=487, 5=480, 4=489, 3=509, 2=503, 1=475,
 0=505}

Creating “key” classes
In the previous example, a standard library class ( Integer) was used as a key for the Hashtable. It worked fine as a key, because it has all the necessary wiring to make it work correctly as a key. But a common pitfall occurs when using Hashtables when you create your own classes to be used as keys. For example, consider a weather predicting system that matches Groundhog objects to Prediction objects. It seems fairly straightforward: you create the two classes and use Groundhog as the key and Prediction as the value:

//: SpringDetector.java
// Looks plausible, but doesn't work right.
import java.util.*;
 
class Groundhog {
  int ghNumber;
  Groundhog(int n) { ghNumber = n; }
}
 
class Prediction {
  boolean shadow = Math.random() > 0.5;
  public String toString() {
    if(shadow)
      return "Six more weeks of Winter!";
    else
      return "Early Spring!";
  }
}
 
public class SpringDetector {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i < 10; i++)
      ht.put(new Groundhog(i), new Prediction());
    System.out.println("ht = " + ht + "\n");
    System.out.println(
      "Looking up prediction for groundhog #3:");
    Groundhog gh = new Groundhog(3);
    if(ht.containsKey(gh))
      System.out.println((Prediction)ht.get(gh));
  }
} ///:~ 

Each Groundhog is given an identity number, so you can look up a Prediction in the Hashtable by saying “Give me the Prediction associated with Groundhog number 3.” The Prediction class contains a boolean that is initialized using Math.random( ), and a toString( ) that interprets the result for you. In main( ), a Hashtable is filled with Groundhogs and their associated Predictions. The Hashtable is printed so you can see that it has been filled. Then a Groundhog with an identity number of 3 is used to look up the prediction for Groundhog #3.

It seems simple enough, but it doesn’t work. The problem is that Groundhog is inherited from the common root class Object (which is what happens if you don’t specify a base class, thus all classes are ultimately inherited from Object). It is Object’s hashCode( ) method that is used to generate the hash code for each object, and by default it just uses the address of its object. Thus, the first instance of Groundhog(3) does not produce a hash code equal to the hash code for the second instance of Groundhog(3) that we tried to use as a lookup.

//: SpringDetector2.java
// If you create a class that's used as a key in
// a Hashtable, you must override hashCode()
// and equals().
import java.util.*;
 
class Groundhog2 {
  int ghNumber;
  Groundhog2(int n) { ghNumber = n; }
  public int hashCode() { return ghNumber; }
  public boolean equals(Object o) {
    if ((o != null) && (o instanceof Groundhog2))
      return 
        ghNumber == ((Groundhog2)o).ghNumber;
    else return false;
  }
}
 
public class SpringDetector2 {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i < 10; i++)
      ht.put(new Groundhog2(i),new Prediction());
    System.out.println("ht = " + ht + "\n");
    System.out.println(
      "Looking up prediction for groundhog #3:");
    Groundhog2 gh = new Groundhog2(3);
    if(ht.containsKey(gh))
      System.out.println((Prediction)ht.get(gh));
  }
} ///:~ 

Note that this uses the Prediction class from the previous example, so SpringDetector.java must be compiled first or you’ll get a compile-time error when you try to compile SpringDetector2.java .

Groundhog2.hashCode( ) returns the ground hog number as an identifier. (In this example, the programmer is responsible for ensuring that no two ground hogs exist with the same ID number.) The hashCode( ) is not required to return a unique identifier, but the equals( ) method must be able to strictly determine whether two objects are equivalent.

The equals( ) method does two sanity checks: to see if the object is null, and if not, whether it is an instance of Groundhog2 (using the instanceof keyword, which is fully explained in Chapter 11). It should be a Groundhog2 to even continue executing equals( ). The comparison, as you can see, is based on the actual ghNumbers. This time, when you run the program, you’ll see it produces the correct output. (Many of the Java library classes override the hashcode( ) and equals( ) methods to be based upon their contents.)

Properties: a type of Hashtable
In the first example in this book, a type of Hashtable was used called Properties. In that example, the lines:

Properties p = System.getProperties();
p.list(System.out);

Enumerators revisited

//: Enumerators2.java
// Revisiting Enumerations
import java.util.*;
 
class PrintData {
  static void print(Enumeration e) {
    while(e.hasMoreElements())
      System.out.println(
        e.nextElement().toString());
  }
}
 
class Enumerators2 {
  public static void main(String[] args) {
    Vector v = new Vector();
    for(int i = 0; i < 5; i++)
      v.addElement(new Mouse(i));
 
    Hashtable h = new Hashtable();
    for(int i = 0; i < 5; i++)
      h.put(new Integer(i), new Hamster(i));
 
    System.out.println("Vector");
    PrintData.print(v.elements());
    System.out.println("Hashtable");
    PrintData.print(h.elements());
  }
} ///:~ 

Note that PrintData.print( ) takes advantage of the fact that the objects in these collections are of class Object so it can call toString( ). It’s more likely that in your problem, you must make the assumption that your Enumeration is walking through a collection of some specific type. For example, you might assume that everything in the collection is a Shape with a draw( ) method. Then you must downcast from the Object that Enumeration.nextElement() returns to produce a Shape.


[34] If you plan to use RMI (described in Chapter 15), you should be aware that there’s a problem when putting remote objects into a Hashtable. (See Core Java , by Cornell & Horstmann, Prentice-Hall 1997).

[35] If these speedups still don’t meet your performance needs, you can further accelerate table lookup by writing your own hash table routine. This avoids delays due to casting to and from Objects and synchronization built into the Java Class Library hash table routine. To reach even higher levels of performance, speed enthusiasts can use Donald Knuth’s The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition to replace overflow bucket lists with arrays that have two additional benefits: they can be optimized for disk storage characteristics and they can save most of the time of creating and garbage collecting individual records .

[36] The best reference I know of is Practical Algorithms for Programmers , by Andrew Binstock and John Rex, Addison-Wesley 1995.



Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: December 11, 2014 @ 1:00 p.m. ET / 10:00 a.m. PT Market pressures to move more quickly and develop innovative applications are forcing organizations to rethink how they develop and release applications. The combination of public clouds and physical back-end infrastructures are a means to get applications out faster. However, these hybrid solutions complicate DevOps adoption, with application delivery pipelines that span across complex hybrid cloud and non-cloud environments. Check out this …

  • CentreCorp is a fully integrated and diversified property management and real estate service company, specializing in the "shopping center" segment, and is one of the premier retail service providers in North America. Company executives travel a great deal, carrying a number of traveling laptops with critical current business data, and no easy way to back up to the network outside the office. Read this case study to learn how CentreCorp implemented a suite of business continuity services that included …

Most Popular Programming Stories

More for Developers

RSS Feeds