Lecture 19:

Symbol Tables

CS 136: Spring 2024

Katie Keith

Record on Zoom

• Lab 5 due Monday (today) or Tuesday (tomorrow)
• Lab 6 this week: No starter code!
• Recommended to allocate a bit more time for this lab
• Optional Midterm Corrections due Monday April 14 (today) at 10pm. Submit on Gradescope.
• TA eval form (Due April 18) : https://forms.gle/sbqCGVLAFnhUQ4i39

📣 Announcements

📚Readings

• Sedgewick and Wayne. Algorithms. Section 3.1.

​

• Symbol tables (ADT) overview
• Symbol Table Data Structure #1: Linked List
• Symbol Table Data Structure #2: Two arrays (sorted)

​

🎯 Today’s Learning Objectives

Symbol Table

A symbol table is an ADT where we save information (a value) that we can later search for and retrieve by specifying a key. Keys are unique (no duplicates).

Running Example:

​

Record the number of gold medals each country won in the 2024 Olympics

Julien Alfred Wins Saint Lucia's First Gold Medal in the 100 M Dash

​

Python Dictionaries are Symbol Tables

gold_medals = {

"USA": 40,

"China": 40,

"Japan": 20,

"Saint Lucia": 1,

}

​

​

​

CS 134: How do we use dictionaries?

​

CS 136: How do we implement dictionaries “under the hood”?

Key of a dictionary

Value of a dictionary

Other Applications of Symbol Tables

Source: S&W Sec 3.1

Lab 6!

Multiple data structures can implement the same ADT

ADT

Data Structures

List

Finite number of elements

(same element may occur more than once)

Stack

Last in first out (LIFO) operations

Symbol Table

Associates a key with a value

Graph

A set of vertices, pairs of which are connected by edges

Queue

First in first out (FIFO) operations

Multiple data structures can implement the same ADT

Singly Linked Lists

Data Structures

Arrays

int[] arr = {1, 2, 3, 4, 5};

List

Finite number of elements

(same element may occur more than once)

Doubly Linked Lists

Stack

Last in first out (LIFO) operations

Symbol Table

Associates a key with a value

Graph

A set of vertices, pairs of which are connected by edges

Queue

First in first out (FIFO) operations

ADT

Multiple data structures can implement the same ADT

Binary Search Tree

Data Structures

Linked List

Hash Tables

​

List

Finite number of elements

(same element may occur more than once)

Two arrays (sorted)

Stack

Last in first out (LIFO) operations

Symbol Table

Associates a key with a value

Graph

A set of vertices, pairs of which are connected by edges

Queue

First in first out (FIFO) operations

String[] keys;

int[] values;

ADT

Symbol Table Interface

import java.util.Comparator;

​

public interface SymbolTable<Key, Value>{

​

/* Returns true if the table is empty */

public abstract boolean isEmpty();

​

/* Returns the number of key-value pairs */

public abstract int size();

​

/* Inserts the key-value pair into the table

* The comparator is used to compare keys

* Convention: If key already exists, overwrites with new val */

public abstract void put(Key key, Value val, Comparator<Key> comparator);

​

/* “Search”!

* Returns the value paired with the key

* Returns null if the key is not in the table */

public abstract Value get(Key key, Comparator<Key> comparator);

}

Generic types

Symbol Table Interface

import java.util.Comparator;

​

public interface SymbolTable<Key, Value>{

​

/* Returns true if the table is empty */

public abstract boolean isEmpty();

​

/* Returns the number of key-value pairs */

public abstract int size();

​

/* Inserts the key-value pair into the table

* The comparator is used to compare keys

* Convention: If key already exists, overwrites with new val */

public abstract void put(Key key, Value val, Comparator<Key> comparator);

​

/* “Search”!

* Returns the value paired with the key

* Returns null if the key is not in the table */

public abstract Value get(Key key, Comparator<Key> comparator);

}

Generic types

Symbol Table Interface

import java.util.Comparator;

​

public interface SymbolTable<Key, Value>{

​

/* Returns true if the table is empty */

public abstract boolean isEmpty();

​

/* Returns the number of key-value pairs */

public abstract int size();

​

/* Inserts the key-value pair into the table

* The comparator is used to compare keys

* Convention: If key already exists, overwrites with new val */

public abstract void put(Key key, Value val, Comparator<Key> comparator);

​

/* “Search”!

* Returns the value paired with the key

* Returns null if the key is not in the table */

public abstract Value get(Key key, Comparator<Key> comparator);

}

