南京大学：《计算机问题求解》课程教学资源（课件讲稿）Hashing方法

Problem Solving 2-12 Hashing MA Jun Institute of Computer Software May10,2022 +口，4y，4三，4=，三0QC

Problem Solving 2-12 Hashing MA Jun Institute of Computer Software May 10, 2022

Contents Hash-table:Basic Idea ②Hash Functions ③Collision Resolution 4口4y，4三，4兰，左0QC

Contents 1 Hash-table: Basic Idea 2 Hash Functions 3 Collision Resolution

Applications of Hashing There are many applications of hashing(not limited to hash table), including modern day cryptography hash functions.Some of these applications are listed below: Message Digest o Password Verification o Data Structures (Programming Languages) ●Compiler Operation Rabin-Karp Algorithm o Linking File Name and Path Together https://www.geeksforgeeks.org/applications-of-hashing/ 4口4的，在+Q0 MA Jun (Institute of Computer Software) Problem Solving May10.2022 1/34

Applications of Hashing There are many applications of hashing (not limited to hash table), including modern day cryptography hash functions. Some of these applications are listed below: Message Digest Password Verification Data Structures (Programming Languages) Compiler Operation Rabin-Karp Algorithm Linking File Name and Path Together https://www.geeksforgeeks.org/applications-of-hashing/ MA Jun (Institute of Computer Software) Problem Solving May 10, 2022 1 / 34

Contents Hash-table:Basic Idea Hash Functions Collision Resolution 4口4y，4三，4兰，左0QC

Contents 1 Hash-table: Basic Idea 2 Hash Functions 3 Collision Resolution

Hash-table:Basic Idea Many applications require a Dynamic Set that supports only the dictionary operations INSERT,SEARCH,and DELETE. 口卡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-(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 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 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 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 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 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 10, 2022 3 / 34