Chapter 11 - Direct Addressing

Document last modified:

OVERVIEW

Scenario:
• Maintain a dynamic set.
• Each element has a key drawn from a universe U = {0, 1, . . . ,m − 1} where m isn’t too large.
• Unique keys, no two elements have the same key.

Represent by a direct-address table, or array, T [0 . . .m − 1]:
• Each slot, or position, corresponds to a key in U.
• If there’s an element x with key k, then T [k] contains a pointer to x.
• Otherwise, T [k] is empty, represented by NIL.

Specialized Universe of Keys

U = {0, 1, 2, ..., m - 1} where m is the total number of possible keys in the universe
U needs to be small because the direct addressing declares an array of size m, i.e., one array location for each k_i's satellite data d_i

Example implementing a dynamic set by a direct-address table

T = direct-address table

U = { 0, 1, .., 9 } each key corresponds to an index of the table (1-to-1 mapping)

K = { 2, 3, 5, 8 } Í U actual keys determines the slots in the table that contain pointers to elements.

Slots with / contain NIL

Question 11.1

The load factor a of a direct-addressed data structure is often given as: a = n / m

n = number of keys used, K = { 2, 3, 5, 8 }

m = number of keys in universe, U = { 0, 1, .., 9 }

What is the load (utilization) of the example?

What is the minimum load factor?

What is the maximum load factor?

Implementation

Initially, each location in the direct address table is initialized to NIL
Note: x.key is the key field of record x
When a location in the table is being used, it holds an address to a node (i.e., a node pointer) where the node contains a copy of the key and the satellite data
Let Node_Ptr be the data type defined for the pointer to the node
Let Direct_Address_Table be the data type for the table, each location in the table holds a Node_Ptr pointer, or NIL
A key k Î U, the universe of all keys

Direct-Address-Search (T: Direct_Address_Table, k: U) : Node_Ptr

-- post: if k is defined in T, then return the Node_Ptr address to the node
--                containing the key and the satellite data
--          if k is not defined in T, then return NIL
           return T[k]

Direct-Address-Insert (T: Direct_Address_Table, x: Node_Ptr)
  -- pre: T[ x.key ] = NIL
  -- post: T[ x.key ] = x
           T[ x.key ] ¬ x

Direct-Address-Delete (T: Direct_Address_Table, x: Node_Ptr)
-- post: T[ x.key ] = NIL
           T[ x.key ] ¬ NIL

Question 11.2

Diagram a data structure for direct-addressing to implement a dictionary of dates translating from historical dates to English representation, for example:

1492 ® "fourteen ninety two"

Which of above is the key? satellite data?

What does T, direct address table, hold?

Give a call to search for 1492 ® "fourteen ninety two".

Give a call to insert 1492 ® "fourteen ninety two".

Give a call to delete 1492 ® "fourteen ninety two".

Java Implementation

class Year {
     public String english;
     public int key;
     Year( int k, String e ) { english=e; key = k; }
}

public class Direct {
    static void INSERT( Year T[], Year x ) {
         T[ x.key ] = x;
    }

    static void DELETE( Year T[], Year x ) {
         T[ x.key ] = null;
    }

    static Year SEARCH( Year T[], int k ) {
         return T[ k ];
    }

     public static void main(String a[]) {
          Year T[] = new Year[10000];
          Year x;

          INSERT( T, new Year( 1492, "fourteen ninety two") );
          INSERT( T, new Year( 2011, "two oh one one") );

          x = SEARCH( T, 2011 );

          System.out.println( x.english );

          DELETE( T, x );
    }
}

Question 11.2

From above Java, what is stored at each index of T?

The natural numbers are totally ordered by the ≤ relation. Are the keys totally ordered?

Is the key field of Year redundant?

Performance

Direct-Address-Insert is Q(1)
Direct-Address-Search is Q(1)
Direct-Address-Delete is Q(1)

Question 11.3

Describe a procedure to find the maximum key used by a dynamic set S represented by a direct-address table T of length m.

What is the best and worst case performance?

Describe a procedure to find the maximum element (satellite data) of dynamic set S represented by a direct-address table T of length m.

What is the best and worst case performance?

When Direct Addressing Does Not Work (Well)

|U| is large then the array is large
K Ì U and |K| is small, then the usage of the array is sparse, i.e., the ratio of |K|/|U| is close to zero
Example:
- U = set of SS#
- K = the SS# of all the employees at IU Southeast
- |U| = 10⁹ and |K| < 5 * 10²

Question 11.4

Give one other situation when direct addressing as implemented here does not work well. Suggest a solution.

What is U for the Java program below?

What is set K of keys actually stored for the Java program below?

What is the maximum load factor?

What are the minimum storage requirements for the direct-addressing?

class Year {
     public String english;
     public int key;
     Year( int k, String e ) { english=e; key = k; }
}

public class Direct {
    static void INSERT( Year T[], Year x ) {
         T[ x.key ] = x;
    }

    static void DELETE( Year T[], Year x ) {
         T[ x.key ] = null;
    }

    static Year SEARCH( Year T[], int k ) {
         return T[ k ];
    }

     public static void main(String a[]) {
          Year T[] = new Year[10000];
          Year x;

          INSERT( T, new Year( 1492, "fourteen ninety two") );
          INSERT( T, new Year( 2011, "two oh one one") );

          x = SEARCH( T, 2011 );

          System.out.println( x.english );

          DELETE( T, x );
    }
}