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. 4口4的，在+是Q0 MA Jun (Institute of Computer Software) Problem Solving May10.2022 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). MA Jun (Institute of Computer Software) Problem Solving May 10, 2022 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-e(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 May10.2022 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). MA Jun (Institute of Computer Software) Problem Solving May 10, 2022 2 / 34
Hash-table:Basic Idea Hashing:the idea Q:When should we use hash table? What situations is the hash table suitable for?
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 10, 2022 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
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 10, 2022 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 10, 2022 3 / 34