Generic types

Preview: important for data structures with sorted keys

Symbol Table Interface

import java.util.Comparator;

​

public interface SymbolTable<Key, Value>{

​

/* Returns true if the table is empty */

public abstract boolean isEmpty();

​

/* Returns the number of key-value pairs */

public abstract int size();

​

/* Inserts the key-value pair into the table

* The comparator is used to compare keys

* Convention: If key already exists, overwrites with new val */

public abstract void put(Key key, Value val, Comparator<Key> comparator);

​

/* "Search"!

* Returns the value paired with the key

* Returns null if the key is not in the table */

public abstract Value get(Key key, Comparator<Key> comparator);

}

Generic types

Python Dictionaries are Symbol Tables

gold_medals = {

"USA": 40,

"China": 40,

"Japan": 20,

"Saint Lucia": 1,

}

gold_medals["New Zealand"] = 10

print(gold_medals["USA"])

​

​

​

put operation

get operation (search!)

• Symbol tables (ADT) overview
• Symbol Table Data Structure #1: Linked List
• Symbol Table Data Structure #2: Two arrays (sorted)

​

✅

🎯 Today’s Learning Objectives

Review: Linked Lists (of Strings)

private Node first;

private class Node {

private String data;

private Node next;

​

public Node() {

this.data =null ;

this.next = null;

}

}

​

first

data

next

for(Node x = first; x != null; x = x.next){

// Do something

}

​

Loop to traverse a Linked List

Linked List to implement a Symbol Table

To implement a Symbol Table with a Linked List, each Node has three instance variables: one that stores the key, one that stores the value and one that stores a reference to the next node.

key

val

next

first

Design Sketch: LinkedList for SymbolTable

• Each node of a Linked List will contain both a key and a value
• put
• First, scan through the list to check if the key already exists
• If a key is found, replace the value.
• If the key is not found, insert a node with the new key and value at the beginning of the list (elements in the list are unordered).
• get
• Scan through the list and return if the key exists

LinkedListST.java

​

​

💻

There are two major errors in the put method below. What are they and how would we fix them?

public void put(Key key, Value val, Comparator<Key> comparator){

if (key == null){return;} //Bad key

​

for (Node x = first; x != null; x = x.next) {

if (key == x.key) {

x.val = val;

return;

}

}

first = new Node();

first.key = key;

first.val = val;

numPairs++;

}

​

​

💡Think-pair-share

LinkedListST.java

​

get()

main()

💻

Analysis of Symbol Table’s Data Structures

Analysis of Symbol Table’s Data Structures

• Symbol tables (ADT) overview
• Symbol Table Data Structure #1: Linked List
• Symbol Table Data Structure #2: Two arrays (sorted)

​

✅

✅

🎯 Today’s Learning Objectives

Design Sketch: Two arrays (sorted) for SymbolTables

• Use two “parallel” arrays, one for keys and one for values
• Keep the keys in sorted order
• Helper function rank: returns number of keys smaller than a given key
• put
• Call rank. If the key exists, move all larger keys over one position to make room
• get
• Call rank and return the value if the key exists

We’ll start with get, then return to put

TwoArraysST.java

​

💻

Search algorithms

*Note: Our book refers to “linear search” as “sequential search”

Finish the rank method below. Note, this uses binary search.

// Returns the num. of keys strictly less than target

private int rank(Key target, Comparator<Key> comp) {

if (target == null){ return -1;} // invalid target

int lo = 0;

int hi = numPairs-1;

while ( ) {

int mid = lo + (hi - lo) / 2;

int cmp = comp.compare( , keys[ ]);

if (cmp < 0) hi = ;

else if (cmp > 0) lo = ;

else return ;

}

return lo;

}

​

​

💡Think-pair-share

LinkedListST.java

​

put()

main()

💻

Analysis of Symbol Table’s Data Structures

Analysis of Symbol Table’s Data Structures

Preview for Weds: Can we do better for put?

• Symbol tables (ADT) overview
• Symbol Table Data Structure #1: Linked List
• Symbol Table Data Structure #2: Two arrays (sorted)

​

✅

✅

✅

🎯 Today’s Learning Objectives