Implementing Map Interface with Binary Search Tree
Discover how to implement a Map interface using a Binary Search Tree, exploring key concepts and intuitive placement of key-value pairs. Learn about TreeMap, HashMap, and the basic operations associated with mapping data. Dabble into the world of data structures and find out how to efficiently store and retrieve values based on keys.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Creative Commons License CS2 in Java Peer Instruction Materials by Cynthia Lee is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. Based on a work at http://peerinstruction4cs.org. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org. CSE 12 Basic Data Structures Cynthia Bailey Lee Some slides and figures adapted from Paul Kube s CSE 12
2 Today s Topics 1. TreeMap 2. HashMap
Review: the Map Interface
Map Interface Want to hold (key, value) associations Want to be able to look up values quickly using the key Siri, what is Diego s phone number? key = Diego , value = 858-555-0176 Basic operations of this ADT are something like this: void put(KeyType k, ValueType v) ValueType get(KeyType k) ValueType delete(KeyType k)
TreeMap An implementation of the Map (or Dictionary ) interface that has guaranteed log(n) worst case.
Implementing Map interface with a Binary Search Tree (BST) Usually we think of a hash table as the go- to implementation of the Map interface But Binary Search Trees are another option C++ s Standard Template Library (STL) uses a Red-Black tree for their Map STL in C++ is like Collections in Java
Implementing Map interface with a Binary Search Tree (BST) The next few slides will explore your intuitions (guesses) about how to place (key, value) pairs into a Binary Search Tree in a way that makes sense for implementing Map The examples list (key, value) pairs in parentheses like this: ( Mike , Clancy ) So this is a dictionary that lets you find somebody s last name if all you know is their first name
What does this tree map look like after we put ("Leonard", "Wei")? (A) (B) (C) (D)
What does this tree map look like after we put ("Paul", "Kube")? (B) (A) (C) (D)
What does this tree map look like after we put ("Maria", "Clancy")? (A) (B) (C) (D)
Hash Tables (HashMaps) Implementing the Map interface with Hash Tables
Imagine you want to look up your neighbors names, based on their house number House numbers: 2555 through 10567 (roughly 4000 houses) Names: one last name per house
Array vs Tree You could store them in a balanced TreeMap of some kind Log(n) to do get, put, delete Or you could store them in an array Array is really fast lookup! O(1) Just look in myarray[housenumber] to get the name
Hash Table is just a modified, more flexible array Keys don t have to be integers 0-(size-1) (Ideally) avoids big gaps like our gap from 0 to 2555 in the house numbers Hash function is what at makes this all work:
Hash key collisions Hash function takes key and maps it to an integer Sometimes will map two DIFFERENT keys to the same integer Collision We can NOT overwrite the value the way we would if it really were the same key Need a way of storing multiple values in a given place in the hash table
Closed Addressing with Linear Probing Where does Annie go if hashkey( Annie ) = 3? A. 0 B. 1 C. 2 D. 3 E. Other Array index 0 1 2 3 4 5 6 7 8 Value
Closed Addressing with Linear Probing Where does Juan go if hashkey( Juan ) = 4? Array index 0 1 2 3 4 5 6 7 8 Value A. 1 B. C. 3 D. 4 E. Annie 2 Other
Closed Addressing with Linear Probing Where does Julian go if hashkey( Julian ) = 3? A. 1 B. 2 C. 3 D. 4 E. Other Array index 0 1 2 3 4 5 6 7 8 Value Annie Juan
Closed Addressing with Linear Probing Where does Solange go if hashkey( Solange ) = 5? A. 3 B. 4 C. 5 D. 6 E. Other Array index 0 1 2 3 4 5 6 7 8 Value Annie Juan Julian
