Hash-table:Basic Idea Many applications require a Dynamic Set that supports only the dictionary operations INSERT,SEARCH,and DELETE. Searching for an element in a hash table can take as long as searching for an element in a linked list (n)time in the worst case. 口卡40,1注·4是生Q0 MA Jun (Institute of Computer Software) Problem Solving May14.20202/34
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hash-table: Basic Idea Many applications require a Dynamic Set that supports only the dictionary operations Insert, Search, and Delete. Searching for an element in a hash table can take as long as searching for an element in a linked list Θ(n) time in the worst case. Under reasonable assumptions, the average time to search for an element in a hash table is Θ(1). MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 2 / 34
Hash-table:Basic Idea Many applications require a Dynamic Set that supports only the dictionary operations INSERT,SEARCH,and DELETE. Searching for an element in a hash table can take as long as searching for an element in a linked list (n)time in the worst case. Under reasonable assumptions,the average time to search for an element in a hash table is (1). 口卡4①，怎4，空月Q0 MA Jun (Institute of Computer Software) Problem Solving May14.20202/34
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hash-table: Basic Idea Many applications require a Dynamic Set that supports only the dictionary operations Insert, Search, and Delete. Searching for an element in a hash table can take as long as searching for an element in a linked list Θ(n) time in the worst case. Under reasonable assumptions, the average time to search for an element in a hash table is Θ(1). MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 2 / 34
Hash-table:Basic Idea Hashing:the idea Q:When should we use hash table? What situations is the hash table suitable for? 口卡4心，之·生，生
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 application 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
Hash-table:Basic Idea Hashing:the idea Q:When should we use hash table? What situations is the hash table suitable for? Key Space 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 application 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
Hash-table:Basic Idea Hashing:the idea Q:When should we use hash table? What situations is the hash table suitable for? Very large,but only a small part is used in an applica- tion at a certain time. Key Space
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 application 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