At the heart of even the most basic Java programs are data structures, which are responsible for modeling information within the context of a program. There are many varieties of data structures, ranging from primitive data types to arrays to more complex structures like hash tables. In this chapter, you learn about the data structures provided by the Java API. More specifically, you learn how to use the data structures in the Java utility package, also known as java.util. This package contains a wide range of data structures applicable to many different programming scenarios. The goal of this chapter is to familiarize you with these data structures and show you the basics of how to use them. If you want more complete details regarding the data structure classes, refer to Chapter 34, "Package java.util," which is a complete reference for the java.util package.
The data structures provided by the Java utility package are very powerful and perform a wide range of functions. These data structures consist of an interface and five classes, which follow:
The Enumeration interface isn't itself a data structure, but it is very important within the context of other data structures. The Enumeration interface defines a means to retrieve successive elements from a data structure. For example, Enumeration defines a method called nextElement that is used to get the next element in a data structure that contains multiple elements.
The BitSet class implements a group of bits, or flags, that can be set and cleared individually. This class is very useful in cases where you need to keep up with a set of Boolean values; you just assign a bit to each value and set it or clear it appropriately.
The Vector class is very similar to a traditional Java array, except that it can grow as necessary to accommodate new elements. Like an array, elements of a Vector object can be accessed through an index into the vector. The nice thing about using the Vector class is that you don't have to worry about setting it to a specific size upon creation.
The Stack class implements a last-in-first-out (LIFO) stack of elements. You can think of a stack as a vertical stack of objects; when you add a new element, it gets stacked on top of the others. When you pull an element off the stack, it comes off the top. In other words, the last element you added to the stack is the first one to come back off.
The Dictionary class is an abstract class that defines a data structure for mapping keys to values. This is useful in cases where you want to be able to access data through a particular key rather than on the value of the data itself. Because the Dictionary class is abstract, it only provides the framework for a key-mapped data structure, rather than a specific implementation.
An actual implementation of a key-mapped data structure is provided by the Hashtable class. The Hashtable class provides a means of organizing data based on some user-defined key structure. For example, in an address list hash table, you could store and sort data based on a key such as ZIP code rather than on a person's name. The specific meaning of keys in regard to hash tables is totally dependent on the usage of the hash table and the data it contains.
That sums up the data structures provided by the Java utility package. Now that you have a cursory understanding of them, let's dig into each in a little more detail and see how they work.
The Enumeration interface provides a standard means of iterating through a list of sequentially stored elements, which is a common task of many data structures. Since Enumeration is an interface, its role is limited to providing the method protocol for data structures that can be enumerated in a sequential manner. Even though you can't use the interface outside the context of a particular data structure, understanding how it works will put you well on your way to understanding other Java data structures. With that in mind, take a look at the only two methods defined by the Enumeration interface:
public abstract boolean hasMoreElements();
public abstract Object nextElement();
The hasMoreElements method is used to determine whether the enumeration contains any more elements. You will typically call this method to see if you can continue iterating through an enumeration. An example of this is calling hasMoreElements in the conditional clause of a while loop that is iterating through an enumeration.
The nextElement method is responsible for actually retrieving the next element in an enumeration. If no more elements are in the enumeration, nextElement will throw a NoSuchElementException exception. Because you want to avoid generating exceptions whenever possible, you should always use hasMoreElements in conjunction with nextElement to make sure there is another element to retrieve. Following is an example of a while loop that uses these two methods to iterate through a data structure object that implements the Enumeration interface:
// e is an object that implements the Enumeration interface
while (e.hasMoreElements()) {
Object o = e.nextElement();
System.out.println(o);
}
This example code prints out the contents of an enumeration using the hasMoreElements and nextElement methods. Pretty simple!
The BitSet class is useful whenever you need to represent a group of Boolean flags. The nice thing about the BitSet class is that it alleviates the need for masking out the value of each bit; you simply refer to each bit using an index. Another nice feature about the BitSet class is that it automatically grows to represent the number of bits required by a program.
A good example of using a BitSet is an object that has a number of attributes that can easily be modeled by Boolean values. Because the individual bits in a bit set are accessed through an index, you can define each attribute as a constant index value:
class someBits {
public static final int readable = 0;
public static final int writeable = 1;
public static final int streamable = 2;
public static final int flexible = 3;
}
Notice that the attributes are assigned increasing values beginning with zero. You can use these values to get and set the appropriate bits in a bit set. But first, you need to create a BitSet object:
BitSet bits = new BitSet();
This constructor creates a bit set with no specified size. You can also create a bit set with a specific size:
BitSet bits = new BitSet(4);
This creates a bit set containing four Boolean bit fields. Regardless of the constructor used, all bits in new bit sets are initially set to false. Once you have a bit set created, you can easily set and clear the bits using the set and clear methods along with the bit constants you defined:
bits.set(someBits.writeable);
bits.set(someBits.streamable);
bits.set(someBits.flexible);
bits.clear(someBits.writeable);
In this code, the writeable, streamable, and flexible attributes are set, and then the writeable bit is cleared. Notice that the fully qualified name is used for each attribute because they are declared as static in the someBits class.
You can get the value of individual bits in a bit set using the get method:
boolean canIWrite = bits.get(someBits.writeable);
You can find out how many bits are being modeled by a bit set using the size method. An example of this follows:
int numBits = bits.size();
The BitSet class also provides other methods for performing comparisons and bitwise operations on bit sets such as AND, OR, and XOR. All of these methods take a BitSet object as their only parameter.
The Vector class implements a growable array of objects. Because the Vector class is responsible for growing itself as necessary to support more elements, it has to decide when and by how much to grow as new elements are added. You can easily control this aspect of vectors upon creation. Before getting into that, however, take a look at how to create a basic vector:
Vector v = new Vector();
That's about as simple as it gets! This constructor creates a default vector containing no elements. Actually, all vectors are empty upon creation. One of the attributes important to how a vector sizes itself is the initial capacity of a vector. The following code shows how to create a vector with a specified capacity:
Vector v = new Vector(25);
This vector is created to immediately support up to 25 elements. In other words, the vector will go ahead and allocate enough memory to support 25 elements. Once 25 elements have been added, however, the vector must decide how to grow itself to accept more elements. You can specify the value by which a vector grows using yet another Vector constructor:
Vector v = new Vector(25, 5);
This vector has an initial size of 25 elements, and it will grow
in increments of 5 elements whenever its size grows to more than
25 elements. This means that the vector will first jump to 30
elements in size, then 35, and so on. A smaller grow value for
a vector results in more efficient memory management, but at a
cost of more execution overhead because more memory allocations
are taking place. On the other hand, a larger grow value results
in fewer memory allocations, but sometimes memory may be wasted
if you don't use all the extra space created.
| Note |
The default grow value for a vector is 0, which actually results in the vector doubling its size whenever it needs to grow. In other words, a default grow value essentially acts like a grow value equal to the size of the vector. |
Unlike arrays, you can't just use square brackets ([]) to access the elements in a vector; you have to use methods defined in the Vector class. To add an element to a vector, you use the addElement method:
v.addElement("carrots");
v.addElement("broccoli");
v.addElement("cauliflower");
This code shows how to add some vegetable strings to a vector. To get the last string added to the vector, you can use the lastElement method:
String s = (String)v.lastElement();
The lastElement method retrieves the last element added to the vector. Notice that you have to cast the return value of lastElement because the Vector class is designed to work with Objects. Although lastElement certainly has its usefulness, you will probably find more use with the elementAt method, which allows you to index into a vector to retrieve an element. Following is an example of using the elementAt method:
String s1 = (String)v.elementAt(0);
String s2 = (String)v.elementAt(2);
Because vectors are zero-based, the first call to elementAt retrieves the "carrots" string, and the second call retrieves the "cauliflower" string. Just as you can retrieve an element at a particular index, you can also add and remove elements at an index using the insertElementAt and removeElementAt methods:
v.insertElementAt("squash", 1);
v.insertElementAt("corn", 0);
v.removeElementAt(3);
The first call to insertElementAt inserts an element at index 1, in between the "carrots" and "broccoli" strings. The "broccoli" and "cauliflower" strings are moved up a space in the vector to accommodate the inserted "squash" string. The second call to insertElementAt inserts an element at index 0, which is the beginning of the vector. In this case, all existing elements are moved up a space in the vector to accommodate the inserted "corn" string. At this point, the contents of the vector look like this:
"corn"
"carrots"
"squash"
"broccoli"
"cauliflower"
The call to removeElementAt removes the element at index 3, which is the "broccoli" string. The resulting contents of the vector consist of the following strings:
"corn"
"carrots"
"squash"
"cauliflower"
You can use the setElementAt method to change a specific element:
v.setElementAt("peas", 1);
This method replaces the "carrots" string with the "peas" string, resulting in the following vector contents:
"corn"
"peas"
"squash"
"cauliflower"
If you want to clear out the vector completely, you can remove all the elements with the removeAllElements method:
v.removeAllElements();
The Vector class also provides some methods for working with elements without using indexes. These methods actually search through the vector for a particular element. The first of these methods is the contains method, which simply checks to see if an element is in the vector:
boolean isThere = v.contains("celery");
Another method that works in this manner is the indexOf method, which finds the index of an element based on the element itself:
int i = v.indexOf("squash");
The indexOf method returns the index of the element in question if it is in the vector, or -1 if not. The removeElement method works similarly in that it removes an element based on the element itself, rather than an index:
v.removeElement("cauliflower");
If you're interested in working with all the elements in a vector sequentially, you can use the elements method, which returns an enumeration of the elements:
Enumeration e = v.elements();
If you recall from earlier in this chapter, you can use an enumeration to step through elements sequentially.
You may find yourself wanting to work with the size of a vector. Fortunately, the Vector class provides a few methods for determining and manipulating the size of a vector. First, the size method determines the number of elements in the vector:
int size = v.size();
If you want to explicitly set the size of a vector, you can use the setSize method:
v.setSize(10);
The setSize method expands or truncates the vector to accommodate the new size specified. If the vector is expanded because of a larger size, null elements are inserted as the newly added elements. If the vector is truncated, any elements at indexes beyond the specified size are discarded.
If you recall, vectors have two different attributes relating to size: size and capacity. The size is the number of elements in the vector, and the capacity is the amount of memory allocated to hold new elements. The capacity is always greater than or equal to the size. You can force the capacity to exactly match the size using the trimToSize method:
v.trimToSize();
You can also check to see what the capacity is using the capacity method:
int capacity = v.capacity();
You'll find that the Vector class is one of the most useful data structures provided in the Java API. This tour of the class should give you an idea of how powerful and easy it is to use vectors.
Stacks are a classic data structure used to model information that is accessed in a specific order. The Stack class in Java is implemented as a last-in-first-out (LIFO) stack, which means that the last item added to the stack is the first one to come back off. The Stack class defines only one constructor, which is a default constructor that creates an empty stack. You use this constructor to create a stack like this:
Stack s = new Stack();
You add new elements to a stack using the push method, which pushes an element onto the top of the stack:
s.push("One");
s.push("Two");
s.push("Three");
s.push("Four");
s.push("Five");
s.push("Six");
This code pushes six strings onto the stack, with the last string ("Six") remaining on top. You pop elements back off the stack using the pop method:
String s1 = (String)s.pop();
String s2 = (String)s.pop();
This code pops the last two strings off the stack, leaving the first four strings remaining. This code results in the s1 variable containing the "Six" string and the s2 variable containing the "Five" string.
If you want to get the top element on the stack without actually popping it off the stack, you can use the peek method:
String s3 = (String)s.peek();
This call to peek returns the "Four" string, but it leaves the string on the stack. You can search for an element on the stack using the search method:
int i = s.search("Two");
The search method returns the distance from the top of the stack of the element if it is found, or -1 if not. In this case, the "Two" string is the third element from the top, so the search method returns 2 (zero-based).
The only other method defined in the Stack class is empty, which determines if a stack is empty:
boolean isEmpty = s.empty();
Although the Stack class may not be quite as useful as the Vector class, it provides the functionality for a very common and established data structure.
The Dictionary class defines a framework for implementing a basic key-mapped data structure. Although you can't actually create Dictionary objects because the Dictionary class is abstract, you can still learn a lot about key-mapped data modeling by learning how the Dictionary class works. You can put the key-mapped approach to work using the Hashtable class, which is derived from Dictionary, or by deriving your own class from Dictionary. You learn about the Hashtable class in the next section of this chapter.
The Dictionary class defines a means of storing information based on a key. This is similar in some ways to how the Vector class works, in that elements in a vector are accessed through an index, which is a type of key. However, keys in the Dictionary class can be just about anything. You can create your own class to use as the keys for accessing and manipulating data in a dictionary.
The Dictionary class defines a variety of methods for working with the data stored in a dictionary. All of these methods are defined as abstract, meaning that derived classes will have to implement all of them to actually be useful. The put and get methods are used to put objects in the dictionary and get them back. Assuming that dict is a Dictionary-derived class that implements these methods, the following code shows how to use the put method to add elements to a dictionary:
dict.put("small", new Rectangle(0, 0, 5, 5));
dict.put("medium", new Rectangle(0, 0, 15, 15));
dict.put("large", new Rectangle(0, 0, 25, 25));
This code adds three rectangles to the dictionary using strings as the keys. To get an element from the dictionary, you use the get method and specify the appropriate key:
Rectangle r = (Rectangle)dict.get("medium");
You can also remove an element from the dictionary with a key using the remove method:
dict.remove("large");
You can find out how many elements are in the dictionary using the size method, much as you did with the Vector class:
int size = dict.size();
You can also check to see if the dictionary is empty using the isEmpty method:
boolean isEmpty = dict.isEmpty();
Finally, the Dictionary class includes two methods for enumerating the keys and values contained within: keys and elements. The keys method returns an enumeration containing all the keys contained in a dictionary, and the elements method returns an enumeration of all the key-mapped values contained. Following is an example of retrieving both enumerations:
Enumeration keys = dict.keys();
Enumeration elements = dict.elements();
Note that because keys are mapped to elements on a one-to-one basis, these enumerations are of equal length.
The Hashtable class is derived from Dictionary and provides a complete implementation of a key-mapped data structure. Like dictionaries, hash tables allow you to store data based on some type of key. Unlike dictionaries, hash tables have an efficiency associated with them defined by the load factor of the table. The load factor of a hash table is a number between 0.0 and 1.0 that determines how and when the hash table allocates space for more elements. Like vectors, hash tables have a capacity, which is the amount of memory allocated for the table. Hash tables allocate more memory by comparing the current size of the table with the product of the capacity and load factor. If the size of the hash table exceeds this product, the table increases its capacity by rehashing itself.
Load factors closer to 1.0 result in a more efficient usage of memory at the expense of a longer look-up time for each element. Similarly, load factors closer to 0.0 result in more efficient look-ups but also tend to be more wasteful with memory. Determining the load factor for your own hash tables is really dependent on the usage of the hash table and whether your priority is on performance or memory efficiency.
You create hash tables using one of three methods. The first method creates a default hash table:
Hashtable hash = new Hashtable();
The second constructor creates a hash table with the specified initial capacity:
Hashtable hash = new Hashtable(20);
Finally, the third constructor creates a hash table with the specified initial capacity and load factor:
Hashtable hash = new Hashtable(20, 0.75);
All of the abstract methods defined in Dictionary are implemented in the Hashtable class. Because these methods perform the exact same function in Hashtable, there's no need to cover them again. However, they are listed here just so you'll have an idea of what support Hashtable provides:
In addition to these methods, the Hashtable class implements a few others that perform functions specific to supporting hash tables. One of these is the clear method, which clears a hash table of all its keys and elements:
hash.clear();
The contains method is used to see if an object is stored in the hash table. This method searches for an object value in the hash table rather than a key. The following code shows how to use the contains method:
boolean isThere = hash.contains(new Rectangle(0, 0, 5, 5));
Similar to contains, the containsKey method searches a hash table, but it searches based on a key rather than a value:
boolean isThere = hash.containsKey("Small");
As mentioned earlier, a hash table will rehash itself when it determines that it must increase its capacity. You can force a rehash yourself by calling the rehash method:
hash.rehash();
That sums up the important methods implemented by the Hashtable class. Even though you've seen all the methods, you still may be wondering exactly how the Hashtable class is useful. The practical usage of a hash table is actually in representing data that is too time-consuming to search or reference by value. In other words, it's much more efficient to access complex elements in a data structure using a key rather than by comparing the objects themselves. Furthermore, hash tables typically compute a key for elements, which is called a hash code. For example, an object such as a string can have an integer hash code computed for it that uniquely represents the string. When a bunch of strings are stored in a hash table, the table can access the strings by integer hash codes as opposed to the contents of the strings themselves.
This technique of computing and using hash codes for object storage and reference is exploited very heavily throughout the Java system. This is apparent in the fact that the parent of all classes, Object, defines a hashCode method that is overridden in most standard Java classes. Any class that defines a hashCode method can be efficiently stored and accessed in a hash table. A class that is to be hashed must also implement the equals method, which defines a way of telling whether two objects are equal. The equals method usually just performs a straight comparison of all the member variables defined in a class.
Hash tables are an extremely powerful data structure that you will probably want to integrate into some of your programs that manipulate large amounts of data. The fact that they are so widely supported in the Java API through the Object class should give you a clue as to their importance in Java programming.
In this chapter, you learned all about the data structures provided by the Java utility package (java.util). You learned exactly what each data structure provides in terms of modeling data in different ways. You then moved on to the details of each data structure and how to use it to actually model data. Although this chapter didn't go into great detail regarding practical scenarios that use the data structures in your own programs, it did cover the basics of how to use each of the data structures. The reality is that there are limitless uses of the data structures in your own programs, so the best approach is to learn how to use them in general terms and then apply them to your own code as you see fit.