Hash-table:Basic Idea Hashing:the idea Q:When should we use hash table? What situations is the hash table suitable for? Feasible size Very large,but only a small E[O] part is used in an applica- E o Index distribution tion at a certain time. ● Collision handling E[k个 Hash Function Key Space E[m-1] 口卡+①，2是生QC MA Jun (Institute of Computer Software) Problem Solving May14,20203/34. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hash-table: Basic Idea Hashing: the idea Q : When should we use hash table? What situations is the hash table suitable for? Key Space x Very large, but only a small part is used in an applica￾tion at a certain time. · · · · · · E [0] E [1] E [m − 1] Feasible size E [k] Hash Function Index distribution Collision handling MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 3 / 34