next up previous
Next: Optional Methods Up: Language Extensions Previous: Extending Interfaces


A Java class can implement one or more interfaces, using the implements clause. The rule for legality of an implements declaration is the same as that for extends. For example, Figure 4 shows part of HashMap, a class that implements Map using a hash table. Note that the class requires equals and therefore the instantiation Map[Key,Value] is legal. The implementation of lookup uses both where-routines: hashcode is used to hash the input k to find the bucket for that key, and equals is used to find the entry for the key, if any. These calls are legal because the where clauses for Key describe them, and at runtime, the calls will invoke the corresponding operations of the actual parameter type being used.

public class HashMap[Key,Value]
       where Key {
                   boolean equals(Key k);
                   int hashcode();
       implements Map[Key,Value]  {

    HashBucket[Key,Value] buckets[ ]; // the hash array
    int sz; // size of the table
    static int count = 0; // number of hash tables

    public HashMap[Key,Value] (int sz) { . . . ; count++; }
    // effects:  makes this be a new,
    //           empty table of size sz.

    public Value lookup (Key k) throws not_in {
        HashBucket[Key, Value] b =
                     buckets[k.hashcode() % sz];
        while((b != null) && (!b.key.equals(k))) 
          b =;
        if (b == null) 
          throw new not_in();
        else return b.value;
    // other methods go here

class HashBucket[Key,Value] {
    public Key key;
    public Value value;
    public HashBucket[Key,Value] next;

Figure 4: Partial implementation of Map

A class need not implement an entire parameterized interface; instead, it can implement a particular instantiation, as shown in these examples: class BigMap[Value] implements Map[long,Value] ... class SortedList_char implements SortedList[char] ... Such specialized implementations can be more efficient than general ones. For example, one fast implementation of SortedList_char uses a fixed-size array of integers, where each array element counts the number of occurrences of the corresponding character.

A parameterized class may have static variables such as the static variable count in HashMap. Each distinct instantiation of HashMap produces a distinct copy of this variable. For example, HashMap[String, Num] and HashMap[String, String] have separate count variables, but all instantiations HashMap[String,Num] share one static variable. In Java, static initializers of ordinary classes are run when the class is first used. Similarly, static initializers of an instantiation are run when the instantiation is first used.

Andrew C. Myers, Joseph A. Bank, Barbara Liskov
Copyright © 1996 Association for Computing Machinery