Содержание
- 2. Dictionary Dictionary: Dynamic-set data structure for storing items indexed using keys. Supports operations Insert, Search, and
- 3. Direct-address Tables Direct-address Tables are ordinary arrays. Facilitate direct addressing. Element whose key is k is
- 4. Hash Tables Notation: U – Universe of all possible keys. K – Set of keys actually
- 5. Hashing Hash function h: Mapping from U to the slots of a hash table T[0..m–1]. h
- 6. Hashing 0 m–1 h(k1) h(k4) h(k2)=h(k5) h(k3) U (universe of keys) K (actual keys) k1 k2
- 7. Issues with Hashing Multiple keys can hash to the same slot – collisions are possible. Design
- 8. Methods of Resolution Chaining: Store all elements that hash to the same slot in a linked
- 9. Collision Resolution by Chaining 0 m–1 h(k1)=h(k4) h(k2)=h(k5)=h(k6) h(k3)=h(k7) U (universe of keys) K (actual keys)
- 10. Collision Resolution by Chaining k2 0 m–1 U (universe of keys) K (actual keys) k1 k2
- 11. Hashing with Chaining Dictionary Operations: Chained-Hash-Insert (T, x) Insert x at the head of list T[h(key[x])].
- 12. Analysis on Chained-Hash-Search Load factor α=n/m = average keys per slot. m – number of slots.
- 13. Expected Cost of an Unsuccessful Search Proof: Any key not already in the table is equally
- 14. Expected Cost of a Successful Search Proof: The probability that a list is searched is proportional
- 15. Expected Cost of a Successful Search Proof (contd): Let xi be the ith element inserted into
- 16. Proof – Contd. (linearity of expectation) Expected total time for a successful search = Time to
- 17. Expected Cost – Interpretation If n = O(m), then α=n/m = O(m)/m = O(1). ⇒ Searching
- 18. Good Hash Functions Satisfy the assumption of simple uniform hashing. Not possible to satisfy the assumption
- 19. Keys as Natural Numbers Hash functions assume that the keys are natural numbers. When they are
- 20. Division Method Map a key k into one of the m slots by taking the remainder
- 21. Multiplication Method If 0 where kA mod 1 means the fractional part of kA, i.e., kA
- 22. Multiplication Mthd. – Implementation Choose m = 2p, for some integer p. Let the word size
- 23. Multiplication Mthd – Implementation We want ⎣m (kA mod 1)⎦. We could get that by shifting
- 25. Скачать презентацию