tailieunhanh - Lecture Algorithms and data structures (CSC112) - Chapter 30

This chapter shows you how to apply your query formulation skills to building applications with views. This chapter also emphasizes views as the foundation for building database applications. Before discussing the link between views and database applications, essential background is provided. | 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: . | 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