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
Example a:012345678 10134681012 Search x=6 midI mid 3 mid2 high 1)amid=x, found 2)amid]>x, x is in the left half of the array, search again 3)amid]x, x is in the right half of the array, search again
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 1) a[mid]=x, found 2) a[mid]>x, x is in the left half of the array,search again 3) a[mid]<x, x is in the right half of the array,search again
Program--binary search Template int SortedList: BinarySearch(const T&x)const i int high=n-1, low=0, mid while(lowx)high=mid-1 else return mid freturn-1
Program—binary search Template int SortedList::BinarySearch(const T&x)const { int high=n-1, low=0, mid; while(lowx) high=mid-1; else return mid; }return –1; }
Analysis of binary search time complexity Best case: compare one time Worst case: no longer than the height of the binary search tree Average compare times
Analysis of binary search time complexity: • Best case: compare one time • Worst case: no longer than the height of the binary search tree • Average compare times:
2. Sorted Chain class sorted Chain(program 7-1) Search Delete(program 7-2) Insert(program 7-3)
2. SortedChain class SortedChain (program 7-1) Search ,Delete(program 7-2) Insert (program 7-3)
7.3 Hashing 1. deal hashing O() Another representation of a dictionary is to use hashing Address=hash(key), also called name-address function
7.3 Hashing 1.Ideal hashing O(1) • Another representation of a dictionary is to use hashing • Address=hash(key), also called : name-address function