COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 13-1 : Maps
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Maps
MAP (MATHEMATICS)
“domain”
A map is a set of pairs { (𝑥, 𝑓(𝑥)) }.
“codomain”
Each 𝑥 in domain maps to exactly one 𝑓(𝑥) in codomain, but it can happen that 𝑓(𝑥1) = 𝑓(𝑥2) for different 𝑥1, 𝑥2, i.e. many-to-one.
FAMILIAR EXAMPLES
Calculus 1 and 2 (“functions”):
𝑓 ∶ R𝑛 → R𝑛
Asymptotic complexity in CS:
𝑡 : input size number of steps in a algorithm.
MAPS IN EVERYDAY LIFE
The term “map” commonly refers to a 2D spatial representation of a region of the earth’s surface.
map(x, y) : position in image position in 2D Montreal
COLOR MAP
The color map representing the USA election results in 2020.
vote_result : US_state {D, R}
RESTAURANT MENU
menu : dish_name price
INDEX IN A BOOK
index : term list of pages
MAP (ADT)
keys (type K) values (type V)
A map is a set of (key, value) pairs.
For each key, there is at most one value.
MAP (ADT)
keys (type K) values (type V)
Note that it is possible for two keys to map to the same value.
MAP (ADT)
keys (type K) values (type V)
It is NOT allowed for one key to map to two different values! The example above is NOT a map.
MAP ENTRIES
values
The black dots here indicate objects (or potential objects) of type
keys
K or V that are not in the map.
Each (key, value) pair is called an entry. In this example, there are four entries.
EXAMPLE
Student IDs
Student records
In COMP 250 this semester, the above mapping has ~650 entries.
Most McGill students are not taking COMP 250 this semester. Student ID also happens to be part of the student record.
MAP ADT
put( key, value )
// Add the entry (key, value) to the map. If the map previously contained an entry with key, the old value is replaced by the specified value.
// Returns the value to which the specified key is mapped. Why not get(key, value) ?
// Removes the entry with the specified key.
Returns true if the entry was removed, false otherwise.
get(key)
remove(key)
DATA STRUCTURES FOR MAPS
How to organize a set of (key, value) pairs, i.e. entries ?
ARRAY LIST
null
null
0 1 2 3 4
How can we implement the following methods?
put( key, value ) get(key) remove(key)
put() would be O(1), while get() and remove() would be O(n)
SINGLY (OR DOUBLY) LINKED LIST
4
head tail
How can we implement the following methods?
put( key, value ) get(key) remove(key)
list
size
put() would be O(1), while get() and remove() would be O(n)
LET’S ADD ASSUMPTIONS
Special case #1: what if keys are comparable ?
ARRAY LIST (SORTED BY KEY)
null
null
0 1 2 3 4
How can we implement the following methods?
put( key, value ) get(key) remove(key)
put() and remove() would be O(n), while get() could be performs in time O(log n) using binary search
BINARY SEARCH TREE (SORTED BY KEY)
How can we implement the following methods?
put( key, value ) get(key) remove(key)
The performance of put(), get() and remove() depends on the tree. If we have a balances tree, then these operations would all take time O(log n) in worst case. You will learn more about balanced tree in COMP 251.
MINHEAP (PRIORITYDEFINEDBYKEY)
How can we implement the following methods?
put( key, value ) get(key) remove(key)
The performance of put() would be O(log n). Implementing get() would require traversing the tree, so it would be O(n). Implementing remove() would be a little weird for heaps…
LET’S ADD ASSUMPTIONS
Special case #1: what if keys are comparable ?
Special case #2: what if keys are unique positive integers in small range ?
ARRAYS OF VALUES
3
6
8
14
4 type V (value) and have O(1) 9
Then, we could use an array of
access.
This would not work well if keys are 9 digit student IDs.
12
22
IN GENERAL
Keys might not be comparable.
Keys might be not be positive integers.
e.g. Keys might be strings or some other type.
STRATEGY IN THE GENERAL CASE
Try to define a map from keys to small range of positive integers (array index), and then store the corresponding values in the array.
3
6
8
14
Recall notation: black dots are not part of the map.
IN THIS VIDEO
Define a map from keys to large range of positive integers Such map is called hash code.
JAVA’S Object.hashcode() 1-to-1
(not many-to-1)
objects in a Java program (runtime)
{0,1,2,…,224 −1}
object’s address in JVM memory (24 bits)
By default, “obj1 == obj2” means “obj1.hashcode() == obj2.hashcode()”
JAVA’S String.hashcode()
https://docs.oracle.com/javase/7/docs/api/java/lang/String.html
EXAMPLE HASH CODE FOR STRINGS
e.g.
(not used in Java)
𝑠.𝑙𝑒𝑛𝑔𝑡h−1
h𝑠≡ 𝑠[𝑖] 𝑖=0
h”𝑒𝑎𝑡” =h”𝑎𝑡𝑒” =h”𝑡𝑒𝑎” ASCII values of ‘a’, ‘e’, ‘t’ are 97, 101, 116.
JAVA’S String.hashcode() 𝑠.𝑙𝑒𝑛𝑔𝑡h−1
s.hashCode()≡ 𝑠 𝑖 ∗ 𝑥𝑠.𝑙𝑒𝑛𝑔𝑡h −1 − 𝑖 𝑖=0
where 𝑥 = 31.
JAVA’S String.hashcode() 𝑠.𝑙𝑒𝑛𝑔𝑡h−1
s.hashCode()
≡ 𝑠𝑖 𝑥𝑠.𝑙𝑒𝑛𝑔𝑡h−1−𝑖 𝑖=0
where 𝑥 = 31.
e.g. s = “eat” then s.hashcode() = 101*312 + 97*31 + 116 ‘e’ ‘a’ ‘t’
s[0] s[1] s[2]
JAVA’S String.hashcode() 𝑠.𝑙𝑒𝑛𝑔𝑡h−1
s.hashCode()
≡ 𝑠𝑖 𝑥𝑠.𝑙𝑒𝑛𝑔𝑡h−1−𝑖 𝑖=0
where 𝑥 = 31.
e.g. s = “ate” then s.hashcode() = 97*312 + 116*31 + 101 ‘a’ ‘t’ ‘e’
s[0] s[1] s[2]
JAVA’S String.hashcode() 𝑠.𝑙𝑒𝑛𝑔𝑡h−1
s.hashCode() ≡ 𝑠 𝑖 ∗ (31)𝑠.𝑙𝑒𝑛𝑔𝑡h −1 − 𝑖 𝑖=0
If s1.hashCode() == s2.hashCode() then what can we conclude about s1.equals(s2) ?
s1 may or may not be the same string as s2.
JAVA’S String.hashcode() 𝑠.𝑙𝑒𝑛𝑔𝑡h−1
s.hashCode() ≡ 𝑠 𝑖 ∗ (31)𝑠.𝑙𝑒𝑛𝑔𝑡h −1 − 𝑖 𝑖=0
If s1.hashCode() != s2.hashCode() then what can we conclude about s1.equals(s2) ?
s1 is a different string then s2.
In the next video: Hash Maps