Chapter 7 Hashing
Chapter 7 Hashing
7.1 Dictionaries a dictionary is a collection of elements; each element has a field called key, and no two elements have the same key value Operations Insert(x) insert an element with a specified key value x Search(k, x): search an element with a specified key value k, put the element into x Delete(k, x): delete an element with a specified key value k,put the element into x
7.1 Dictionaries A dictionary is a collection of elements; each element has a field called key, and no two elements have the same key value. Operations: • Insert(x): insert an element with a specified key value x • Search(k,x):search an element with a specified key value k, put the element into x • Delete(k,x):delete an element with a specified key value k,put the element into x
7.2 Linear List representation a dictionary can be maintained as an ordered Linear list(er, e2,...) e: are dictionary elements and their keys are increased from left to right We may define two classes Sorted List and Sorted Chain to facilitate this representation
7.2 Linear List Representation • A dictionary can be maintained as an ordered Linear List(e1 ,e2 ,……) • ei are dictionary elements and their keys are increased from left to right • We may define two classes Sorted List and Sorted Chain to facilitate this representation
1. SortedList Sequential Search(program 2.1 a012 The array can be ordered or unordered Time complexity ASLucC=(1+2+..tn)/n (n+1)*n/2n=(n+1)2=O(n)
1. SortedList Sequential Search(program 2.1) The array can be ordered or unordered Time complexity: ASLsucc=(1+2+……+n)/n = ((n+1)*n/2)/n=(n+1)/2=O(n) a0 a1 a2 an-1 a 0 1 2 n-1
2. Binary search It is suitable for sorted list example a:012345678 3468 10 Search x=6 low midI mid mid2 high
2.Binary Search It is suitable for sorted list example -1 0 1 3 4 6 8 10 12 a: 0 1 2 3 4 5 6 7 8 low mid1 mid3 mid2 high Search x=6