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

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

Problem Solving 2-12 Hashing MA Jun Institute of Computer Software May 14, 2020 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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 Password Verification oData Structures (Programming Languages) 。Compiler Operation Rabin-Karp Algorithm o Linking File Name and Path Together https://www.geeksforgeeks.org/applications-of-hashing/ 4口卡40，在是生Q0 MA Jun (Institute of Computer Software) Problem Solving May14.20201/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 14, 2020 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 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. 口卡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 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

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 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

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 14, 2020 3 / 34