Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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 .
