tailieunhanh - Lecture Java methods: Object-oriented programming and data structures (2nd AP edition): Chapter 25 - Maria Litvin, Gary Litvin

Chapter 25 - Lookup tables and hashing. After you have mastered the material in this chapter, you will be able to: Learn about lookup tables, learn about hashing, review and . | Lookup Tables and Hashing Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 2nd AP edition with GridWorld 25- A rather technical chapter. Objectives: Learn about lookup tables Learn about hashing Review and 25- You do not need to implement your own hash tables: case studies and labs use and . However, you need to understand how HashSet and HashMap work. Lookup Tables A lookup table is an array that helps to find data very quickly. The array stores references to data records (or some values). A data record is identified by some key. The value of a key is directly translated into an array index using a simple formula. 25- A lookup table may waste some space, but it provides instantaneous (O(1)) access to the data — no search is needed. Lookup Tables (cont’d) Only one key can | Lookup Tables and Hashing Copyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 2nd AP edition with GridWorld 25- A rather technical chapter. Objectives: Learn about lookup tables Learn about hashing Review and 25- You do not need to implement your own hash tables: case studies and labs use and . However, you need to understand how HashSet and HashMap work. Lookup Tables A lookup table is an array that helps to find data very quickly. The array stores references to data records (or some values). A data record is identified by some key. The value of a key is directly translated into an array index using a simple formula. 25- A lookup table may waste some space, but it provides instantaneous (O(1)) access to the data — no search is needed. Lookup Tables (cont’d) Only one key can be mapped onto a particular index (no collisions). The index that corresponds to a key must fall into the valid range (from 0 to ). Access to data is “instantaneous” (O(1)). 25- In certain applications a look up table can be a 2-D array. Lookup Tables: Example 1 Zip codes Corresponding locales Some table entries remain unused 25- Last time we checked, the lowest valid zip code was 00501 and the highest 99950. Lookup Tables: Example 2 private static final int [ ] n_thPowerOf3 = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683 }; . // precondition: 0 25- It is not hard to calculate a power of 3. A lookup table is more appropriate when the function is harder to compute and we need to compute it frequently, but not necessarily with the highest precision. For example, we can approximate a function defined on [0, 1] by its values in 1000 points evenly distributed over [0, 1]. Lookup Tables: Example