Hash Maps: A Common Data Structure
Module 8 - Part 5
Hash Maps
I
n
t
r
o
d
u
c
t
i
o
n
●
So far we’ve learned about the following
datastructures:
○
Arrays
○
ArrayList/Lists
○
Linked Lists
○
Stacks
○
Queues
○
Trees (BST)
○
Graphs
●
There is one more common data structure you
should know about.
K
n
o
w
n
b
y
d
i
f
f
e
r
e
n
t
n
a
m
e
s
●
Most languages have an equivalent of this data
structure, but there are many names:
○
Java: HashMap
○
C#: Dictionary
○
C++: map
○
Python: dict
○
PHP: array
●
They all share the same properties.
○
You can store keys and values.
○
You cannot have duplicate keys
D
e
c
l
a
r
i
n
g
a
H
a
s
h
M
a
p
import java.util.HashMap;
HashMap<type,type> x = new HashMap<type,type>();
//You’ll replace each instance of type with an object
type.
// For example, String, Integer, Double, Dog
// Remember it’s Integer not int
S
t
o
r
e
s
a
K
e
y
a
n
d
V
a
l
u
e
m
a
p
p
i
n
g
●
For example, you could be storing the colors of fruits.
Then you would do:
○
FruitColors.put(“Banana”, “Yellow”);
○
FruitColors.put(“Apple”, “Green”);
■
This example uses a HashMap with two Strings.
●
Or Ages:
○
Ages.put(“John”,19);
○
Ages.put(“Jane”,18);
■
This example uses a HashMap with a String and an
Integer
●
Or Months:
○
Months.put(1,”Jan”);
○
Months.put(2,”Feb”);
O
t
h
e
r
H
a
s
h
M
a
p
m
e
t
h
o
d
s
●
.remove() // e.g. x.remove(“Apple”);
●
.get() // e.g. x.get(“Apple”); will return “Green”
●
.clear() //removes all keys from the list.
●
.size() //returns how many items are in the hashmap
You can iterate through the list with:
for(int monthNum : Months.keySet()) {System.out.println(monthNum); // This will print 1-12
}
for(String month : Months.values()) {System.out.println(month); // This will print Jan Feb…Dec
}
P
r
i
n
t
i
n
g
a
l
l
t
h
e
v
a
l
u
e
s
i
n
a
H
a
s
h
M
a
p
import java.util.HashMap;
HashMap<String,Integer> months = new
HashMap<String,Integer>();
months.put(“Jan”,1);
…
months.put(“Dec”,12);
for(String monthName : months.keySet()) {System.out.println(“Month “+monthName+” is month
number “+months.get(monthName));
}
C
#
:
D
i
c
t
i
o
n
a
r
y
using System.Collections.Generic;
Dictionary<string,int> months=new
Dictionary<string,int>();
months.Add(“Jan”,1);
months.Add(“Feb”,2);
…
//Another syntax:
months[“Dec”]=12;
O
t
h
e
r
D
i
c
t
i
o
n
a
r
y
m
e
t
h
o
d
s
●
.Remove() // e.g. x.Remove(“Apple”);
●
.Get() // e.g. x.Get(“Apple”); will return “Green”
●
.Clear() //removes all keys from the list.
●
.Count //returns how many items are in the hashmap
You can iterate through the list with:
foreach(int monthNum in Months.Keys) {Console.WriteLine(monthNum); // This will print 1-12
}
foreach(string month in Months.Values) {Console.WriteLine(month); // This will print Jan Feb…Dec
}
P
r
i
n
t
i
n
g
a
l
l
t
h
e
v
a
l
u
e
s
i
n
a
D
i
c
t
i
o
n
a
r
y
using System.Collections.Generic;
Dictionary<string,int> months = new
Dictionary<string,int>();
months[“Jan”]=1;
…
months[“Dec”]=12;
foreach(string monthName in months.Keys) {Console.WriteLine(monthName+" is month
"+months[monthName]);
}
A
s
s
o
c
i
a
t
e
d
A
r
r
a
y
●
HashMaps/Dictionaries vs Arrays?
●
Similarities:
○
Each cell of an Array or a HashMap/Dictionary
contain the SAME type.
○
You must declare the type when you create the data
structure.
●
Differences:
○
Arrays have a fixed size, HashMaps/Dictionaries grow
dynamically. In that way they are more like
ArrayLists/Lists
○
How the cells are named:
■
Array cells are automatically numbered 0, 1, 2, 3…
■
HashMaps/Dictionaries cells are named whatever you
want.
C
o
m
m
o
n
U
s
e
-
C
o
u
n
t
i
n
g
t
h
i
n
g
s
●
Imagine you have an array of doubles with student
grades.
●
We would like to count how many A’s, B’s, C’s, D’s,
F’s we have.
●
We’ll write a method which takes in an array of
doubles
●
It’ll iterate over the array:
○
Using a conditional it’ll check if each grade is >89.5 if
so it’ll add one to the number of A’s in the hashmap.
○
If the grade is greater then 79.5 it’ll increment the
number of B’s in the hashmap.
●
It returns the hashmap<String,int> where each key is
a letter grade and each value is how many of those
letter grades we saw
public static HashMap<String,Integer> countGrades(double[] grades) {HashMap<String,Integer> gradeMap =new HashMap<String,Integer>();
gradeMap.put("A",0); gradeMap.put("B",0); gradeMap.put("C",0); gradeMap.put("D",0); gradeMap.put("F",0); for(int i=0;i<grades.length;i++) { if(grades[i]>=89.5) { gradeMap.put("A",gradeMap.get("A")+1);}
else if(grades[i]>=79.5) { gradeMap.put("B",gradeMap.get("B")+1);}
else if(grades[i]>=69.5) { gradeMap.put("C",gradeMap.get("C")+1);}
else if(grades[i]>=59.5) { gradeMap.put("D",gradeMap.get("D")+1);}
else { gradeMap.put("F",gradeMap.get("F")+1);}
}
return(gradeMap);
}
public static Dictionary<string,int> countGrades(double[] grades) {Dictionary<string,int> gradeMap =new Dictionary<string,int>();
gradeMap["A"]=0;
gradeMap["B"]=0;
gradeMap["C"]=0;
gradeMap["D"]=0;
gradeMap["F"]=0;
for(int i=0;i<grades.Length;i++) { if(grades[i]>=89.5) {gradeMap["A"]++;
}
else if(grades[i]>=79.5) {gradeMap["B"]++;
}
else if(grades[i]>=69.5) {gradeMap["C"]++;
}
else if(grades[i]>=59.5) {gradeMap["D"]++;
}
else {gradeMap["F"]++;
}
}
return(gradeMap);
}
T
e
s
t
i
n
g
t
h
e
c
o
d
e
:
public static void Main (string[] args) { double[] grades=new double[] {100,83,32,59,87,72,100,90,100,20,77};Dictionary<string,int> letterGrades=countGrades(grades);
foreach(string letterGrade in letterGrades.Keys) {Console.WriteLine(letterGrade+": "+letterGrades[letterGrade]);
}
}
Output:
A: 4
B: 2
C: 2
D: 0
F: 3
B
i
g
(
O
)
o
f
H
a
s
h
M
a
p
s
/
D
i
c
t
i
o
n
a
r
i
e
s
●
Looking up a value in a HashMap or Dictionary is
generally considered O(1).
○
This is much like looking up a value in an Array.
●
The details are more complicated.
○
Values are stored in a very large array. A “hash”
function is used to pick which cell to store for example
“Apple” in.
○
The “Hash” function converts a string (the key) to an
integer.
○
A good hash function has no “collisions” meaning that
each key maps to given ID, and that ID shouldn’t be
used by any other key. This is very tricky, and
something you’ll study in Data Structures.
○
Collisions are a big problem here, when 2 keys “hash”
to the same value.
In this module, learn about Hash Maps, a common data structure used in various programming languages like Java, C#, C++, Python, and PHP. Hash Maps allow you to store key-value pairs without duplicate keys, making it efficient for mapping relationships between data elements. Explore how to declare, store, and manipulate data using Hash Maps, along with key methods and iteration techniques in different languages.
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
Module 8 - Part 5 Hash Maps
Introduction So far we ve learned about the following datastructures: Arrays ArrayList/Lists Linked Lists Stacks Queues Trees (BST) Graphs There is one more common data structure you should know about.
Known by different names Most languages have an equivalent of this data structure, but there are many names: Java: HashMap C#: Dictionary C++: map Python: dict PHP: array They all share the same properties. You can store keys and values. You cannot have duplicate keys
Declaring a HashMap import java.util.HashMap; HashMap<type,type> x = new HashMap<type,type>(); //You ll replace each instance of type with an object type. // For example, String, Integer, Double, Dog // Remember it s Integer not int
Stores a Key and Value mapping For example, you could be storing the colors of fruits. Then you would do: FruitColors.put( Banana , Yellow ); FruitColors.put( Apple , Green ); This example uses a HashMap with two Strings. Or Ages: Ages.put( John ,19); Ages.put( Jane ,18); This example uses a HashMap with a String and an Integer Or Months: Months.put(1, Jan ); Months.put(2, Feb );
Other HashMap methods .remove() // e.g. x.remove( Apple ); .get() // e.g. x.get( Apple ); will return Green .clear() //removes all keys from the list. .size() //returns how many items are in the hashmap You can iterate through the list with: for(int monthNum : Months.keySet()) { System.out.println(monthNum); // This will print 1-12 } for(String month : Months.values()) { System.out.println(month); // This will print Jan Feb Dec }
Printing all the values in a HashMap import java.util.HashMap; HashMap<String,Integer> months = new HashMap<String,Integer>(); months.put( Jan ,1); months.put( Dec ,12); for(String monthName : months.keySet()) { System.out.println( Month +monthName+ is month number +months.get(monthName)); }
C#: Dictionary using System.Collections.Generic; Dictionary<string,int> months=new Dictionary<string,int>(); months.Add( Jan ,1); months.Add( Feb ,2); //Another syntax: months[ Dec ]=12;
Other Dictionary methods .Remove() // e.g. x.Remove( Apple ); .Get() // e.g. x.Get( Apple ); will return Green .Clear() //removes all keys from the list. .Count //returns how many items are in the hashmap You can iterate through the list with: foreach(int monthNum in Months.Keys) { Console.WriteLine(monthNum); // This will print 1-12 } foreach(string month in Months.Values) { Console.WriteLine(month); // This will print Jan Feb Dec }
Printing all the values in a Dictionary using System.Collections.Generic; Dictionary<string,int> months = new Dictionary<string,int>(); months[ Jan ]=1; months[ Dec ]=12; foreach(string monthName in months.Keys) { Console.WriteLine(monthName+" is month "+months[monthName]); }
Associated Array HashMaps/Dictionaries vs Arrays? Similarities: Each cell of an Array or a HashMap/Dictionary contain the SAME type. You must declare the type when you create the data structure. Differences: Arrays have a fixed size, HashMaps/Dictionaries grow dynamically. In that way they are more like ArrayLists/Lists How the cells are named: Array cells are automatically numbered 0, 1, 2, 3 HashMaps/Dictionaries cells are named whatever you want.
Common Use - Counting things Imagine you have an array of doubles with student grades. We would like to count how many A s, B s, C s, D s, F s we have. We ll write a method which takes in an array of doubles It ll iterate over the array: Using a conditional it ll check if each grade is >89.5 if so it ll add one to the number of A s in the hashmap. If the grade is greater then 79.5 it ll increment the number of B s in the hashmap. It returns the hashmap<String,int> where each key is a letter grade and each value is how many of those letter grades we saw
public static HashMap<String,Integer> countGrades(double[] grades) { HashMap<String,Integer> gradeMap =new HashMap<String,Integer>(); gradeMap.put("A",0); gradeMap.put("B",0); gradeMap.put("C",0); gradeMap.put("D",0); gradeMap.put("F",0); for(int i=0;i<grades.length;i++) { if(grades[i]>=89.5) { gradeMap.put("A",gradeMap.get("A")+1); } else if(grades[i]>=79.5) { gradeMap.put("B",gradeMap.get("B")+1); } else if(grades[i]>=69.5) { gradeMap.put("C",gradeMap.get("C")+1); } else if(grades[i]>=59.5) { gradeMap.put("D",gradeMap.get("D")+1); } else { gradeMap.put("F",gradeMap.get("F")+1); } } return(gradeMap); }
public static Dictionary<string,int> countGrades(double[] grades) { Dictionary<string,int> gradeMap =new Dictionary<string,int>(); gradeMap["A"]=0; gradeMap["B"]=0; gradeMap["C"]=0; gradeMap["D"]=0; gradeMap["F"]=0; for(int i=0;i<grades.Length;i++) { if(grades[i]>=89.5) { gradeMap["A"]++; } else if(grades[i]>=79.5) { gradeMap["B"]++; } else if(grades[i]>=69.5) { gradeMap["C"]++; } else if(grades[i]>=59.5) { gradeMap["D"]++; } else { gradeMap["F"]++; } } return(gradeMap); }
Testing the code: public static void Main (string[] args) { double[] grades=new double[] {100,83,32,59,87,72,100,90,100,20,77}; Dictionary<string,int> letterGrades=countGrades(grades); foreach(string letterGrade in letterGrades.Keys) { Console.WriteLine(letterGrade+": "+letterGrades[letterGrade]); } } Output: A: 4 B: 2 C: 2 D: 0 F: 3
Big(O) of HashMaps/Dictionaries Looking up a value in a HashMap or Dictionary is generally considered O(1). This is much like looking up a value in an Array. The details are more complicated. Values are stored in a very large array. A hash function is used to pick which cell to store for example Apple in. The Hash function converts a string (the key) to an integer. A good hash function has no collisions meaning that each key maps to given ID, and that ID shouldn t be used by any other key. This is very tricky, and something you ll study in Data Structures. Collisions are a big problem here, when 2 keys hash to the same value.
