TAILIEUCHUNG - 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 .
đang nạp các trang xem trước
