Java objects objects object In this chapter we will review the structure of a Java program and use some of the classes that are provided in the Java libraries. Program Structure A Java program is a set of class definitions. One class definition is designated as the startup class. It must contain a method named main that is where the execution of the program begins. A minimal Java program consists of a class definition with a single method definition: verbatim class Hello // main: generate some simple output public static void main (String[] args) System.out.println ("Hello, world."); verbatim Some people judge the quality of a programming language by the simplicity of the ``Hello, World.'' program. By this standard, Java does not do very well. Although this program only defines one class, named Hello, it is free to use the built-in Java classes. This program uses the class named System which contains an object named out on which we invoke a method named println. This method has the effect of printing a String. Packages package AWT Abstract Window Toolkit import statement!import The built-in Java classes are divided into a number of packages, including java.lang, which contains many of the most commonly used classes (like System), and java.awt, which contains classes that pertain to the Java Abstract Window Toolkit (AWT), which contains classes for windows, buttons, graphics, etc. In order to use a package, you have to import it; for example, the statment import java.awt.Point imports a class named Point from the AWT. The classes in java.lang are imported automatically, which is why the Hello class didn't require an import statement. All import statements appear at the beginning of the program, outside the class definition. Point objects Point class!Point At the most basic level, a point is two numbers (coordinates) that we treat collectively as a single object. In mathematical notation, points are often written in parentheses, with a comma separating the coordinates. For example, indicates the origin, and indicates the point units to the right and units up from the origin. new statement!new In Java, a point is represented by a Point object. To create a new point, you have to use the new command: verbatim Point blank; blank = new Point (3, 4); verbatim The first line is a conventional variable declaration: blank has type Point. The second line invokes the new command, specifies the type of the new object, and provides arguments. It will probably not surprise you that the arguments are the coordinates of the new point, . declaration statement!declaration reference state diagram state The result of the new command is a reference to the new point. This reference is assigned to the the variable blank. A standard way to diagram this assignment is shown in the figure. 0.1in figure=reference.eps 0.1in As usual, the name of the variable blank appears outside the box and its value appears inside the box. In this case, the value is a reference, which is shown graphically with a dot and an arrow. The arrow points to the object that is referred to. The big box shows the newly-created object with two values in it. The names x and y are the names of the instance variables. Taken together, all the variables, values, and objects in a program are called the state. Diagrams like this that show the state of the program are called state diagrams. As the program runs, the state changes, so you should think of a state diagram as a snapshot of a particular point in the execution. Instance variables variable!instance instance variable The pieces of data that make up an object are sometimes called components, records, or fields. In Java they are called instance variables because each object, which is an instance of its type, has its own copy of the instance variables. It's like the glove compartment of a car. Each car is an instance of the type ``car,'' and each car has its own glove compartment. If you asked me to get something from the glove compartment of your car, you would have to tell me which car is yours. dot notation Similarly, if you want to read a value from an instance variable, you have to specify the object you want to get it from. In Java this is done using the dot operator. verbatim int x = blank.x; verbatim The expression blank.x means ``go to the object blank refers to, and get the value of x.'' In this case we assign the value to a local variable named x. Notice that there is no conflict between the local variable named x and the instance variable named x. The purpose of the dot operator is to identify which variable you are referring to unambiguously. You can use the dot operator as part of any Java expression, so the following are legal. verbatim System.out.println (blank.x + ", " + blank.y); int distance = blank.x * blank.x + blank.y * blank.y; verbatim The first line prints 3, 4; the second line calculates the value 25. Objects as parameters parameter object!as parameter You can pass objects as parameters in the usual way. For example verbatim public static void printPoint (Point p) System.out.println ("(" + p.x + ", " + p.y + ")"); verbatim is a method that takes a point as an argument and prints it in the standard format. If you invoke printPoint (blank), it will print (3, 4). Actually, Java has a built-in method for printing Points. If you invoke System.out.println (blank), you get verbatim java.awt.Point[x=3,y=5] verbatim This is a standard format Java uses for printing objects. It prints the name of the type, followed by the contents of the object, including the names and values of the instance variables. As a second example, the method distance takes two Points as parameters and calculates the distance between them. verbatim public static double distance (Point p1, Point p2) double dx = (double)(p2.x - p1.x); double dy = (double)(p2.y - p1.y); return Math.sqrt (dx*dx + dy*dy); verbatim The typecasts are not really necessary; I just added them as a reminder that the instance variables in a Point are integers. Rectangles Rectangle class!Rectangle Rectangles are similar to points, except that they have four instance variables, named x, y, width and height. Other than that, everything is pretty much the same. verbatim Rectangle box = new Rectangle (0, 0, 100, 200); verbatim creates a new Rectangle object and makes box refer to it. The figure shows the effect of this assignment. 0.1in figure=rectangle.eps 0.1in If you print box, you get verbatim java.awt.Rectangle[x=0,y=0,width=100,height=200] verbatim Again, this is the result of a built-in Java method that knows how to print Rectangle objects. Objects as return types object!as return type return statement!return You can write methods that return objects. For example, findCenter takes a Rectangle as an argument and returns a Point that contains the coordinates of the center of the Rectangle: verbatim public static Point findCenter (Rectangle box) int x = box.x + box.width/2; int y = box.y + box.height/2; return new Point (x, y); verbatim Notice that you can use new to create a new object, and then immediately use the result as a return value. Objects are mutable object!mutable mutable You can change the contents of an object by making an assignment to one of its instance variables. For example, to ``move'' a rectangle without changing its size, you could modify the x and y values: verbatim box.x = box.x + 50; box.y = box.y + 100; verbatim The result is shown in the figure: 0.1in figure=rectangle2.eps 0.1in encapsulation generalization We could take this code and encapsulate it in a method, and generalize it to move the rectangle by any amount: verbatim public static void moveRect (Rectangle box, int dx, int dy) box.x = box.x + dx; box.y = box.y + dy; verbatim The variables dx and dy indicate how far to move the rectangle in each direction. Invoking this method has the effect of modifying the Rectangle that is passed as an argument. verbatim Rectangle box = new Rectangle (0, 0, 100, 200); moveRect (box, 50, 100); System.out.println (box); verbatim prints java.awt.Rectangle[x=50,y=100,width=100,height=200]. Modifying objects by passing them as arguments to methods can be useful, but it can also make debugging more difficult because it is not always clear which method invocations do or do not modify their arguments. Later, I will discuss some pros and cons of this programming style. In the meantime, we can enjoy the luxury of Java's built-in methods, which include translate, which does exactly the same thing as moveRect, although the syntax for invoking it is a little different. Instead of passing the Rectangle as an argument, we invoke translate on the Rectangle and pass only dx and dy as arguments. verbatim box.translate (50, 100); verbatim The effect is exactly the same. Aliasing aliasing aliasing reference Remember that when you make an assignment to an object variable, you are assigning a reference to an object. It is possible to have multiple variables that refer to the same object. For example, this code: verbatim Rectangle box1 = new Rectangle (0, 0, 100, 200); Rectangle box2 = box1; verbatim generates a state diagram that looks like this: 0.1in figure=aliasing.eps 0.1in Both box1 and box2 refer or ``point'' to the same object. In other words, this object has two names, box1 and box2. When a person uses two names, it's called aliasing. Same thing with objects. When two variables are aliased, any changes that affect one variable also affect the other. For example: verbatim System.out.println (box2.width); box1.grow (50, 50); System.out.println (box2.width); verbatim The first line prints 100, which is the width of the Rectangle referred to by box2. The second line invokes the grow method on box1, which expands the Rectangle by 50 pixels in every direction (see the documentation for more details). The effect is shown in the figure: 0.1in figure=aliasing2.eps 0.1in As should be clear from this figure, whatever changes are made to box1 also apply to box2. Thus, the value printed by the third line is 200, the width of the expanded rectangle. (As an aside, it is perfectly legal for the coordinates of a Rectangle to be negative.) As you can tell even from this simple example, code that involves aliasing can get confusing fast, and it can be difficult to debug. In general, aliasing should be avoided or used with care. null null When you create an object variable, remember that you are creating a reference to an object. Until you make the variable point to an object, the value of the variable is null. null is a special value in Java (and a Java keyword) that is used to mean ``no object.'' The declaration Point blank; is equivalent to this initialization verbatim Point blank = null; verbatim and is shown in the following state diagram: 0.1in figure=reference2.eps 0.1in The value null is represented by a dot with no arrow. exception!NullPointer run-time error If you try to use a null object, either by accessing an instance variable or invoking a method, you will get a NullPointerException. The system will print an error message and terminate the program. verbatim Point blank = null; int x = blank.x; // NullPointerException blank.translate (50, 50); // NullPointerException verbatim On the other hand, it is legal to pass a null object as an argument or receive one as a return value. In fact, it is common to do so, for example to represent an empty set or indicate an error condition. Garbage collection garbage collection In Section aliasing we talked about what happens when more than one variable refers to the same object. What happens when no variable refers to an object? For example: verbatim Point blank = new Point (3, 4); blank = null; verbatim The first line creates a new Point object and makes blank refer to it. The second line changes blank so that instead of referring to the object, it refers to nothing (the null object). 0.1in figure=reference3.eps 0.1in If no one refers to an object, then no one can read or write any of its values, or invoke a method on it. In effect, it ceases to exist. We could keep the object in memory, but it would only waste space, so periodically as your program runs, the Java system looks for stranded objects and reclaims them, in a process called garbage collection. Later, the memory space occupied by the object will be available to be used as part of a new object. You don't have to do anything to make garbage collection work, and in general you will not be aware of it. Objects and primitives type!object type!primitive object type primitive type There are two kinds of types in Java, primitive types and object types. Primitives, like int and boolean begin with lower-case letters; object types begin with upper-case letters. This distinction is useful because it reminds us of some of the differences between them: itemize When you declare a primitive variable, you get storage space for a primitive value. When you declare an object variable, you get a space for a reference to an object. In order to get space for the object itself, you have to use the new command. If you don't initialize a primitive type, it is given a default value that depends on the type. For example, 0 for ints and true for booleans. The default value for object types is null, which indicates no object. Primitive variables are well isolated in the sense that there is nothing you can do in one method that will affect a variable in another method. Object variables can be tricky to work with because they are not as well isolated. If you pass a reference to an object as an argument, the method you invoke might modify the object, in which case you will see the effect. The same is true when you invoke a method on an object. Of course, that can be a good thing, but you have to be aware of it. itemize There is one other difference between primitives and object types. You cannot add new primitives to the Java language (unless you get yourself on the standards committee), but you can create new object types. We'll see how in the next chapter. Glossary description [package:] A collection of classes. The built-in Java classes are organized in packages. [AWT:] The Abstract Window Toolkit, one of the biggest and most commonly-used Java packages. [instance:] An example from a category. My cat is an instance of the category ``feline things.'' Every object is an instance of some class. [instance variable:] One of the named data items that make up an object. Each object (instance) has its own copy of the instance variables for its class. [reference:] A value that indicates an object. In a state diagram, a reference appears as an arrow. [aliasing:] The condition when two or more variables refer to the same object. [garbage collection:] The process of finding objects that have no references and reclaiming their storage space. [state:] A complete description of all the variables and objects and their values, at a given point during the execution of a program. [state diagram:] A snapshot of the state of a program, shown graphically. package AWT instance instance variable reference aliasing garbage collection state state diagram description User-defined objects Class definitions and object types classes type!object type!user-defined object type class definition user-defined type Every time you write a class definition, you create a new Object type, with the same name as the class. In the previous chapter, when we defined the class named Hello, we also created an object type named Hello. We didn't create any variables with type Hello, and we didn't use the new command to create any Hello objects, but we could have! That example may not make any sense, since there is no reason to create a Hello object, and it is not clear what it would be good for if we did. In this chapter, we will look at some examples of class definitions that create useful new Object types. Here are the most important ideas in this chapter: itemize Defining a new class also creates a new object type with the same name. A class definition is like a template for objects: it determines what instance variables the objects have and what methods can operate on them. Every object belongs to some object type; hence, it is an instance of some class. When you invoke the new command to create an object, Java invokes a special method called a constructor to initialize the instance variables. You provide one or more constructors as part of the class definition. Typically all the methods that operate on a type go in the class definition for that type. itemize Here are some syntax issues about class definitions: itemize Class names (and hence object types) always begin with a capital letter, which helps distinguish them from primitive types and variable names. You usually put one class definition in each file, and the name of the file must be the same as the name of the class, with the suffix .java. For example, the Time class is defined in the file named Time.java. In any program, one class is designated as the startup class. The startup class must contain a method named main, which is where the execution of the program begins. Other classes may have a method named main, but they will not be executed. itemize With those issues out of the way, let's look at an example of a user-defined type, Time. Time time class!Time Time A common motivation for creating a new Object type is to take several related pieces of data and encapsulate them into an object that can be manipulated (passed as an argument, operated on) as a single unit. We have already seen two built-in types like this, Point and Rectangle. Another example, which we will implement ourselves, is Time, which is used to record the time of day. The various pieces of information that form a time are the hour, minute and second. Because every Time object will contain these data, we need to create instance variables to hold them. The first step is to decide what type each variable should be. It seems clear that hour and minute should be integers. Just to keep things interesting, let's make second a double, so we can record fractions of a second. instance variable variable!instance Instance variables are declared at the beginning of the class definition, outside of any method definition, like this: verbatim class Time int hour, minute; double second; verbatim All by itself, this code fragment is a legal class definition. The state diagram for a Time object would look like this: 0.1in figure=time.eps 0.1in After declaring the instance variables, the next step is usually to define a constructor for the new class. Constructors constructor method!constructor static The usual role of a constructor is to initialize the instance variables. The syntax for constructors is similar to that of other methods, with three exceptions: itemize The name of the constructor is the same as the name of the class. Constructors have no return type and no return value. The keyword static is omitted. itemize Here is an example for the Time class: verbatim public Time () this.hour = 0; this.minute = 0; this.second = 0.0; verbatim Notice that where you would expect to see a return type, between public and Time, there is nothing. That's how we (and the compiler) can tell that this is a constructor. This constructor does not take any arguments, as indicated by the empty parentheses (). Each line of the constructor initializes an instance variable to an arbitrary default value (in this case, midnight). The name this is a special keyword that is the name of the object we are creating. You can use this the same way you use the name of any other object. For example, you can read and write the instance variables of this, and you can pass this as an argument to other methods. this But you do not declare this and you do not use new to create it. In fact, you are not even allowed to make an assignment to it! this is created by the system; all you have to do is store values in its instance variables. A common error when writing constructors is to put a return statement at the end. Resist the temptation. More constructors overloading Constructors can be overloaded, just like other methods, which means that you can provide multiple constructors with different parameters. Java knows which constructor to invoke by matching the arguments of the new command with the parameters of the constructors. It is very common to have one constructor that takes no arguments (shown above), and one constructor that takes a parameter list that is identical to the list of instance variables. For example: verbatim public Time (int hour, int minute, double second) this.hour = hour; this.minute = minute; this.second = second; verbatim The names and types of the parameters are exactly the same as the names and types of the instance variables. All the constructor does is copy the information from the parameters to the instance variables. If you go back and look at the documentation for Points and Rectangles, you will see that both classes provide constructors like this. Overloading constructors provides the flexibility to create an object first and then fill in the blanks, or to collect all the information before creating the object. So far this might not seem very interesting, and in fact it is not. Writing constructors is a boring, mechanical process. Once you have written two, you will find that you can churn them out in your sleep, just by looking at the list of instance variables. Creating a new object new statement!new Although constructors look like methods, you never invoke them directly. Instead, when you use the new command, the system allocates space for the new object and then invokes your constructor to initialize the instance variables. The following program demonstrates two ways to create and initialize Time objects: verbatim class Time int hour, minute; double second; public Time () this.hour = 0; this.minute = 0; this.second = 0.0; public Time (int hour, int minute, double second) this.hour = hour; this.minute = minute; this.second = second; public static void main (String[] args) // one way to create and initialize a Time object Time t1 = new Time (); t1.hour = 11; t1.minute = 8; t1.second = 3.14159; System.out.println (t1); // another way to do the same thing Time t2 = new Time (11, 8, 3.14159); System.out.println (t2); verbatim As an exercise, figure out the flow of execution through this program. In main, the first time we invoke the new command, we provide no arguments, so Java invokes the first constructor. The next few lines assign values to each of the instance variables. The second time we invoke the new command, we provide arguments that match the parameters of the second constructor. This way of initializing the instance variables is more concise (and slightly more efficient), but it can be harder to read, since it is not as clear which values are assigned to which instance variables. Printing an object printobject print statement!print object!printing The output of this program is: verbatim Time@80cc7c0 Time@80cc807 verbatim When Java prints the value of a user-defined object type, it prints the name of the type and a special hexadecimal (base 16) code that is unique for each object. This code is not meaningful in itself; in fact, it can vary from machine to machine and even from run to run. But it can be useful for debugging, in case you want to keep track of individual objects. In order to print objects in a way that is more meaningful to users (as opposed to programmers), you usually want to write a method called something like printTime: verbatim public static void printTime (Time t) System.out.println (t.hour + ":" + t.minute + ":" + t.second); verbatim The output of this method, if we pass either t1 or t2 as an argument, is 11:8:3.14159. Although this is recognizable as a time, it is not quite in the standard format. For example, if the number of minutes or seconds is less than 10, we expect a leading 0 as a place-keeper. Also, we might want to drop the decimal part of the seconds. In other words, we want something like 11:08:03. In most languages, there are simple ways to control the output format for numbers. In Java there are no simple ways. Java provides very powerful tools for printing formatted things like times and dates, and also for interpreting formatted input. Unfortunately, these tools are not very easy to use, so I am going to leave them out of this book. If you want, though, you can take a look at the documentation for the Date class in the java.util package. Date class!Date Operations on objects objectops object operator!object Even though we can't print times in an optimal format, we can still write methods that manipulate Time objects. In the next few sections, I will demonstrate several of the possible interfaces for methods that operate on objects. For some operations, you will have a choice of several possible interfaces, so you should consider the pros and cons of each of these: description [pure function:] Takes objects and/or primitives as arguments but does not modify the objects. The return value is either a primitive or a new object created inside the method. [modifier:] Takes objects as arguments and modifies some or all of them. Often returns void. void [fill-in method:] One of the arguments is an ``empty'' object that gets filled in by the method. Technically, this is a type of modifier. description Pure functions pure function function method!pure function A method is considered a pure function if the result depends only on the arguments, and it has no side effects like modifying an argument or printing something. The only result of invoking a pure function is the return value. One example is after, which compares two Times and returns a boolean that indicates whether the first operand comes after the second: verbatim public static boolean after (Time time1, Time time2) if (time1.hour > time2.hour) return true; if (time1.hour < time2.hour) return false; if (time1.minute > time2.minute) return true; if (time1.minute < time2.minute) return false; if (time1.second > time2.second) return true; return false; verbatim What is the result of this method if the two times are equal? Does that seem like the appropriate result for this method? If you were writing the documentation for this method, would you mention that case specifically? A second example is addTime, which calculates the sum of two times. For example, if it is 9:14:30, and your breadmaker takes 3 hours and 35 minutes, you could use addTime to figure out when the bread will be done. Here is a rough draft of this method that is not quite right: verbatim public static Time addTime (Time t1, Time t2) Time sum = new Time (); sum.hour = t1.hour + t2.hour; sum.minute = t1.minute + t2.minute; sum.second = t1.second + t2.second; return sum; verbatim Although this method returns a Time object, it is not a constructor. You should go back and compare the syntax of a method like this with the syntax of a constructor, because it is easy to get confused. Here is an example of how to use this method. If currentTime contains the current time and breadTime contains the amount of time it takes for your breadmaker to make bread, then you could use addTime to figure out when the bread will be done. verbatim Time currentTime = new Time (9, 14, 30.0); Time breadTime = new Time (3, 35, 0.0); Time doneTime = addTime (currentTime, breadTime); printTime (doneTime); verbatim The output of this program is 12:49:30.0, which is correct. On the other hand, there are cases where the result is not correct. Can you think of one? The problem is that this method does not deal with cases where the number of seconds or minutes adds up to more than 60. In that case, we have to ``carry'' the extra seconds into the minutes column, or extra minutes into the hours column. Here's a second, corrected version of this method. verbatim public static Time addTime (Time t1, Time t2) Time sum = new Time (); sum.hour = t1.hour + t2.hour; sum.minute = t1.minute + t2.minute; sum.second = t1.second + t2.second; if (sum.second >= 60.0) sum.second -= 60.0; sum.minute += 1; if (sum.minute >= 60) sum.minute -= 60; sum.hour += 1; return sum; verbatim Although it's correct, it's starting to get big. Later, I will suggest an alternate approach to this problem that will be much shorter. increment decrement operator!increment operator!decrement This code demonstrates two operators you may not have seen, += and -=. These operators provide a concise way to increment and decrement variables. They are similar to ++ and --, except (1) they work on doubles as well as ints, and (2) the amount of the increment does not have to be 1. The statement sum.second -= 60.0; is equivalent to sum.second = sum.second - 60; Modifiers modifier method!modifier As an example of a modifier, consider increment, which adds a given number of seconds to a Time object. Again, a rough draft of this method looks like: verbatim public static void increment (Time time, double secs) time.second += secs; if (time.second >= 60.0) time.second -= 60.0; time.minute += 1; if (time.minute >= 60) time.minute -= 60; time.hour += 1; verbatim The first line performs the basic operation; the remainder deals with the same cases we saw before. Is this method correct? What happens if the argument secs is much greater than 60? In that case, it is not enough to subtract 60 once; we have to keep doing it until second is below 60. We can do that by simply replacing the if statements with while statements: verbatim public static void increment (Time time, double secs) time.second += secs; while (time.second >= 60.0) time.second -= 60.0; time.minute += 1; while (time.minute >= 60) time.minute -= 60; time.hour += 1; verbatim This solution is correct, but not very efficient. Can you think of a solution that does not require iteration? Fill-in methods fill-in method method!fill-in Occasionally you will see methods like addTime written with a different interface (different arguments and return values). Instead of creating a new object every time addTime is invoked, we could require the caller to provide an ``empty'' object where addTime should store the result. Compare the following with the previous version: verbatim public static void addTimeFill (Time t1, Time t2, Time sum) sum.hour = t1.hour + t2.hour; sum.minute = t1.minute + t2.minute; sum.second = t1.second + t2.second; if (sum.second >= 60.0) sum.second -= 60.0; sum.minute += 1; if (sum.minute >= 60) sum.minute -= 60; sum.hour += 1; verbatim One advantage of this approach is that the caller has the option of reusing the same object repeatedly to perform a series of additions. This can be slightly more efficient, although it can be confusing enough to cause subtle errors. For the vast majority of programming, it is worth a spending a little run time to avoid a lot of debugging time. Which is best? programming style Anything that can be done with modifiers and fill-in methods can also be done with pure functions. In fact, there are programming languages, called functional programming languages, that only allow pure functions. Some programmers believe that programs that use pure functions are faster to develop and less error-prone than programs that use modifiers. Nevertheless, there are times when modifiers are convenient, and some cases where functional programs are less efficient. In general, I recommend that you write pure functions whenever it is reasonable to do so, and resort to modifiers only if there is a compelling advantage. This approach might be called a functional programming style. Incremental development vs. planning incremental development prototyping program development!incremental program development!planning In this chapter I have demonstrated an approach to program development I refer to as rapid prototyping with iterative improvement. In each case, I wrote a rough draft (or prototype) that performed the basic calculation, and then tested it on a few cases, correcting flaws as I found them. Although this approach can be effective, it can lead to code that is unnecessarily complicated---since it deals with many special cases---and unreliable---since it is hard to convince yourself that you have found all the errors. An alternative is high-level planning, in which a little insight into the problem can make the programming much easier. In this case the insight is that a Time is really a three-digit number in base 60! The second is the ``ones column,'' the minute is the ``60's column'', and the hour is the ``3600's column.'' When we wrote addTime and increment, we were effectively doing addition in base 60, which is why we had to ``carry'' from one column to the next. arithmetic!floating-point Thus an alternate approach to the whole problem is to convert Times into doubles and take advantage of the fact that the computer already knows how to do arithmetic with doubles. Here is a method that converts a Time into a double: verbatim public static double convertToSeconds (Time t) int minutes = t.hour * 60 + t.minute; double seconds = minutes * 60 + t.second; return seconds; verbatim Now all we need is a way to convert from a double to a Time object. We could write a method to do it, but it might make more sense to write it as a third constructor: verbatim public Time (double secs) this.hour = (int) (secs / 3600.0); secs -= this.hour * 3600.0; this.minute = (int) (secs / 60.0); secs -= this.minute * 60; this.second = secs; verbatim This constructor is a little different from the others, since it involves some calculation along with assignments to the instance variables. You might have to think a bit to convince yourself that the technique I am using to convert from one base to another is correct. Assuming you are convinced, we can use these methods to rewrite addTime: verbatim public static Time addTime (Time t1, Time t2) double seconds = convertToSeconds (t1) + convertToSeconds (t2); return new Time (seconds); verbatim This is much shorter than the original version, and it is much easier to demonstrate that it is correct (assuming, as usual, that the methods it invokes are correct). As an exercise, rewrite increment the same way. Generalization generalization In some ways converting from base 60 to base 10 and back is harder than just dealing with times. Base conversion is more abstract; our intuition for dealing with times is better. But if we have the insight to treat times as base 60 numbers, and make the investment of writing the conversion methods (convertToSeconds and the third constructor), we get a program that is shorter, easier to read and debug, and more reliable. It is also easier to add more features later. For example, imagine subtracting two Times to find the duration between them. The naive approach would be to implement subtraction complete with ``borrowing.'' Using the conversion methods would be much easier. Ironically, sometimes making a problem harder (more general) makes is easier (fewer special cases, fewer opportunities for error). Algorithms algorithm algorithm When you write a general solution for a class of problems, as opposed to a specific solution to a single problem, you have written an algorithm. This word is not easy to define, so I will try a couple of approaches. First, consider some things that are not algorithms. For example, when you learned to multiply single-digit numbers, you probably memorized the multiplication table. In effect, you memorized 100 specific solutions, so that knowledge is not really algorithmic. But if you were ``lazy,'' you probably cheated by learning a few tricks. For example, to find the product of and 9, you can write as the first digit and as the second digit. This trick is a general solution for multiplying any single-digit number by 9. That's an algorithm! Similarly, the techniques you learned for addition with carrying, subtraction with borrowing, and long division are all algorithms. One of the characteristics of algorithms is that they do not require any intelligence to carry out. They are mechanical processes in which each step follows from the last according to a simple set of rules. In my opinion, it is embarrassing that humans spend so much time in school learning to execute algorithms that, quite literally, require no intelligence. On the other hand, the process of designing algorithms is interesting, intellectually challenging, and a central part of what we call programming. Some of the things that people do naturally, without difficulty or conscious thought, are the most difficult to express algorithmically. Understanding natural language is a good example. We all do it, but so far no one has been able to explain how we do it, at least not in the form of an algorithm. Later in this class, you will have the opportunity to design simple algorithms for a variety of problems. If you take the next class in the Computer Science sequence, Data Structures, you will see some of the most interesting, clever, and useful algorithms computer science has produced. Glossary description [class:] Previously, I defined a class as a collection of related methods. In this chapter we learned that a class definition is also a template for a new type of object. [instance:] A member of a class. Every object is an instance of some class. [constructor:] A special method that initializes the instance variables of a newly-constructed object. [project:] A collection of one or more class definitions (one per file) that make up a program. [startup class:] The class that contains the main method where execution of the program begins. [function:] A method whose result depends only on its parameters, and that has so side-effects other than returning a value. [functional programming style:] A style of program design in which the majority of methods are functions. [modifier:] A method that changes one or more of the objects it receives as parameters, and usually returns void. [fill-in method:] A type of method that takes an ``empty'' object as a parameter and fills it its instance variables instead of generating a return value. This type of method is usually not the best choice. [algorithm:] A set of instructions for solving a class of problems by a mechanical, unintelligent process. class instance constructor project startup class function functional programming modifier algorithm description Arrays arrays array type!array An array is a set of values where each value is identified by an index. You can make an array of ints, doubles, or any other type, but all the values in an array have to have the same type. Syntactically, array types look like other Java types except they are followed by []. For example, int[] is the type ``array of integers'' and double[] is the type ``array of doubles.'' You can declare variables with these types in the usual ways: verbatim int[] count; double[] values; verbatim Until you initialize these variables, they are set to null. To create the array itself, use the new command. verbatim count = new int[4]; values = new double[size]; verbatim The first assignment makes count refer to an array of 4 integers; the second makes values refer to an array of doubles. The number of elements in values depends on size. You can use any integer expression as an array size. null state diagram The following figure shows how arrays are represented in state diagrams: 0.1in figure=array.eps 0.1in The large numbers inside the boxes are the elements of the array. The small numbers outside the boxes are the indices used to identify each box. When you allocate a new array, the elements are initialized to zero. Accessing elements element array!element To store values in the array, use the [] operator. For example count[0] refers to the ``zeroeth'' element of the array, and count[1] refers to the ``oneth'' element. You can use the [] operator anywhere in an expression: verbatim count[0] = 7; count[1] = count[0] * 2; count[2]++; count[3] -= 60; verbatim All of these are legal assignment statements. Here is the effect of this code fragment: 0.1in figure=array2.eps 0.1in By now you should have noticed that the four elements of this array are numbered from 0 to 3, which means that there is no element with the index 4. This should sound familiar, since we saw the same thing with String indices. Nevertheless, it is a common error to go beyond the bounds of an array, which will cause an ArrayOutOfBoundsException. As with all exceptions, you get an error message and the program quits. exception!ArrayOutOfBounds run-time error index expression You can use any expression as an index, as long as it has type int. One of the most common ways to index an array is with a loop variable. For example: verbatim int i = 0; while (i < 4) System.out.println (count[i]); i++; verbatim This is a standard while loop that counts from 0 up to 4, and when the loop variable i is 4, the condition fails and the loop terminates. Thus, the body of the loop is only executed when i is 0, 1, 2 and 3. loop loop variable variable!loop Each time through the loop we use i as an index into the array, printing the ith element. This type of array traversal is very common. Arrays and loops go together like fava beans and a nice Chianti. Copying arrays array!copying When you copy an array variable, remember that you are copying a reference to the array. For example: verbatim double[] a = new double [3]; double[] b = a; verbatim This code creates one array of three doubles, and sets two different variables to refer to it. This situation is a form of aliasing. 0.1in figure=array3.eps 0.1in Any changes in either array will be reflected in the other. This is not usually the behavior you want; instead, you should make a copy of the array, by allocating a new array and copying each element from one to the other. verbatim double[] b = new double [3]; int i = 0; while (i < 4) b[i] = a[i]; i++; verbatim for loops The loops we have written so far have a number of elements in common. All of them start by initializing a variable; they have a test, or condition, that depends on that variable; and inside the loop they do something to that variable, like increment it. loop!for for statement!for This type of loop is so common that there is an alternate loop statement, called for, that expresses it more concisely. The general syntax looks like this: verbatim for (INITIALIZER; CONDITION; INCREMENTOR) BODY verbatim This statement is exactly equivalent to verbatim INITIALIZER; while (CONDITION) BODY INCREMENTOR verbatim except that it is more concise and, since it puts all the loop-related statements in one place, it is easier to read. For example: verbatim for (int i = 0; i < 4; i++) System.out.println (count[i]); verbatim is equivalent to verbatim int i = 0; while (i < 4) System.out.println (count[i]); i++; verbatim As an exercise, write a for loop to copy the elements of an array. Arrays and objects object!compared to array array!compared to object In many ways, arrays behave like objects: itemize When you declare an array variable, you get a reference to an array. You have to use the new command to create the array itself. When you pass an array as an argument, you pass a reference, which means that the invoked method can change the contents of the array. itemize Some of the objects we have looked at, like Rectangles, are similar to arrays, in the sense that they are named collection of values. This raises the question, ``How is an array of 4 integers different from a Rectangle object?'' If you go back to the definition of ``array'' at the beginning of the chapter, you will see one difference, which is that the elements of an array are identified by indices, whereas the elements (instance variables) of an object have names (like x, width, etc.). Another difference between arrays and objects is that all the elements of an array have to be the same type. Although that is also true of Rectangles, we have seen other objects that have instance variables with different types (like Time). Array length length!array array!length Actually, arrays do have one named instance variable: length. Not surprisingly, it contains the length of the array (number of elements). It is a good idea to use this value as the upper bound of a loop, rather than a constant value. That way, if the size of the array changes, you won't have to go through the program changing all the loops; they will work correctly for any size array. verbatim for (int i = 0; i < a.length; i++) b[i] = a[i]; verbatim The last time the body of the loop gets executed, i is a.length - 1, which is the index of the last element. When i is equal to a.length, the condition fails and the body is not executed, which is a good thing, since it would cause an exception. This code assumes that the array b contains at least as many elements as a. As an exercise, write a method called cloneArray that takes an array of integers as a parameter, creates a new array that is the same size, copies the elements from the first array into the new one, and then returns a reference to the new array. Random numbers random pseudorandom random number deterministic nondeterministic Most computer programs do the same thing every time they are executed, so they are said to be deterministic. Usually, determinism is a good thing, since we expect the same calculation to yield the same result. For some applications, though, we would like the computer to be unpredictable. Games are an obvious example, but there are many more. Making a program truly nondeterministic turns out to be not so easy, but there are ways to make it at least seem nondeterministic. One of them is to generate random numbers and use them to determine the outcome of the program. Java provides a built-in method that generates pseudorandom numbers, which are not truly random in the mathematical sense, but for our purposes, they will do. Check out the documentation of the random method in the Math class. The return value is a double between 0.0 and 1.0. Each time you invoke random you get a different randomly-generated number. To see a sample, run this loop: verbatim for (int i = 0; i < 10; i++) double x = Math.random (); System.out.println (x); verbatim To generate a random double between 0.0 and an upper bound like high, you can multiply x by high. How would you generate a random number between low and high? How would you generate a random integer? Statistics statistics distribution mean The numbers generated by random are supposed to be distributed uniformly. If you have taken statistics, you know what that means. Among other things, it means that if we divide the range of possible values into equal sized ``buckets,'' and count the number of times a random value falls in each bucket, each bucket should get the same number of hits (eventually). In the next few sections, we will write programs that generate a sequence of random numbers and check whether this property holds true. Array of random numbers The first step is to generate a large number of random values and store them in an array. By ``large number,'' of course, I mean 8. It's always a good idea to start with a manageable number, to help with debugging, and then increase it later. The following method takes a single argument, the size of the array. It allocates a new array of doubles, fills it with random values, and returns a reference to the new array. verbatim public static double[] randomArray (int n) double[] a = new double[n]; for (int i = 0; i= low && a[i] < high) count++; return count; verbatim I haven't been very careful about whether something equal to low or high falls in the bucket, but you can see from the code that low is in and high is out. That should prevent me from counting any elements twice. Now, to divide the range into two pieces, we could write verbatim int low = inBucket (a, 0.0, 0.5); int high = inBucket (a, 0.5, 1.0); verbatim To divide it into four pieces: verbatim int bucket1 = inBucket (a, 0.0, 0.25); int bucket2 = inBucket (a, 0.25, 0.5); int bucket3 = inBucket (a, 0.5, 0.75); int bucket4 = inBucket (a, 0.75, 1.0); verbatim You might want to try out this program using a larger numValues. As numValues increases, are the numbers in each bucket levelling off? Many buckets bucket histogram Of course, as the number of buckets increases, we don't want to have to rewrite the program, especially since the code is getting big and repetitive. Any time you find yourself doing something more than a few times, you should be looking for a way to automate it. Let's say that we wanted 8 buckets. The width of each bucket would be one eighth of the range, which is 0.125. To count the number of values in each bucket, we need to be able to generate the bounds of each bucket automatically, and we need to have some place to store the 8 counts. We can solve the first problem with a loop: verbatim int numBuckets = 8; double bucketWidth = 1.0 / numBuckets; for (int i = 0; i < numBuckets; i++) double low = i * bucketWidth; double high = low + bucketWidth; System.out.println (low + " to " + high); verbatim This code uses the loop variable i to multiply by the bucket width, in order to find the low end of each bucket. The output of this loop is: verbatim 0.0 to 0.125 0.125 to 0.25 0.25 to 0.375 0.375 to 0.5 0.5 to 0.625 0.625 to 0.75 0.75 to 0.875 0.875 to 1.0 verbatim You can confirm that each bucket is the same width, that they don't overlap, and that they cover the whole range from 0.0 to 1.0. Now we just need a way to store 8 integers, preferably so we can use an index to access each one. Immediately, you should be thinking ``array!'' What we want is an array of 8 integers, which we can allocate outside the loop; then, inside the loop, we'll invoke inBucket and store the result: verbatim int numBuckets = 8; int[] buckets = new int [8]; double bucketWidth = 1.0 / numBuckets; for (int i = 0; i and the others) don't work for object types. For Strings there is a built-in compare method. For Cards we have to write our own, which we will call compareCard. Later, we will use this method to sort a deck of cards. ordering complete ordering partial ordering Some sets are completely ordered, which means that you can compare any two elements and tell which is bigger. For example, the integers and the floating-point numbers are totally ordered. Some sets are unordered, which means that there is no meaningful way to say that one element is bigger than another. For example, the fruits are unordered, which is why we cannot compare apples and oranges. In Java, the boolean type is unordered; we cannot say that true is greater than false. The set of playing cards is partially ordered, which means that sometimes we can compare cards and sometimes not. For example, I know that the 3 of Clubs is higher than the 2 of Clubs, and the 3 of Diamonds is higher than the 3 of Clubs. But which is better, the 3 of Clubs or the 2 of Diamonds? One has a higher rank, but the other has a higher suit. comparable In order to make cards comparable, we have to decide which is more important, rank or suit. The choice is completely arbitrary, but for the sake of choosing, I will say that suit is more important. As evidence, I would point out that when you buy a new deck of cards, it comes sorted with all the Clubs together, followed by all the Diamonds, and so on. With that decided, we can write compareCard. It will take two Cards as parameters and return 1 if the first card wins, -1 if the second card wins, and 0 if they tie (indicating deep equality). It is sometimes confusing to keep those return values straight, but they are pretty standard for comparison methods. First we compare the suits: verbatim if (c1.suit > c2.suit) return 1; if (c1.suit < c2.suit) return -1; verbatim If neither statement is true, then the suits must be equal, and we have to compare ranks: verbatim if (c1.rank > c2.rank) return 1; if (c1.rank < c2.rank) return -1; verbatim If neither of these is true, the ranks must be equal, so we return 0. In this ordering, aces will appear lower than deuces (2s). As an exercise, fix it so that aces are ranked higher than Kings, and encapsulate this code in a method. Arrays of cards array!of object object!array of deck The reason I chose Cards as the objects for this chapter is that there is an obvious use for an array of cards---a deck. Here is some code that creates a new deck of 52 cards: verbatim Card[] deck = new Card [52]; verbatim Here is the state diagram for this object: state diagram 0.1in figure=cardarray.eps 0.1in The important thing to see here is that the array contains only references to objects; it does not contain any Card objects. The values of the array elements are initialized to null. You can access the elements of the array in the usual way: verbatim if (deck[3] == null) System.out.println ("No cards yet!"); verbatim But if you try to access the instance variables of the non-existent Cards, you will get a NullPointerException. exception!NullPointer run-time error null verbatim deck[2].rank; // NullPointerException verbatim Nevertheless, that is the correct syntax for accessing the rank of the ``twoeth'' card in the deck (really the third---we started at zero, remember?). This is another example of composition, the combination of the syntax for accessing an element of an array and an instance variable of an object. composition loop!nested The easiest way to populate the deck with Card objects is to write a nested loop: verbatim int index = 0; for (int suit = 0; suit <= 3; suit++) for (int rank = 1; rank <= 13; rank++) deck[index] = new Card (suit, rank); index++; verbatim The outer loop enumerates the suits, from 0 to 3. For each suit, the inner loop enumerates the ranks, from 1 to 13. Since the outer loop iterates 4 times, and the inner loop iterates 13 times, the total number of times the body is executed is 52 (13 times 4). index I used the variable index to keep track of where in the deck the next card should go. The following state diagram shows what the deck looks like after the first two cards have been allocated: 0.1in figure=cardarray2.eps 0.1in As an exercise, encapsulate this deck-building code in a method called buildDeck that takes no parameters and that returns a fully-populated array of Cards. encapsulation The printDeck method printdeck printDeck print!array of Cards Whenever you are working with arrays, it is convenient to have a method that will print the contents of the array. We have seen the pattern for traversing an array several times, so the following method should be familiar: verbatim public static void printDeck (Card[] deck) for (int i=0; i 0) return findBisect (deck, card, low, mid-1); else return findBisect (deck, card, mid+1, high); verbatim Rather than call compareCard three times, I called it once and stored the result. Although this code contains the kernel of a bisection search, it is still missing a piece. As it is currently written, if the card is not in the deck, it will recurse forever. We need a way to detect this condition and deal with it properly (by returning -1). recursion The easiest way to tell that your card is not in the deck is if there are no cards in the deck, which is the case if high is less than low. Well, there are still cards in the deck, of course, but what I mean is that there are no cards in the segment of the deck indicated by low and high. With that line added, the method works correctly: verbatim public static int findBisect (Card[] deck, Card card, int low, int high) System.out.println (low + ", " + high); if (high < low) return -1; int mid = (high + low) / 2; int comp = deck[mid].compareCard (card); if (comp == 0) return mid; else if (comp > 0) return findBisect (deck, card, low, mid-1); else return findBisect (deck, card, mid+1, high); verbatim I added a print statement at the beginning so I could watch the sequence of recursive calls and convince myself that it would eventually reach the base case. I tried out the following code: verbatim Card card1 = new Card (1, 11); System.out.println (findBisect (deck, card1, 0, 51)); verbatim And got the following output: verbatim 0, 51 0, 24 13, 24 19, 24 22, 24 23 verbatim Then I made up a card that is not in the deck (the 15 of Diamonds), and tried to find it. I got the following: verbatim 0, 51 0, 24 13, 24 13, 17 13, 14 13, 12 -1 verbatim These tests don't prove that this program is correct. In fact, no amount of testing can prove that a program is correct. On the other hand, by looking at a few cases and examining the code, you might be able to convince yourself. testing correctness The number of recursive calls is fairly small, typically 6 or 7. That means we only had to invoke compareCard 6 or 7 times, compared to up to 52 times if we did a linear search. In general, bisection is much faster than a linear search, especially for large arrays. Two common errors in recusive programs are forgetting to include a base case and writing the recursive call so that the base case is never reached. Either error will cause an infinite recursion, in which case Java will (eventually) throw a StackOverflowException. recursion!infinite infinite recursion exception!StackOverflow Decks and subdecks deck subdeck Looking at the interface to findBisect verbatim public static int findBisect (Card[] deck, Card card, int low, int high) verbatim it might make sense to treat three of the parameters, deck, low and high, as a single parameter that specifies a subdeck. parameter!abstract abstract parameter This kind of thing is quite common, and I sometimes think of it as an abstract parameter. What I mean by ``abstract,'' is something that is not literally part of the program text, but which describes the function of the program at a higher level. For example, when you invoke a method and pass an array and the bounds low and high, there is nothing that prevents the invoked method from accessing parts of the array that are out of bounds. So you are not literally sending a subset of the deck; you are really sending the whole deck. But as long as the recipient plays by the rules, it makes sense to think of it, abstractly, as a subdeck. There is one other example of this kind of abstraction that you might have noticed in Section objectops, when I referred to an ``empty'' data structure. The reason I put ``empty'' in quotation marks was to suggest that it is not literally accurate. All variables have values all the time. When you create them, they are given default values. So there is no such thing as an empty object. But if the program guarantees that the current value of a variable is never read before it is written, then the current value is irrelevant. Abstractly, it makes sense to think of such a variable as ``empty.'' This kind of thinking, in which a program comes to take on meaning beyond what is literally encoded, is a very important part of thinking like a computer scientist. Sometimes, the word ``abstract'' gets used so often and in so many contexts that it comes to lose its meaning. Nevertheless, abstraction is a central idea in computer science (as well as many other fields). abstraction A more general definition of ``abstraction'' is ``The process of modeling a complex system with a simplified description in order to suppress unnecessary details while capturing relevant behavior.'' Glossary description [encode:] To represent one set of values using another set of values, by constructing a mapping between them. [shallow equality:] Equality of references. Two references that point to the same object. [deep equality:] Equality of values. Two references that point to objects that have the same value. [abstract parameter:] A set of parameters that act together as a single parameter. [abstraction:] The process of interpreting a program (or anything else) at a higher level than what is literally represented by the code. encode shallow equality deep equality abstract parameter abstraction description Objects of Arrays deck deck array!of Cards In the previous chapter, we worked with an array of objects, but I also mentioned that it is possible to have an object that contains an array as an instance variable. In this chapter I am going to create a new object, called a Deck, that contains an array of Cards as an instance variable. instance variable variable!instance The class definition looks like this verbatim class Deck Card[] cards; public Deck (int n) cards = new Card[n]; verbatim The name of the instance variable is cards to help distinguish the Deck object from the array of Cards that it contains. Here is a state diagram showing what a Deck object looks like with no cards allocated: state diagram constructor 0.2in figure=deckobject.eps 0.2in As usual, the constructor initializes the instance variable, but in this case it uses the new command to create the array of cards. It doesn't create any cards to go in it, though. For that we could write another constructor that creates a standard 52-card deck and populates it with Card objects: verbatim public Deck () cards = new Card[52]; int index = 0; for (int suit = 0; suit <= 3; suit++) for (int rank = 1; rank <= 13; rank++) cards[index] = new Card (suit, rank); index++; verbatim Notice how similar this method is to buildDeck, except that we had to change the syntax to make it a constructor. To invoke it, we use the new command: new statement!new verbatim Deck deck = new Deck (); verbatim Now that we have a Deck class, it makes sense to put all the methods that pertain to Decks in the Deck class definition. Looking at the methods we have written so far, one obvious candidate is printDeck (Section printdeck). Here's how it looks, rewritten to work with a Deck object: printDeck verbatim public static void printDeck (Deck deck) for (int i=0; i 0) maxIndex = i; Comparable result = array[maxIndex]; // move the last item into the empty slot index--; array[maxIndex] = array[index]; return result; verbatim As we traverse the array, maxIndex keeps track of the index of the largest element we have seen so far. What it means to be the ``largest'' is determined by compareTo. In this case the compareTo method is provided by the Integer class, and it does what we expect---larger (more positive) numbers win. A Priority Queue client The implementation of Priority Queue is written entirely in terms of Comparable objects. But there is no such thing as a Comparable object! Go ahead, try to create one: verbatim Comparable comp = new Comparable (); // ERROR verbatim You'll get a compile-time message that says something like ``java.lang.Comparable is an interface. It can't be instantiated.'' In Java, abstract classes are called interfaces. I have avoided this word so far because it also means several other things, but now you have to know. Why can't abstract classes be instantiated? Because an abstract class only specifies requirements (you must have a compareTo method); it does not provide an implementation. To create a Comparable object, you have to create one of the objects that implements Comparable, like Integer. Then you can use that object anywhere a Comparable is called for. verbatim PriorityQueue pq = new PriorityQueue (); Integer item = new Integer (17); pq.insert (item); verbatim This code creates a new, empty Priority Queue and a new Integer object. Then it inserts the Integer into the queue. insert is expecting a Comparable as a parameter, so it is perfectly happy to take an Integer. If we try to pass a Rectangle, which does not implement Comparable, we get a compile-time message like, ``Incompatible type for method. Explicit cast needed to convert java.awt.Rectangle to java.lang.Comparable.'' That's the compiler telling us that if we want to make that conversion, we have to do it explicitly. We might try to do what it says: verbatim Rectangle rect = new Rectangle (); pq.insert ((Comparable) rect); verbatim But in that case we get a run-time error, a ClassCastException. When the Rectangle tries to pass as a Comparable, the run-time system checks whether it satisfies the requirements, and rejects it. So that proves that you can't fit a square peg in a round hole. To get items out of the queue, we have to reverse the process: verbatim while (!pq.empty ()) item = (Integer) pq.remove (); System.out.println (item); verbatim This loop removes all the items from the queue and prints them. We are assuming that the items in the queue are Integers. If they were not, we would get a ClassCastException. The Customer class Finally, let's looks at how we can make a new class that implements Comparable. As an example of something with an unusual definition of ``highest'' priority, we'll use golfers: verbatim public class Golfer implements Comparable String name; int score; public Golfer (String name, int score) this.name = name; this.score = score; verbatim The class definition and the constructor are pretty much the same as always; the difference is that we have to declare that Golfer implements Comparable. If we try to compile Golfer.java at this point, we get something like ``class Golfer must be declared abstract. It does not define int compareTo(java.lang.Object) from interface java.lang.Comparable.'' In other words, to be a Comparable, Golfer has to provide a method named compareTo. So let's write one: verbatim public int compareTo (Object obj) Golfer that = (Golfer) obj; int a = this.score; int b = that.score; // for golfers, low is good! if (ab) return -1; return 0; verbatim Two things here are a little surprising. First, the parameter is an Object. That's because in general the caller doesn't know what type the objects are that are being compared. For example, in PriorityQueue.java when we invoke compareTo, we pass a Comparable as a parameter. We don't have to know whether it is an Integer or a Golfer or whatever. Inside compareTo we have to convert the parameter from an Object to a Golfer. As usual, there is a risk when we do this kind of cast: if we cast to the wrong type we get an exception. Finally, we can create some golfers: verbatim Golfer tiger = new Golfer ("Tiger Woods", 61); Golfer phil = new Golfer ("Phil Mickelson", 72); Golfer hal = new Golfer ("Hal Sutton", 69); verbatim And put them in the queue: verbatim pq.insert (tiger); pq.insert (phil); pq.insert (hal); verbatim When we pull them out: verbatim while (!pq.empty ()) golfer = (Golfer) pq.remove (); System.out.println (golfer); verbatim They appear in descending order (for golfers): verbatim Tiger Woods 61 Hal Sutton 69 Phil Mickelson 72 verbatim When we switched from Integers to Golfers, we didn't have to make any changes in PriorityQueue.java at all. So we succeeded in maintaining a barrier between PriorityQueue and the classes that use it, allowing us to reuse the code without modification. Furthermore, we were able to give the client code control over the definition of compareTo, making this implementation of PriorityQueue more versatile. Glossary description [queue:] An ordered set of objects waiting for a service of some kind. [queueing discipline:] The rules that determine which member of a queue is removed next. [FIFO:] ``first in, first out,'' a queueing discipline in which the first member to arrive is the first to be removed. [priority queue:] a queueing discipline in which the each member has a priority determined by external factors. The member with the highest priority is the first to be removed. [Priority Queue:] An ADT that defines the operations one might perform on a priority queue. [veneer:] A class definition that implements an ADT with method definitions that are invocations of other methods, sometimes with simple transformations. The veneer do no significant work, but it improves or standardizes the interface seen by the client. [performance hazard:] A danger associated with a veneer that some of the methods might be implemented inefficiently in a way that is not apparent to the client. [linked queue:] An implementation of a queue using a linked list and references to the first and last nodes. [circular buffer:] An implementation of a queue using an array and indices of the first element and the next available space. [abstract class:] A set of classes. The abstract class specification lists the requirements a class must satisfy to be included in the set. [interface:] The Java word for an abstract class. Not to be confused with the more broad meaning of the word interface. description Trees This chapter presents a new data structure called a tree, some of its uses and two ways to implement it. A possible source of confusion is the distinction between an ADT, a data structure, and an implementation of an ADT or data structure. There is no universal answer, because something that is an ADT at one level might in turn be the implementation of another ADT. To help keep some of this straight, it is sometimes useful to draw a diagram showing the relationship between an ADT and its possible implementations. This figure shows that there are two implementation of a tree: figure=tree_adt.eps In the next chapter we will see a more complicated figure that depicts the heap implementation of a Priority Queue. A tree node Like lists, trees are made up of nodes. A common kind of tree is a binary tree, in which each node contains a reference to two other nodes (possibly null). The class definition looks like this: verbatim public class Tree Object cargo; Tree left, right; verbatim Like list nodes, tree nodes contain cargo: in this case a generic Object. The other instance variables are called left and right, in accordance with a standard way to represent trees graphically: figure=tree1.eps The top of the tree (the node referred to by tree) is called the root. In keeping with the tree metaphor, the other nodes are called branches and the nodes at the tips with null references are called leaves. It may seem odd that we draw the picture with the root at the top and the leaves at the bottom, but that is not the strangest thing. To make things worse, computer scientists mix in yet another metaphor: the family tree. The top node is sometimes called a parent and the nodes it refers to are its children. Nodes with the same parent are called siblings, and so on. Finally, there is also a geometric vocabulary for taking about trees. I already mentioned left and right, but there is also ``up'' (toward the parent/root) and down (toward the children/leaves). Also, all the nodes that are the same distance from the root comprise a level of the tree. I don't know why we need three metaphors for talking about trees, but there it is. Building trees The process of assembling tree nodes is very similar to the process of assembling lists. We have a constructor for tree nodes that initializes the instance variables. verbatim public Tree (Object cargo, Tree left, Tree right) this.cargo = cargo; this.left = left; this.right = right; verbatim We allocate the child nodes first: verbatim Tree left = new Tree (new Integer(2), null, null); Tree right = new Tree (new Integer(3), null, null); verbatim We can create the parent node and link it to the children at the same time: verbatim Tree tree = new Tree (new Integer(1), left, right); verbatim This code produces the state shown in the previous figure. By now, any time you see a new compound data type, your first question should be, ``How can I traverse it?'' The most natural way to traverse a tree is recursively. For example, to add up all the integers in a tree, we could write this class method: verbatim public static int total (Tree tree) if (tree == null) return 0; Integer cargo = (Integer) tree.cargo; return cargo.intValue() + total (tree.left) + total (tree.right); verbatim This is a class method because we would like to use null to represent the empty tree, and make the empty tree the base case of the recursion. If the tree is empty, the method returns 0. Otherwise it makes two recursive calls to find the total value of its two children. Finally, it adds in its own cargo and returns the total. Although this method works, there is some difficulty fitting it into an object-oriented design. It should not appear in the Tree class because it requires the cargo to be Integer objects. If we make that assumption in Tree.java then we lose the advantages of a generic data structure. On the other hand, this code accesses the instance variables of the Tree nodes, so it ``knows'' more than it should about the implementation of the tree. If we changed that implementation later (and we will) this code would break. Later in this chapter we will develop ways to solve this problem, allowing client code to traverse trees containing any kinds of objects without breaking the abstraction barrier between the client code and the implementation. Before we get there, though, let's look at an application of trees. Expression trees A tree is a natural way to represent the structure of an expression. For example, the infix expression 1 + 2 * 3 and the postfix expression 1 2 3 * + represent the same computation, but in both cases we have to know semantic rules in order to evaluate the expression. In the first case we have to know the order of operations; in the second case we have to know the stack model of evaluation. Without these rules, the expressions are ambiguous. A tree is an unambiguous representation of a computation. The following figure represents the same computation: figure=tree2.eps The nodes can be operands like 1 and 2 or operators like + and *. Operands are leaf nodes; operators contain references to their operands (all of these operators are binary, meaning they have exactly two operands). Looking at this figure, there is no question what the order of operations is: the multiplication happens first in order to compute the first operand of the addition. Expression trees like this have many uses. The example we are going to look at is translation from one format (postfix) to another (infix). Similar trees are used inside compilers to parse, optimize and translate programs. Traversal I already pointed out that recursion provides a natural way to traverse a tree. We can print the contents of an expression tree like this: verbatim public static void print (Tree tree) if (tree == null) return; System.out.print (tree + " "); print (tree.left); print (tree.right); verbatim In other words, to print a tree, first print the contents of the root, then print the entire left subtree, then print the entire right subtree. This way of traversing a tree is called a preorder, because the contents of the root appear before (pre-) the contents of the children. For the example expression the output is + 1 * 2 3. This is different from both postfix and infix; it is a new format called prefix, in which the operators appear before their operands. You might begin to suspect that if we traverse the tree in a different order we might get the expression back in a different format. For example, if we print the subtrees first, and then the root node: verbatim public static void printPostorder (Tree tree) if (tree == null) return; printPostorder (tree.left); printPostorder (tree.right); System.out.print (tree + " "); verbatim We get the expression in postfix (1 2 3 * +)! As the name of the previous method implies, this order of traversal is called postorder. Finally, to traverse a tree inorder, we print the left tree, then the root, then the right tree: verbatim public static void printInorder (Tree tree) if (tree == null) return; printInorder (tree.left); System.out.print (tree + " "); printInorder (tree.right); verbatim The result is 1 + 2 * 3, which is the expression in infix. Now, to be fair, I have to point out that I have omitted an important complication. Sometimes when we write an expression in infix we have to use parentheses to preserve the order of operations. So an inorder traversal is not quite sufficient to generate an infix expression. Nevertheless, with a few improvements, the expression tree and the three recursive traversals provide a general way to translate expressions from one format to another. Encapsulation There is still one problem with the way we have been traversing trees: it breaks down the barrier between the client code (the application that builds the tree) and the Tree implementation. Ideally, tree code should be general; it shouldn't know anything about expression trees. And the code that generates and traverses the expression tree shouldn't know about the implementation of the trees. This design criterion is called object encapsulation. In the current version, the Tree code knows too much about the application. Instead, the Tree class should provide the general capability of traversing a tree in various ways. As it traverses, it should perform operations on each node that are specified by the application. To facilitate this separation of interests, we will create a new abstract class, called Visitable. The items stored in a tree will be required to be visitable, which means that they define a method named visit that does whatever it is the application wants done to each node. That way the Tree can perform the traversal and the application can perform the node operations. Here are the steps we have to perform to wedge an abstract class between an application and a library: enumerate Define an abstract class that specifies the operations we need the library to be able to perform. Rewrite the library to use the new abstract class instead of generic Objects. Define a concrete class that implements the abstract class in a way that is appropriate for the application. Rewrite the application to use the new concrete class. enumerate The next few sections demonstrate these steps. Defining an abstract class An abstract class definition looks a lot like a concrete class definition, except that it only specifies the interface of each method and not an implementation. The definition of Visitable is verbatim public interface Visitable public void visit (); verbatim That's it! The word interface is Java's keyword for an abstract class. The definition of visit looks like any other method definition, except that it has no body. This definition specifies that any class that implements Visitable has to have a method named visit that takes no parameters and that returns void. Like other class definitions, abstract class definitions go in a file with the same name as the class (in this case Visitable.java). Implementing an abstract class For the current application, ``visiting'' a tree node means printing its contents. Since the contents of an expression tree are tokens, we'll create a new concrete class called Token that implements Visitable verbatim public class Token implements Visitable String str; public Token (String str) this.str = str; public void visit () System.out.print (str + " "); verbatim When we compile this class definition (which is in a file named Token.java), the compiler checks whether the methods provided satisfy the requirements specified by the abstract class. If not, it will produce an error message. For example, if we misspell the name of the method that is supposed to be visit is not correct, we might get something like, ``class Token must be declared abstract. It does not define void visit() from interface Visitable.'' The next step is to modify the parser to put Token objects into the tree instead of Strings. Here is a small example: verbatim String expr = "1 2 3 * +"; StringTokenizer st = new StringTokenizer (expr, " +-*/", true); String token = st.nextToken(); Tree tree = new Tree (new Token (token), null, null)); verbatim Array implementation of trees What does it mean to ``implement'' a tree? So far we have been talking about trees as data structures. To say what a tree is, we would explain how to build one and what basic operations we can perform (like traversal). But the Tree type we have been working with is not the only kind of thing we would like to recognize as a tree. There is a set of operations trees should be able to perform, and anything that can perform them should be recognized as a tree. In other words, a tree is an ADT. It is defined by the following operations. description [construction:] Build an empty tree. [empty:] Is this tree the empty tree? [left:] Return the left child of this node, or an empty tree if there is none. [right:] Return the left child of this node, or an empty tree if there is none. [parent:] Return the parent of this node, or an empty tree if this node is the root. description In the implementation we have seen, the empty tree is represented by the special value null. left and right are performed by accessing the instance variables of the node. We have not implemented parent yet (you might think about how to do it). There is another implementation of trees that uses arrays and indices instead of objects and references. To see how it works, we will start by looking at a hybrid implementation that uses both arrays and objects. This figure shows a tree like the ones we have been looking at, although it is laid out sideways, with the root at the left and the leaves on the right. At the bottom there is an array of references that refer to the objects in the trees. figure=tree3.eps In this particular case, the cargo of each node is the same as the array index of the node, but of course that is not true in general. You might notice that array index 1 refers to the root node and array index 0 is empty. The reason for that will become clear soon. So now we have a tree where each node has a unique index. Furthermore, the indices have been assigned to the nodes according to a deliberate pattern, in order to achieve the following results: enumerate The left child of the node with index has index . The right child of the node with index has index . The parent of the node with index has index (rounded down). enumerate Using these formulas, we can implement left, right and parent just by doing arithmetic; we don't have to use the references at all! Since we don't use the references, we can get rid of them, which means that what used to be a tree node is now just cargo and nothing else. That means we can implement the tree as an array of cargo objects; we don't need tree nodes at all. Here's what one implementation looks like: verbatim public class Tree Object[] array; static String empty = "empty node"; public Tree () array = new Object [128]; for (int i=0; i a and a > b. Now that this subtree is reheapified, we can work our way up the tree until we reach the root. Performance of heaps For both insert and remove, we perform a constant-time operation to do the actual insertion and removal, but then we have to reheapify the tree. In one case we start at the root and work our way down, comparing items and then recursively reheapifying one of the subtrees. In the other case we start at a leaf and work our way up, again comparing elements at each level of the tree. As usual, there are several operations we might want to count, like comparisons and swaps. Either choice would work, the real issue is the number of levels of the tree we examine and how much work we do at each level. In both cases we keep examining levels of the tree until we restore the heap property, which means we might only visit one, or in the worst case we might have to visit them all. Let's consider the worst case. At each level, we perform only constant-time operations like comparisons and swaps. So the total amount of work is proportional to the number of levels in the tree, also called the height of the tree. So we might say that these operations are linear with respect to the height of the tree, but the ``problem size'' we are interested in is not height, it's the number of items in the heap. As a function of , the height of the tree is . This is not true for all trees, but it is true for complete trees. To see why, think of the number of nodes on each level of the tree. The first level contains 1, the second contains 2, the third contains 4, and so on. The th level contains nodes, and the total number in all levels up to is . In other words, which means that . Thus, both insertion and removal take logarithmic time. To insert and remove items takes time proportional to . Heapsort The result of the previous section suggests yet another algorithm for sorting. Given items, we insert them into a Heap and then remove them. Because of the Heap semantics, they come out in order. We have already shown that this algorithm, which is called heapsort, takes time proportional to , which is better than selection sort and the same as mergesort. As the value of gets large, we expect heapsort to be faster than selection sort, but performance analysis gives us no way to know whether it will be faster than mergesort. We would say that the two algorithms have the same order of growth because they grow with the same functional form. Another way to say the same thing is that they belong to the same complexity class. Complexity classes are sometimes written in ``big-O notation''. For example, , pronounced ``oh of en squared'' is the set of all functions that grow no faster than for large values of . To say that an algorithm is is the same as saying that it is quadratic. The other complexity classes we have seen, in decreasing order of performance, are: 0.2in tabularll & constant time & logarithmic & linear & ``en log en'' & quadratic & exponential tabular 0.2in So far none of the algorithms we have looked at are exponential. The reason is that these algorithms take so long (for any significant value of ) that they are impractical. Glossary description [selection sort:] The simple sorting algorithm in Section sorting. [mergesort:] A better sorting algorithm from Section mergesort. [heapsort:] Yet another sorting algorithm. [complexity class:] A set of algorithms whose performance (usually run time) has the same order of growth. [order of growth:] A set of functions with the same leading-order term, and therefore the same qualitative behavior for large values of . [overhead:] Additional time or resources consumed by a programming performing operations other than the abstract operations considered in performance analysis. [height:] The height of a tree is the number of levels. description Table Arrays, Vectors and Tables Arrays are a generally useful data structure, but they suffer from two important limitations: itemize The size of the array does not depend on the number of items in it. If the array is too big, it wastes space. If it is too small it might cause an error, or we might have to write code to resize it. Although the array can contain any type of item, the indices of the array have to be integers. We cannot, for example, use a String to specify an element of an array. itemize In Section vector we saw how the built-in Vector class solves the first problem. As the user adds items it expands automatically. It is also possible to shrink a Vector so that the capacity is the same as the current size. But Vectors don't help with the second problem. The indices are still integers. That's where the Table ADT comes in. The Table is a generalization of a Vector that can use any type as an index. These generalized indices are called keys. Just as you would use an index to access a value in an array, you use a key to access a value in a Table. So each key is associated with a value, which is why Tables are sometimes called associative arrays. The canonical example of a table is a dictionary, which is a table that associates words (the keys) with their definitions (the values). Because of this example Tables are also sometimes called Dictionaries. Also, the association of a particular key with a particular value is called an entry. The Table ADT Like the other ADTs we have looked at, Tables are defined by the set of operations they support: description [constructor:] Make a new, empty table. [put:] Create an entry that associates a value with a key. [get:] For a given key, find the corresponding value. [containsKey:] Return true if there is an entry in the Table with the given Key. description The built-in Hashtable Java provides an implementation of the Table ADT called Hashtable. It is in the java.util package. Later in the chapter we'll see why it is called Hashtable. To demonstrate the use of the Hashtable we'll write a short program that traverses a String and counts the number of times each word appears. We'll create a new class called WordCount that will build the Table and then print its contents. Naturally, each WordCount object will contain a Hashtable: verbatim public class WordCount Hashtable ht; public WordCount () ht = new Hashtable (); verbatim The only public methods for WordCount are processLine, which takes a String and adds its words to the Table, and print, which prints the results at the end. processLine breaks the String into words using a StringTokenizer and passes each word to processWord. verbatim public void processLine (String s) StringTokenizer st = new StringTokenizer (s, " ,.", false); while (st.hasMoreTokens()) String word = st.nextToken(); processWord (word.toLowerCase ()); verbatim The interesting work is in processWord. verbatim public void processWord (String word) if (ht.containsKey (word)) Integer i = (Integer) ht.get (word); Integer j = new Integer (i.intValue() + 1); ht.put (word, j); else ht.put (word, new Integer (1)); verbatim If the word is already in the table, we get its counter, increment it, and put the new value. Otherwise, we just put a new entry in the table with the counter set to 1. To print the entries in the table, we need to be able to enumerate the keys in the table. Fortunately, the Hashtable implementation provides a method, keys, that returns an Enumeration object we can use. Enumerations are very similar to the Iterators we saw in Section iterator. Both are abstract classes in the java.util package; you should review the documentation of both. Here's how keys works: verbatim public void print () Enumeration enum = ht.keys (); while (enum.hasMoreElements ()) String key = (String) enum.nextElement (); Integer value = (Integer) ht.get (key); System.out.println (" " + key + ", " + value + " "); verbatim Each of the elements of the Enumeration is an Object, but since we know they are keys, we typecast them to be Strings. When we get the values from the Table, they are also Objects, but we know they are counters, so we typecast them to be Integers. Finally, to count the words in a string: verbatim WordCount wc = new WordCount (); wc.processLine ("da doo ron ron ron, da doo ron ron"); wc.print (); verbatim The output is verbatim ron, 5 doo, 2 da, 2 verbatim In general the Enumeration is not in any particular order. The only guarantee is that all the keys in the table will appear. A Vector implementation One easy way to implement the Table ADT is to use a Vector of entries, where each entry is an object that contains a key and a value. These objects are called key-value pairs. A class definition for a KeyValuePair might look like this: verbatim class KeyValuePair Object key, value; public KeyValuePair (Object key, Object value) this.key = key; this.value = value; public String toString () return " " + key + ", " + value + " "; verbatim Then the implementation of Table looks like this: verbatim public class Table Vector v; public Table () v = new Vector (); verbatim To put a new entry in the table, we just add a new KeyValuePair to the Vector: verbatim public void put (Object key, Object value) KeyValuePair pair = new KeyValuePair (key, value); v.add (pair); verbatim Then to look up a key in the Table we have to traverse the Vector and find a KeyValuePair with a matching key: verbatim public Object get (Object key) Iterator iterator = v.iterator (); while (iterator.hasNext ()) KeyValuePair pair = (KeyValuePair) iterator.next (); if (key.equals (pair.key)) return pair.value; return null; verbatim The idiom to traverse a Vector is the one we saw in Section iterator. When we compare keys, we use deep equality (the equals method) rather than shallow equality (the == operator). This allows the key class to specify the definition of equality. In our example, the keys are Strings, so it will use the built-in equals method in the String class. For most of the built-in classes, the equals method implements deep equality. For some classes, though, it is not easy to define what that means. For example, see the documentation of equals for Doubles. The containsKey method is almost identical to get except that it returns true or false instead of an object reference or null. Actually, the implementation of put is not complete. If there is already an entry in the table with the given key, put should update it (give it a new value), not add another entry with the same key. So a more correct version is: verbatim public void put (Object key, Object value) if (containsKey (key)) update (key, value); else KeyValuePair pair = new KeyValuePair (key, value); v.add (pair); verbatim The update method is not part of the Table ADT, so it is declared private: verbatim private void update (Object key, Object value) Iterator iterator = v.iterator (); while (iterator.hasNext ()) KeyValuePair pair = (KeyValuePair) iterator.next (); if (key.equals (pair.key)) pair.value = value; break; verbatim The only method we haven't implemented is keys. As an exercise, write this method by building a Vector of keys and returning the elements of the vector. The List abstract class The java.util package defines an abstract class called List that specifies the set of operations a class has to implement in order to be considered (very abstractly) a list. This does not mean, of course, that every class that implements List has to be a linked list. As a matter of fact, the built-in LinkedList class does implement List, but so does Vector Some of the methods in the List definition are add, get and iterator. Notice that all the methods from the Vector class that we used to implement Table are defined in the List abstract class. That means that instead of a Vector, we could have used any List class. In Table.java we can replace Vector with LinkedList, and the program still works! This kind of type generality can be very useful for tuning the performance of a program. You can write the program in terms of an abstract class like List and then test the program with several different implementations to see which yields the best performance. Hash table implementation The reason that the built-in implementation of the Table ADT is called Hashtable is that it uses a particularly efficient implementation of a Table called a hashtable. Of course, the whole point of defining an ADT is that it allows us to use an implementation without knowing the details. So it is probably a bad thing that the people who wrote the Java library named this class according to its implementation rather than its ADT, but I suppose of all the bad things they did, this one is pretty small. Anyhoo, you might be wondering what a hashtable is, and why I say it is particularly efficient. We'll start by analyzing the performance of the List implementation we just did. Looking at the implementation of put, we see that there are two cases. If the key is not already in the table, then we only have to create a new key-value pair and add it to the List. Both of these are constant-time operations. In the other case, we have to traverse the List to find the existing key-value pair. This operation is linear (depending on the length of the list). For the same reason, get and containsKey are also linear. Although linear operations are often good enough, we can do better. It turns out that there is a way to implement the Table ADT so that both put and get are constant-time operations! The key is to realize that traversing a list takes time proportional to the length of the list. If we can put an upper bound on the length of the list, then we can put an upper bound on the traverse time, and anything with a fixed upper bound is considered constant time. But how can we limit the length of the lists without limiting the number of items in the table? By increasing the number of lists: instead of one long list, we'll keep many short lists. As long as we know which list to search, we can put a bound on the amount of searching. Hash Functions And that's where hash functions come in. We need some way to look at a key and know, without searching, which list it will be in. We'll assume that the lists are in an array (or Vector) so we can refer to them by index. The solution is to come up with some mapping---almost any mapping---between the key values and the indices of the lists. For every possible key there has to be a single index, but there might be many keys that map to the same index. For example, imagine an array of 8 lists and a table made up of keys that are Integers and values that are Strings. It might be tempting to use the intValue of the Integers as indices, since they are the right type, but there are a whole lot of integers that do not fall between 0 and 7, which are the only legal indices. The modulus operator provides a simple (in terms of code) and efficient (in terms of run time) way to map all the integers into the range . The expression verbatim key.intValue() verbatim is always in the range. For other types, we can play similar games. For example, to convert a Character to an integer, we can use the built-in method Character.getNumericValue and for Doubles there is intValue. For Strings we could get the numeric value of each character and add them up, or instead we might use a shifted sum. To calculate a shifted sum, alternate between adding new values to the accumulator and shifting the accumulator to the left. By ``shift to the left'' I mean ``multiply by a constant.'' To see how this works, take the list of numbers 1, 2, 3, 4, 5, 6 and compute their shifted sum as follows. First, initialize the accumulator to 0. Then, enumerate Add the next element of the list to the accumulator. Multiply the accumulator by 10. Repeat until the list is finished. enumerate As an exercise, write a method that calculates the shifted sum of the numeric values of the characters in a String using a multiplier of 32. So, for each type, we have a function that takes values of that type and generates a corresponding integer value. These functions are called hash functions, because they often involve making a hash of the components of the objects. The integer value for each object is called its hash code. There is one other way we might generate a hash code for Java objects. Every Java object provides a method called hashCode that returns an integer that corresponds to that object. For the built-in types, the hashCode method is implemented so that if two objects contain the same data, they will have the same hash code (as in deep equality). The documentation of these methods explains what the hash function is. You should check them out. For user-defined types, it is up to the implementor to provide an appropriate hash function. The default hash function, provided in the Object class, often uses the location of the object to generate a hash code, so its notion of ``sameness'' is shallow equality. Most often when we are searching a hash table for a key, shallow equality is not what we want. Regardless of how the hash code is generated, the last step is to use the modulus operator to map the hash code into the range of legal indices. Resizing a hash table Let's review. A Hash table consists of an array (or Vector) of Lists, where each List contains a small number of key-value pairs. To add a new entry to a table, we calculate the hash code of the new key and add the entry to the corresponding List. To look up a key, we hash it again (getting the same value every time) and search the corresponding list. If the lengths of the lists are bounded then the search time is bounded. So how do we keep the lists short? Well, one goal is to keep them as balanced as possible, so that there are no very long lists at the same time that others are empty. This is not easy to do perfectly---it depends on how well we chose the hash function---but we can usually do a pretty good job. Even with perfect balance, the average list length grows linearly with the number of entries, and we have to put a stop to that. The solution is to keep track of the average number of entries per list, which is called the load factor; if the load factor gets to high, we have to resize the table. To resize, we create a new table, usually twice as big as the original, take all the entries out of the old one, hash them again, and put them in the new table. Usually we can get away with using the same hash function; we just use a different value for the modulus operator. Performance of resizing How long does it take to resize the table? Clearly it is linear with the number of entries. That means that most of the time put takes constant time, but every once in a while it takes linear time. At first glance, that sounds bad. Doesn't that undermine my claim that we can perform put in constant time? Well, frankly, yes. But with a little wheedling, I can fix it. Since some put operations take longer than others, let's figure out the average time for a put operation. The average is going to be , the constant time for a simple put, plus an additional term of , the percentage of the time I have to resize, times , the cost of resizing. equation t(n) = c + p kn equation I don't know what and are, but we can figure out what is. Imagine that we have just resized the hash table by doubling its size. If there are entries, then we can add an addition entries before we have to resize again. So the percentage of the time we have to resize is . Plugging into the equation, we get equation t(n) = c + 1/n kn = c + k equation In other words, is constant time! Glossary description [table:] An ADT that defines operations on a collection of entries. [entry:] An element in a table that contains a key-value pair. [key:] An index, of any type, used to look up values in a table. [value:] An element, of any type, stored in a table. [dictionary:] Another name for a table. [associative array:] Another name for a dictionary. [hashtable:] A particularly efficient implementation of a table. [hash function:] A function that maps values of a certain type onto integers. [hash code:] The integer value that corresponds to a given value. [shifted sum:] A simple hash function often used for compounds objects like Strings. [load factor:] The number of entries in a hashtable divided by the number of lists in the hashtable; i.e. the average number of entries per list. description