Hashing (11)
Michael L. Littman
October 15th, 1998
SPELL CHECKING
Dynamic Dictionary
Dictionary
Implementing a Dictionary
Similar Applications
HASHING BASICS
Motivation
Universal Concepts
Extending Tables
Hash Function
Collisions
COLLISION RESOLUTION
Chaining: Basic Idea
Chaining: Evaluation
Open Addressing
Probing
Problem with Delete
Linear Probing
Desirable Property of Hash Functions
ANALYSIS
Worst Case
Uniform-Hashing Assumption
Comments on the Assumption
Chaining Analysis
Open-Addressing Analysis
Punchline
Universal Hashing
DYNAMIC OPERATIONS
Data Structures
Operations
Combining Data Structures
Next:
SPELL CHECKING
