1Implementing a queue in an arrayHashingWe show a neat idea that allows a queue to be storedin an array but takes constant time for both addingand removing an element. We then discuss hashing.Implementing a queue in an arrayA first attempt at implementing a queue in an arrayusually uses the following idea:At any point, the queue contains k elements. Theelements are stored in a[0], a[1], .. a[k-1] in the orderin which they were placed in the queue, so a[0] is atthe front.In this situation, adding an element to the queue takesconstant time: place it in a[k] and increase k. Butdeleting an element takes O(k) time. The items ina[1..k-1] have to be moved down to a[0..k-2] and khas to be decreased.Instead let’s use two variables, f and b, to mark thefront and the back of the queue:Adding an element is done as before: a[b]= element;b= b+1;Now, removing an element takes O(1) time: f= f+1;But where do we put the next element when the arraylooks like this?The answer is: in a[0] --we allow wraparound!.Thus, we can describe the general picture, theinvariant for this class, using two pictures. The queueis defined by:front back a0 k a.length front back a0 f b a.length front backa0 f b (= a.length)orWe also maintain:(1) 0 <= f < a.length and 0 < b < a.length.(2) the queue elements are in a[f], a[(f+1)%a.length], a[(f+2)%a.length], …, a[(b-1)%a.length](3) the queue is empty when b = f(4) the queue is full when (b+1)%a.length = f.To understand point (4), suppose the array has onlyone unoccupied element:If we try adding another element usinga[b]= element; b= b+1;we end up with b=f. But b=f is supposed to describean empty queue, not a full queue. So we have to letthe above picture represent a full queue. At least onearray element will always be empty.An alternative is to introduce a fresh variable, size,that will contain the number of elements in the queue.A good exercise is to write a class QueueArray,similar to class QueueVector but using an array toimplement the queue, as just described. If you do this,be sure you give comments on the fields of the classthat describe how the queue is implemented in thearray!!!! Points (0)-(4) above should be given ascomments. front back a0 f b a.length back front a0 b f a.length back front a0 b f a.length2HashingHashing is a technique for maintaining a set ofelements in an array. You should also read Weiss,chapter 20, which goes into more detail (but is harderto read).A set is just a collection of distinct (different)elements on which the following operations can beperformed:• Make the set empty• Add an element to the set• Remove an element from the set• Get the size of the set (number of elements in it)• Tell whether a value is in the set• Tell whether the set is empty.Obvious first implementation: Keep the elements inan array b. The elements are in b[0..n-1], wherevariable n contains the size of the array. No duplicatesare allowed.Problems: Adding an item take time O(n) --itshouldn’t be inserted if it is already in the set, sob[0..n-1] has first to be searched for it. Removing anitem also takes time O(n) in the worst case. We wouldlike an implementation in which the expected time forthese operations is constant: O(1).Solution: Use hashing. We illustrate hashingassuming that the elements of the set are Strings.Basic idea: Rather than keep the Strings in b[0..n-1],we allow them to be anywhere in the b. We use anarray whose elements are of the following nestedclass type:// An instance is an entry in array bprivate static class HashEntry {public String element; // the elementpublic boolean isInSet; // = “element is in set”// Constructor: an entry that is in the set iff bpublic HashEntry( String e, boolean b ) { element = e; isInSet= b;}}Each element of our array b is either null or the nameof a HashEntry, and that entry indicates whether it isin the set or not. So, to remove an element of the set,just set its isInSet field to false.Hashing with linear probing. Here’s the basic idea.Suppose we want to insert the String “bc” into the set.We compute an index k of the array, using what’scalled a hash function,int k= hashCode(“bc”);and try to store the element at position b[k]. If thatentry is already filled with some other element, we tryto store it in b[(k+1)%b.length] --note that we usewraparound, just as in implementing a queue in anarray. If that position is filled, we keep tryingsuccessive elements in the same way.Each test of an array element to see whether it is theString is called a probe.The hash function just picks some index, dependingon its argument. We’ll show a hash function later.Checking to see whether a String “xxx” is in the set issimilar; compute k= hashCode(“xxx”) and look insuccessive elements of b[k..] until a null element isreached or until “xxx” is found. If it is found, it is inthe set iff the position in which it is found has itsisInSet field true.You might think that this is a weird way to implementthe set, that it couldn’t possibly work. But it does,provided the set doesn’t fill up too much, andprovided we later make some adjustments.Here’s a basic fact:Suppose String s is in the set and hashCode(s) = k.Let b[j] be the first nonnull element after b[k] (weinclude wraparound here). Then s is one of theelements b[k], b[k+1], …, b[j-1] (withwraparound).Then, because of the basic fact, we can write methodadd as follows, assuming that array b is never full: b0 k b.lengthtry to insert element at b[k], b[k+1], etc...3Hashing// Add s to this setpublic void add(String s) {int k= hashCode(s);while (b[k] != null && !b[k].element.equals(s)){ k= (k+1)%b.length(); }if (b[k] != null && b.isInSet)return;// s is not in the set; store it in b[k].b[k]= new HashEntry(s, true);size= size+1;}Removing an element is just as easy. Note thatremoving a value from the set leaves it in the array.// Remove s from this set (if it is in it)public void remove(String s) {int k= hashCode(s);while (b[k] != null && !b[k].element.equals(s)){ k= (k+1)%b.length(); }if (b[k] == null || !b[k].isInSet) return;// s is in the set; remove it.b[k].isInSet= false;size= size-1;}Hashing functionsWe need a function that
View Full Document
Unlocking...