Transcript Lecture: Advanced Data Structures

COMP206-08S
General
Programming 2
Geoff Holmes and Bernhard
Pfahringer
Lectures
-
Today
Collections Continued
Sets
-
Trees
Hashing
Department of Computer Science
2
So far



Arrays
Arraylists
LinkedList
Stacks
 Queues


Items are all placed at a position in the data
structure

LinkedList has an iterator with an “add” method
Department of Computer Science
3
Sets

A set is a collection of items that does not permit
duplicates
Adding an existing item has no effect
 Removing an item not in the set has no effect


Java has a Set interface with two implementations
HashSet (uses hashing to store items)
 TreeSet (uses a tree to store items – Sorted)

Department of Computer Science
4
Example
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class SetTest {
public static void main(String[] args)
{
Set<String> names = new HashSet<String> ();
names.add(“Harry”); // add lots more
Department of Computer Science
5
Continued
names.add("Jane");
names.add("Tom");
names.add("Richard");
names.add("Tom");
names.add("Barbara");
print(names);
}
Department of Computer Science
6
Printing
private static void print(Set<String> s)
{
System.out.print("{ ");
for (String x : s)
{
System.out.print(x);
System.out.print(" ");
}
System.out.println("}");
}
Department of Computer Science
7
TreeSet


Changing only two lines of code lets us have a
Tree behind the scenes
Note the order of items!
Department of Computer Science
8
Maps







Similar idea can be developed to make
associations
Two sets are kept in association
Set of keys -> Set of Values
Two keys may refer to same value
Names and phone numbers
Java has a Map Interface
Two maps are implemented
HashMap
 TreeMap

Department of Computer Science
9
Test program for maps
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
import java.util.Map;
public class maps {
public static void main(String[] args) {
Department of Computer Science
10
Continued
Map<String, String> yellowpages = new
HashMap<String, String> ();
yellowpages.put("Harry", "123456");
yellowpages.put("Jane", "012345");
yellowpages.put("Tom", "123458");
yellowpages.put("Richard", "123457");
yellowpages.put("Barbara", "123454");
yellowpages.put("Barbara", "987654"); // assignment
Department of Computer Science
11
Printing out maps
Set<String> keySet = yellowpages.keySet();
for (String key : keySet)
{
String value = yellowpages.get(key); // value assoc with key
System.out.println(key + "->" + value);
}
}
}
Department of Computer Science
12
What is hashing?




Technique for finding elements without making a
linear search through all elements
Uses a hash function is a function that computes
an integer value (called a hash code) from an
object (different objects should have different hash
codes)
Object class has a hashCode method
int h = x.hashCode();
Department of Computer Science
13
Hash functions


Should avoid collisions (two or more different
objects with the same hash code)
If you have your own objects you write:
public int hashCode( )
 When adding x.equals(y) => x.hashCode() ==
y.hashCode (avoid duplicates)



Eg for a circle so that circles of different radii are
stored separately.
Forgetting to implement hashCode means the one
assoc with Object is used – not a good idea.
Department of Computer Science
14
Example

Consider
Set<Circle> circles = new HashSet<Circle>();
circles.add(new Circle(5));
if (circles.contains(new Circle(5))
System.out.println(“Circle of radius 5 exists”);
Department of Computer Science
15
Binary Search Trees





Finding things is O(log N) with binary search
With arrays insertion and deletion are O(N)
Binary search trees are fast at everything
Nodes of a binary search tree have two children
Data values of all descendants to the left of any
node are less than the data value stored at that
node (similarly right and greater)
Department of Computer Science
16
Tree of names





For the list {Adam, Eve, Harry, Jane, Richard,
Tom}
Jane (root) – children Eve and Richard
Eve – children Adam and Harry
Richard – children Tom and null
Adam, Harry and Tom are leaf nodes (both
children null)
Department of Computer Science
17
Implementation overview
public class BinarySearchTree {
// need reference to root (like first in LL)
private node root;
// inner class for node
private class Node {
public void addNode(Node newNode) { }
public Comparable data;
public Node left;
public Node right;
}
}
Department of Computer Science
18
Tree Operations

Tree Traversal (sorted order)
Print left subtree
 Print data
 Print right subtree




Called Inorder traversal
Preorder traversal (root, left, right)
Postorder traversal (left, right, root) (3+4*5)
Department of Computer Science
19
Trees and Recursion
// Note this is a method of the Node inner class
public void printNodes( )
{
if (left != null) left.printNodes( );
System.out.println(data);
if (right != null) right.printNodes( );
}
// Method of BinarySearchTree
public void print( )
{
if (root != null) root.printNodes( );
}
Department of Computer Science
20
HashSet or TreeSet




If you have a good hash function for your objects
then performance will be better than trees
Hash sets are at the mercy of the hash function
Iterators visit TreeSet data in sorted order (hash
order is random)
TreeSet requires objects to implement
Comparable (or Comparator)
Department of Computer Science
21
How to choose – ask questions

How are elements accessed?
Doesn’t matter
 By key (eg a/c #)
 Integer index


(MAP)
(ARRAYLIST)
Does data order matter?
Doesn’t matter
 Must be sorted
 Store in insert order

(TREESET)
(LL, ARRAYLIST)
Department of Computer Science
22
More questions

What operations need to be fast?
Doesn’t matter (small dataset)
 Add/remove
 Search



(LL)
(SET)
(DM = ARRAYLIST)
Hash or Tree?
Strings should be hashed
 Own class need to check hashCode and equals
 Trees may need a Comparator

Department of Computer Science
23