Java Collections By John Zukowski - Part3

Couple of Days i started reading Java Collections by John Zukowski.

Nice book written by John Zukowski.

Few important quotations i wanted to share from the next 2 chapters (5-6).

1) Understanding Hash Tables

Internally, a hash table is a data structure that offers nearly constant time insertion and searching (this is shown as 0(1) in Big O Notation). This means that no matter how large or small the structure, it will take roughly the same amount of time to insert or locate any element. How do hash tables do that? And under what conditions is the time not "nearly constant?"

When using the key−value pairs in a hash table, the keys are converted into an integer called a hash code by using a hashing algorithm. This hash code is then reduced—based upon the internal storage structure used by the hash table—to serve as an index into this structure (an array). For two equal elements, the hash code must be the same. Two elements are defined as equal if the equals() method returns true when they are compared.
For two unequal elements, the hash code may be different or the same.

Note The hashCode() method is defined in the Object class to generate hash codes and is frequently overridden in subclasses.

2) The process of converting a key (an object) into a hash code is done by the object's hashing algorithm, the hashCode() method of the object in Java. A hashing algorithm must be quick so that the process of finding something is fast. However, a quick algorithm isn't always best because the algorithm needs to spread out the results in order to avoid collisions.

3) Removing Key−Value Pairs

If you need to remove an element from a hash table, simply call the remove() method with the specific key as its argument:

public Object remove(Object key)

If the key is present as a key within the hash table, the key−value pair will be removed and the value object will be returned.

To get rid of all key−value pairs from a hash table, call the clear() method instead:
public void clear()

Warning Clearing a hash table does not return its internal capacity to the initial capacity. It only nulls out all the entries within the table.

4) Finding Elements

The Hashtable class contains three methods that let you check to see whether a specific key or a specific value is within the set of entries for the hash table. The simplest of the three is the containsKey() method, which functions like the get() method:

public boolean containsKey(Object key)

But instead of returning a value for the key, it returns true if the key is present and false if otherwise.

The duplicate pair of methods, contains() and containsValue(), each check to see if a specific value is found
within the Hashtable:

public boolean contains(Object value)
public boolean containsValue(Object value)

5) Hashtable Immutability

If it occurs that a hash table's contents are initialized to a fixed set of elements, you can make the table read−only to prevent accidental change. The Collections class provides this capability with the public static Map unmodifiableMap(Map map) method:

Hashtable h = new Hashtable();
// fill hash table
Map m = Collections.unmodifiableMap(h);

6) Printing Bit Sets

The BitSet class overrides the toString() method inherited from Object:

public String toString()

The string generated by calling the toString() method is a comma−delimited list of set bit positions, which is set and is surrounded by curly braces ({ }). For example, if the bits at position 0, 36, and 42 were set, calling toString() would generate the following string:

{0, 36, 42}

When a BitSet is first created, the returned string is the empty set:
{}

7) Checking Bit Sets for Equality

The BitSet class overrides the equals() method from Object to define the equality of bit sets.

public boolean equals(Object object)

Two bit sets are defined as equal if both bit sets have the same set or clear state at every position. In other
words, this[index]=object[index] must be true for each index in both sets. When one set is shorter than the
other, the remaining elements would need to be clear in the longer set for both sets to be equal.

About the Author

John Zukowski has been involved with the Java platform since it was just called Java, 11 years and running, since 1995. He is actively working with SavaJe Technologies to finish up the JavaOne 2006 device of show: the Jasper S20 mobile phone. He currently writes a monthly column for Sun’s Core Java Technologies Tech Tips and Technology Fundamentals Newsletter. He has contributed content to numerous other sites, including jGuru, DevX, Intel, and JavaWorld. He has written many other popular titles on Java, including Java AWT Reference (O’Reilly), Mastering Java 2 (Sybex), Borlands’ JBuilder: No Experience Required (Sybex), Learn Java with JBuilder 6 (Apress), Java Collections (Apress), and The Definitive Guide to Swing (Apress).