tailieunhanh - Lecture Data structures and algorithms in Java (6th edition): Chapter 10.1 - Goodrich, Tamassia, Goldwasser

This chapter provides knowledge of hash tables. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Hash Tables 3/19/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Hash Tables 0 1 2 3 4 © 2014 Goodrich, Tamassia, Godlwasser Hash Tables ∅ 025-612-0001 981-101-0002 ∅ 451-229-0004 1 Recall the Map ADT q   q   q   q   q   q   q   get(k): if the map M has an entry with key k, return its associated value; else, return null put(k, v): insert entry (k, v) into the map M; if key k is not already in M, then return null; else, return old value associated with k remove(k): if the map M has an entry with key k, remove it from M and return its associated value; else, return null size(), isEmpty() entrySet(): return an iterable collection of the entries in M keySet(): return an iterable collection of the keys in M values(): return an iterator of the values in M © 2014 Goodrich, Tamassia, Godlwasser Hash Tables 2 1 Hash Tables 3/19/14 Intuitive Notion of a Map q   q   Intuitively, a map M supports the abstraction of using keys as indices with a syntax such as M[k]. As a mental warm-up, consider a restricted setting in which a map with n items uses keys that are known to be integers in a range from 0 to N − 1, for some N ≥ n. © 2014 Goodrich, Tamassia, Godlwasser Hash Tables 3 More General Kinds of Keys q   But what should we do if our keys are not integers in the range from 0 to N – 1? n   n   Use a hash function to map general keys to corresponding indices in a table. For instance, the last four digits of a Social Security number. 0 1 2 3 4 ∅ 025-612-0001 981-101-0002 ∅ 451-229-0004 © 2014 Goodrich, Tamassia, Godlwasser Hash Tables 4 2 Hash Tables 3/19/14 Hash Functions and Hash Tables q   q   q   q   q   A hash function h maps keys of a given type to integers in a fixed interval [0, N - 1] Example: h(x) = x mod N is a hash function for integer keys The integer h(x) is called the hash value of key x A hash table for a .