TAILIEUCHUNG - Lecture Algorithms and data structures: Chapter 30 - Hashing

This chapter presents the following content: More of an interactive demonstration than an animation, demonstrate conceptual execution model of Type II nested queries, type II nested queries are important for solving problems involving difference operator, problems with difference are not common,. | Review Graph Directed Graph Undirected Graph Sub-Graph Spanning Sub-Graph Degree of a Vertex Weighted Graph Elementary and Simple Path Link List Representation 1 Traversing a Graph Breadth First Search (BFS) Depth First Search (DFS) 2 Hashing Hash Function Properties of Hash Function Division Method Mid-Square Method Folding Method Hash Collision Open addressing Chaining Bucket addressing 3 Introduction The searching time of each searching technique depends on the comparison. ., n comparisons required for an array A with n elements To increase the efficiency, ., to reduce the searching time, we need to avoid unnecessary comparisons Hashing is a technique where we can compute the location of the desired record in order to retrieve it in a single access (or comparison) Let there is a table of n employee records and each employee record is defined by a unique employee code, which is a key to the record and employee name If the key (or employee code) is used as the array index, then the record can be accessed by the key directly 4 If L is the memory location where each record is related with the key If we can locate the memory address of a record from the key then the desired record can be retrieved in a single access For notational and coding convenience, we assume that the keys in k and the address in L are (decimal) integers So the location is selected by applying a function which is called hash function or hashing function from the key k Unfortunately such a function H may not yield different values (or index); it is possible that two different keys k1 and k2 will yield the same hash address This situation is called Hash Collision, which is discussed later 5 Hash Function The basic idea of hash function is the transformation of the key into the corresponding location in the hash table A Hash function H can be defined as a function that takes key as input and transforms it into a hash table index 6 Properties of Hash Function A good hash function should: .

• Cơ sở dữ liệu
• Data structures
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Design techniques
• Cấu trúc dữ liệu
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Memory allocation
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming