Chapter 24 - 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 . | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Lookup Tables and Hashing 24- A rather technical chapter. Objectives: Learn about lookup tables Learn about hashing Review and 24- 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 a one-dimensional 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. 24- A lookup table may waste 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 | Java Methods A & AB Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin Copyright © 2006 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Lookup Tables and Hashing 24- A rather technical chapter. Objectives: Learn about lookup tables Learn about hashing Review and 24- 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 a one-dimensional 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. 24- A lookup table may waste 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)). 24- A lookup table may waste space, but it provides instantaneous (O(1)) access to the data — no search is needed. Lookup Tables: Example 1 Zip codes Corresponding locales Some table entries remain unused 24- Last time we checked, the lowest valid zip code was 00601 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 24- 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
