table ADT

Complete

Summary

Table ADT

  • binds a key to a value
  • allows lookup for stored values

Direct addressing table(DAT) - array

  • the values are used as the key/indexes of the array
OperationMethodPerformance
search(v)check if the index v is filled-
insert(v)fill index v-
remove(v)empty index v-

the couting array in counting sort works similarly, range of keys must be small(and non-negative), space

java.util.Map interface

Library implementations

java
Map<Integer> mp = new HashMap<>();
// or
Map<Integer> mp = new TreeMap<>();

// insert(v)
mp.put(0, 123);
mp.put(0, 100); // replaces the old mapping
mp.put(1, 120);
// 0 -> 100, 1 -> 120

// search(v)
mp.containsKey(0); // true, checks if this key has a value
mp.containsValue(120); // true, checks if this value is present

// remove(v)
mp.remove(0); // removes key-value pair
// 0 -> 120

mp.size(); // number of key-value pairs
mp.isEmpty(); // check if the Map is empty
mp.values(); // collection of the values

there are other useful functions that allow Map to be a monad

java.util.Set interface

Library implementations

java
Set<Integer> set = new HashSet<>();
// or
Set<Integer> set = new TreeSet<>();

// insert(v)
set.add(1);
set.add(1); // duplicates are not added
set.add(12);
// 1, 12

// search(v)
set.contains(1); // true, checks if the value is present

// remove(v)
set.remove(1);
// 12

set.size(); // number of values in the set
set.isEmpty(); // check if the Set is empty

by the no repititon property of sets

Concept

Table operations

  • search(v)
    • determine if v exists in the table
  • insert(v)
    • insert v into the table
  • remove(v)
    • remove v from the table
0123...kv0v3vk