Week 9 - Hash Tables

Learning objectives

  • Describe how to construct a hash function for various types of data
  • Implement a hash table
  • Represent a graph with an adjacency matrix or adjacency list
  • Execute basic search-based algorithms in a graph

Class Schedule

Monday

  • Hashing

Tuesday

  • Hash Tables
  • Std Unordered Set/Map

Wednesday

  • Graphs & Searches

Thursday

  • Holiday

Topics

Hashing

  • Hashing is an important general concept in CS. It is the idea of transforming a large chunk of information into a fixed-sized, smaller string. Hashing is used in various cryptography and security-related algorithms and to build data structures. Watch these videos for more information:

  • Read Ch 24.1-24.3

Hash Tables

  • Read Ch 24.4-24.7

  • Watch these videos:

Other Hash Table Collision Strategies

  • Linear probing is not the only way to resolve collisions. Watch this video to learn about other strategies. It also covers the standard data types that are built with Hash Tables: std::unordered_map and std::unordered_set:

Graphs & Basic Searches

  • Graphs are the generalized idea of nodes (or vertexes) connected by edges. The linked lists and trees we have learned about are just specific forms of graphs. Watch this video to learn about the general concept of graphs:

  • Read Ch 26.1-26.3

  • Do the Graph WS