The University of Arizona

Events & News

CS Colloquium

DateThursday, February 5, 2015
Time11:00 am
Concludes12:15 pm
LocationGould-Simpson 906
DetailsPlease join us for coffee and light refreshments at 11am in Gould-Simpson 906.

Faculty Host: Patrick Homer
SpeakerMichael Chang
AffiliationStanford University

Implementing Maps in a Hash Table

In this talk, we'll discuss implementing maps using a data structure called a hash table. Assuming the existence of a hash function, we'll first see how hash tables can lead to extremely fast lookup and insertion for very large maps.

We'll explore how to modify a map implementation that uses a linked list to one that uses a hash table, which requires surprisingly few changes. Finally, we'll explore the details behind the hash function, identifying important properties for a good function and how the choice of function impacts the performance of the map.


Michael Chang has a BS in Computer Science and is completing an MS in Computer Science both at Stanford University. His specialization for his Master's Degree is in Systems / Computer and Network Security.