CS 225 Lecture 31: Hashing Tables
18 Nov 2016
School
Department
Course
Professor
Document Summary
Declares an object of adt dictionary dict d; ex: insert is d[k] = v; Collision resolution strategy class dict (implemeneted with a hash table) k data---- hash function h(k) ---i index--- array of key, value. If the hash function is a bijection, you have a perfect hash function. So what do you do when you get two pieces of data with the same key where h(k_1) == h(k_2) Violation of 1 to 1 is called a collision in the hash table. Roll 5 dice: puzzle called petals around the rose find a center pip on the die, then count the dots around the ip. 5 die ------ [hash function] ------ array the keys are the die roll, how many 5 die rolls are there? key word derangements to calculate the # of die rolls. // the amount of rolls is too greate for our hash table.
