TAILIEUCHUNG - Lecture Data structures and other objects using C++ - Chapter 12: Hash tables

Chapter 12 discusses several ways of storing information in an array, and later searching for the information. Hash tables are a common approach to the storing/searching problem. This presentation introduces hash tables. | Chapter 12 discusses several ways of storing information in an array, and later searching for the information. Hash tables are a common approach to the storing/searching problem. This presentation introduces hash tables. Hash Tables Data Structures and Other Objects Using C++ This lecture illustrates hash tables, using open addressing. Before this lecture, students should have seen other forms of a Dictionary, where a collection of data is stored, and each data item has a key associated with it. What is a Hash Table ? The simplest kind of hash table is an array of records. This example has 701 records. [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] An array of records . . . [ 700] This lecture introduces hash tables, which are an array-based method for implementing a Dictionary. You should recall that we have seen dictionaries implemented in other ways, for example with a binary search tree. The abstract properties of a dictionary remain the same: We can insert items in the dictionary, and each item has a key associated with it. When we want to retrieve an item, we specify only the key, and the retrieval process finds the associated data. What we do now is use an array to implement the dictionary. The array is an array of records. In this example, we could store up to 701 records in the array. What is a Hash Table ? Each record has a special field, called its key. In this example, the key is a long integer field called Number. [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] . . . [ 700] [ 4 ] Number 506643548 Each record in the array contains two parts. The first part is a number that we'll use for the key of the item. We could use something else for the keys, such as a string. But for a hash table, numbers make the most convenient keys. What is a Hash Table ? The number might be a person's identification number, and the rest of the record has information about the person. [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] . . . [ 700] [ 4 ] Number 506643548 The numbers might be identification numbers

• Kỹ thuật lập trình
• Data structures
• Cấu trúc dữ liệu
• Hash tables
• The hash value
• Searching problem
• Storing problem
• 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
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• Computer science
• Design of data structures
• Algorithms in Java
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming