Guide
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 4
lab_hash
Hellish Hash Tables
!"#$%&'(%)*+%,)-./%0&
!1234#5 6'7%8'591": 6'7%;<=9#;
Assignment Description
>5%:8=;%<'7%31"%?=<<%7#%=@A<#@#5:=54%B"5C:=15;%15%8';8%:'7<#;%?=:8%:8(##%9=BB#(#5:%C1<<=;=15%(#;1<":=15%;:(':#4=#;
D%;#A'(':#%C8'=5=54+%<=5#'(%A(17=54+%'59%91"7<#%8';8=54E%F8#;#%8';8%:'7<#;%;#(G#%'5%=@A<#@#5:':=15%1B%:8#
9=C:=15'(3%'7;:('C:%9':'%:3A#E
Lab Insight
H';8=54%=;%G#(3%A1?#(B"<%';%=:%#5'7<#;%";%:1%7"=<9%9':'%;:("C:"(#%<=I#%8';8%:'7<#;%'59%@'A;E%J5%:1A%1B%?8=C8+
:8#(#%'(#%G'(=':=15;%1B%8';8=54%:8':%C'5%7#%";#9%:1%8#<A%#5C(3A:%9':'E%>B%31"%'(#%=5:#(#;:#9%=5%<#'(5=54%@1(#
'71":%:8#%'AA<=C':=15;%1B%8';8=54+%31"%C'5%:'I#%KL%M/N%OAA<=#9%K(3A:14('A83+%KL%MP*%K1@A":#(%L#C"(=:3%>+
'59%KL%MP)%K1@A":#(%L#C"(=:3%>>E
Getting Set Up
Q(1@%31"(%KL%,,.%4=:%9=(#C:1(3+%("5%:8#%B1<<1?=54%15%RSL$
git fetch release
git merge release/lab_hash -m "Merging initial lab_hash files"
>B%31"T(#%15%31"(%1?5%@'C8=5#+%31"%@'3%5##9%:1%("5$
git fetch release
git merge --allow-unrelated-histories release/lab_hash -m "Merging initial lab_hash files"
UA15%'%;"CC#;;B"<%@#(4#+%31"(%<'7V8';8%B=<#;%'(#%51?%=5%31"(%lab_hash%9=(#C:1(3E
F8#%C19#%B1(%:8=;%'C:=G=:3%(#;=9#;%=5%:8#%lab_hash/%9=(#C:1(3E%W#:%:8#(#%73%:3A=54%:8=;%=5%31"(%?1(I=54%9=(#C:1(3$
cd lab_hash/
Notes About list Iterators
S8#5%31"%'(#%?1(I=54%?=:8%:8#%L#A'(':#%K8'=5=54%H';8%F'7<#+%31"%?=<<%5##9%:1%=:#(':#%1G#(%:8#%<=5I#9%<=;:%1B%'
4=G#5%7"CI#:E%L=5C#%:8#%8';8%:'7<#;%'(#%:#@A<':=X#9+%81?#G#(+%:8=;%C'";#;%";%'%;<=48:%8#'9'C8#%;35:'C:=C'<<3%=5
KYYE%F1%9#B=5#%'%list%=:#(':1(%15%'%4=G#5%7"CI#:+%31"%?=<<%5##9%:1%9#C<'(#%=:%';%B1<<1?;$
typename list< pair<K,V> >::iterator it = table[i].begin();
!%>B%31"%?'5:%:1%;A##9%"A%C1@A=<#%:=@#%15%'%make+%:(3%";=54%make -j <target>+%=#%make -j test
Assignment
Description
Lab Insight
Getting Set Up
Notes About
list Iterators
Separate
Chaining Hash
Table
Linear Probing
Hash Table
Double
Hashing Hash
Table
Committing
Your Code
Grading
Information
Separate Chaining Hash Table
JA#5%31"(%schashtable.cppE%>5%:8=;%B=<#+%;#G#('<%B"5C:=15;%8'G#%51:%7##5%=@A<#@#5:#9D31"(%Z17%=;%:1
=@A<#@#5:%:8#@E
insert
insert+%4=G#5%'%key%'59%'%value+%;81"<9%=5;#(:%:8#%(key, value)%A'=(%=5:1%:8#%8';8%:'7<#E
[1"%91%51:%5##9%:1%C15C#(5%31"(;#<B%?=:8%9"A<=C':#%I#3;E%S8#5%=5%C<=#5:%C19#%'59%";=54%1"(%8';8%:'7<#;+
:8#%A(1A#(%A(1C#9"(#%B1(%"A9':=54%'%I#3%=;%:1%B=(;:%(#@1G#%:8#%I#3+%:8#5%(#\=5;#(:%:8#%I#3%?=:8%:8#%5#?
9':'%G'<"#E
H#(#%=;%:8#%!1234#5%B1(%insertE
find
4=G#5%'%key+%;81"<9%(#:"(5%:8#%C1((#;A159=54%value%';;1C=':#9%?=:8%:8':%I#3
H#(#%=;%:8#%!1234#5%B1(%findE
remove
W=G#5%'%I#3+%(#@1G#%=:%B(1@%:8#%8';8%:'7<#E
>B%:8#%4=G#5%I#3%=;%51:%=5%:8#%8';8%:'7<#+%91%51:8=54E
[1"%@'3%B=59%:8#%!1234#5%B1(%remove%8#<AB"<E
resizeTable
F8=;%=;%C'<<#9%?8#5%:8#%<1'9%B'C:1(%B1(%1"(%:'7<#%=;% E
>:%;81"<9%(#;=X#%:8#%=5:#(5'<%'(('3%B1(%:8#%8';8%:'7<#E%U;#%:8#%(#:"(5%G'<"#%1B%findPrime%?=:8%'%A'('@#:#(
1B%91"7<#%:8#%C"((#5:%;=X#%:1%;#:%:8#%;=X#E%L##%1:8#(%C'<<;%:1%resize%B1(%(#B#(#5C#E
H#(#%=;%:8#%!1234#5%B1(%resizeTableE
Linear Probing Hash Table
JA#5%31"(%lphashtable.cppE%>5%:8=;%B=<#+%31"%?=<<%7#%=@A<#@#5:=54%:8#%B1<<1?=54%B"5C:=15;E
insert
insert+%4=G#5%'%key%'59%'%value+%;81"<9%=5;#(:%:8#%(key, value)%A'=(%=5:1%:8#%8';8%:'7<#E
]#@#@7#(%:8#%C1<<=;=15%8'59<=54%;:(':#43%B1(%<=5#'(%A(17=54^%_F1%@'=5:'=5%C1@A':=7=<=:3%?=:8%1"(%1":A":;+
31"%;81"<9%A(17#%73%@1G=54%B1(?'(9;%:8(1"48%:8#%=5:#(5'<%'(('3+%51:%7'CI?'(9;`E
[1"%91%51:%5##9%:1%C15C#(5%31"(;#<B%?=:8%9"A<=C':#%I#3;E%S8#5%=5%C<=#5:%C19#%'59%";=54%1"(%8';8%:'7<#;+
:8#%A(1A#(%A(1C#9"(#%B1(%"A9':=54%'%I#3%=;%:1%B=(;:%(#@1G#%:8#%I#3+%:8#5%(#\=5;#(:%:8#%I#3%?=:8%:8#%5#?
9':'%G'<"#E
H#(#%=;%:8#%!1234#5%B1(%insertE
[1"%&ULF%8'59<#%C1<<=;=15;%=5%31"(%insert%B"5C:=15+%1(%31"(%8';8%:'7<#%?=<<%7#%7(1I#5^
"%>B%31"%";#%:8#%list::erase()%B"5C:=15+%7#%'9G=;#9%:8':%=B%31"%#(';#%:8#%#<#@#5:%A1=5:#9%:1%73%'5
=:#(':1(%:8':%:8#%A'('@#:#(%=:#(':1(%=;%51%<154#(%G'<=9E%Q1(%=5;:'5C#$
typename list< pair<K,V> >::iterator it = table[i].begin();
table[i].erase(it);
it++;
=;%=5G'<=9%7#C'";#%it%=;%=5G'<=9':#9%'B:#(%:8#%C'<<%:1%erase()E%So, if you are looping with an iterator,
remember a break statement after you call erase()!
ge0.7
findIndex
4=G#5%'%key+%;81"<9%(#:"(5%:8#%C1((#;A159=54%index%';;1C=':#9%?=:8%:8':%I#3
H#(#%=;%:8#%!1234#5%B1(%findIndexE
remove
W=G#5%'%I#3+%(#@1G#%=:%B(1@%:8#%8';8%:'7<#E
>B%:8#%4=G#5%I#3%=;%51:%=5%:8#%8';8%:'7<#+%91%51:8=54E
[1"%@'3%B=59%:8#%!1234#5%B1(%remove%8#<AB"<E
resizeTable
F8=;%=;%C'<<#9%?8#5%:8#%<1'9%B'C:1(%B1(%1"(%:'7<#%=;% E
>:%;81"<9%(#;=X#%:8#%=5:#(5'<%'(('3%B1(%:8#%8';8%:'7<#E%U;#%:8#%(#:"(5%G'<"#%1B%findPrime%?=:8%'%A'('@#:#(
1B%91"7<#%:8#%C"((#5:%;=X#%:1%;#:%:8#%;=X#E%L##%1:8#(%C'<<;%:1%resize%B1(%(#B#(#5C#E
H#(#%=;%:8#%!1234#5%B1(%resizeTableE
Double Hashing Hash Table
JA#5%31"(%dhhashtable.cppE%>5%:8=;%B=<#+%31"%?=<<%7#%=@A<#@#5:=54%:8#%B1<<1?=54%B"5C:=15;E
insert
insert+%4=G#5%'%key%'59%'%value+%;81"<9%=5;#(:%:8#%(key, value)%A'=(%=5:1%:8#%8';8%:'7<#E
]#@#@7#(%:8#%C1<<=;=15%8'59<=54%;:(':#43%B1(%91"7<#%8';8=54^%_F1%@'=5:'=5%C1@A':=7=<=:3%?=:8%1"(
1":A":;+%31"%;81"<9%A(17#%73%@1G=54%B1(?'(9;%:8(1"48%:8#%=5:#(5'<%'(('3+%51:%7'CI?'(9;`E
[1"%91%51:%5##9%:1%C15C#(5%31"(;#<B%?=:8%9"A<=C':#%I#3;E%S8#5%=5%C<=#5:%C19#%'59%";=54%1"(%8';8%:'7<#;+
:8#%A(1A#(%A(1C#9"(#%B1(%"A9':=54%'%I#3%=;%:1%B=(;:%(#@1G#%:8#%I#3+%:8#5%(#\=5;#(:%:8#%I#3%?=:8%:8#%5#?
9':'%G'<"#E
H#(#%=;%:8#%!1234#5%B1(%insertE
[1"%&ULF%8'59<#%C1<<=;=15;%=5%31"(%insert%B"5C:=15+%1(%31"(%8';8%:'7<#%?=<<%7#%7(1I#5^
findIndex
4=G#5%'%key+%;81"<9%(#:"(5%:8#%C1((#;A159=54%index%';;1C=':#9%?=:8%:8':%I#3
H#(#%=;%:8#%!1234#5%B1(%findIndexE
remove
W=G#5%'%I#3+%(#@1G#%=:%B(1@%:8#%8';8%:'7<#E
>B%:8#%4=G#5%I#3%=;%51:%=5%:8#%8';8%:'7<#+%91%51:8=54E
[1"%@'3%B=59%:8#%!1234#5%B1(%remove%8#<AB"<E
Committing Your Code
#%W"=9#$%H1?%:1%;"7@=:%KL%,,.%?1(I%";=54%4=:
Grading Information
F8#%B1<<1?=54%B=<#;%_'59%Ja6[%:81;#%B=<#;^^`%'(#%";#9%B1(%4('9=54%:8=;%<'7$
dhhashtable.cpp
lphashtable.cpp
schashtable.cpp
>B%31"%@19=B3%'53%1:8#(%B=<#;+%:8#3%?=<<%51:%7#%4('77#9%B1(%4('9=54%'59%31"%@'3%#59%"A%?=:8%'%b;:"A=9%X#(1Ec
ge0.7
