- What not to use:
- Do not use
a hash table
Reason:
- Hash table entries
are inserted in a
random position into
the hash table
- The ordering property is not implementable using a hash table
Result:
- You cannot implement the
methods
firstEntry(),
lastEntry(),
floorEntry(k),...
easily if you use
a hash table data structure
(To find the smallest key value, you need to search the entire hash table !!!)
- Hash table entries
are inserted in a
random position into
the hash table
- Do not use
a heap
Reason:
- A heap can
easily find
the largest
(or the smallest)
key
- But it will not allow you to find the next smaller/larger key value than a specific value k easily
- A heap can
easily find
the largest
(or the smallest)
key
- Do not use
a hash table
- Possible choices of data structure for ordered map:
- An ordered list
(Use a double list so you can traverse the list forward and backward easily)
- A sorted array
- A binary search tree !!!
The entries in an binary serach tree is "some what" ordered
More on this subject later
- An ordered list
- Simplest data structure to implement ordered map:
- A sorted array
- Running times:
- The lookup operation:
O(log(n))
using a binary search
-
(Running time for binary search is
O(log(N)))
- Insert:
O(n)
-
(We need to move array elements
to make space for the
insertion.
You may need to more all n elements if the inserted entry occupies the first location)
- Delete:
O(n)
-
(We need to move array elements
to make space for the
insertion.
You may need to more all n elements if the inserted entry occupies the first location)
- The lookup operation:
O(log(n))
using a binary search
- Disadvantage:
- May need to increase the array size (copy old array !) dynamically to allow growth
- A sorted array
- Lookup algorithm (pseudo code):
Value Lookup(Key k) { e = BinarySearch(k); // Binary search works on sorted arrays !!! if ( e.key == k ) { return e.value; // Return value } else { return null; // Not found } }
- Insert algorithm (pseudo code):
Insert(Key k, Value v) { Find first element e such that: e.key ≥ k (with a modified binary search) // ........... e ......... // key < k | | // +-----------+ // key >= k if ( e.key == k ) e.value = v; // Replace value else { for ( j = NItems; j >= index(e)+1; j-- ) { bucket[j] = bucket[j-1]; // Make room for new entry } bucket[ index(e) ] = (k, v); NItems++; } }
- Delete algorithm (pseudo code):
Delete(Key k) { e = BinarySearch(k); // Binary search works on sorted arrays !!! if ( e == null ) { return; // Not found... nothing to delete } else { for ( j = index(e); j < NItems-1; j++ ) { bucket[j] = bucket[j+1]; // Copy array down... } NItems--; } }
- Example: search for the key 7 in an ordered map:
- Compare 7 with the
middle element:
- 8 < 7, search in lower half:
- 3 > 7, search in upper half:
- 5 > 7, search in upper half:
- Found... return corresponding value...
- Compare 7 with the
middle element:
- The modified binary search algorithm:
- This modified binary search algorithm
will return an index i
such that:
k <= Entry[i].key
Modified Binary Search:
public static int BinSearch(MyEntry[] Bucket, int N, int k) { int low, high, mid; low = 0; // low end high = N-1; // high end mid = (high + low)/2; /* ==================================================== This is the ordinary binary search algorithm ==================================================== */ while ( low <= high ) { mid = (high + low)/2; // Middle element if ( Bucket[mid].key == k ) { return( mid ); // found } if ( k < Bucket[mid].key ) { high = mid - 1; // Search lower half } else { low = mid + 1; // Search upper half } } /* ============================================================== When we arrive here, we have: high < low In any case, we are NEAR the key k =============================================================== */ if ( high >= 0 && k <= Bucket[high].key ) return high; if ( low < N && k <= Bucket[low].key ) return low; return N; // Exceeded ! }
- This modified binary search algorithm
will return an index i
such that:
- Example Program:
(Demo above code)
- Prog file: click here
How to run the program:
- Right click on link(s) and
save in a scratch directory
- To compile: javac BinSearch1.java
- To run: java BinSearch1
Sample output:
0:(4,a) 1:(7,b) 2:(9,c) 3:(14,d) 4:(18,e) 5:(23,f) 6:(29,g) 7:(39,g) BinSearch(2) = 0 BinSearch(4) = 0 BinSearch(5) = 1 BinSearch(7) = 1 BinSearch(8) = 2 BinSearch(9) = 2 BinSearch(13) = 3 BinSearch(14) = 3 BinSearch(16) = 4 BinSearch(18) = 4 BinSearch(20) = 5 BinSearch(23) = 5 BinSearch(26) = 6 BinSearch(29) = 6 BinSearch(33) = 7 BinSearch(39) = 7 BinSearch(93) = 8
- The Ordered Map
can be easily implemented
using the
modified binary search algorithm
How to do it:
- The modified binary search
returns an index that is
near the key you are
searching for
- All you need to do now is to traverse a few elements before or after that spot to find the element you need.
- The modified binary search
returns an index that is
near the key you are
searching for
- I will therefore not waste time
teaching you how to implement an
Ordered Map
as an Ordered Array
We will move on to something more interesting....