11 Sets

Version 6.3¹

Handouts:

A: BinarySearchTree.hs, TreeSet.hs, TreeSetTest.hs

B: None

Part A: Sets, Lists, and Binary Search Trees

The Concept of Sets

• A set is a collection with no duplicates and in which there is no order defined.
  • No order: {A, B, C} is the same set as {C, B, A}.
  • No duplicates: {A, A, B, C} either is not a set, or is the same set as {A, B, C}.
• Note: a collection which is like a set, unordered, but allows duplicates, is called a bag.

11.1 The Set Interface

• Figure 11-4, p. 286 (preliminary version). The important methods are:
  • S.add(E)
  • S.contains(E) ⇒ boolean
  • S.remove(E)
  • S.size() ⇒ int
• Strangely, the Set interface does not include the familiar set operations such as union, intersection, difference, subset of.

The Game of Anagrams

• Figure 11-1, p. 284.
• In the program implementing this game, there are a few data collections:
  • The "bag" of letter tiles is actually a bag data structure.
  • The pool of letter tiles on the table is also a bag.
  • The dictionary, for determining the validity of words, is a set.
• The Unix dictionary is found typically at /usr/share/dict/words.
  • Do we have it?

  • How big is it?

    $ wc /usr/share/dict/words
    

  • What does it look like?

    $ less /usr/share/dict/words
    

  • How long does cat /usr/share/dict/words take?
• Efficiency considerations, pp. 289-290:
  • He implies that there are at least 3 set-implementing classes: HashTable, OrderedList, and BinarySearchTree
  • Only one of these is acceptable if dict is large and alphabetized. Which one is this?
  • How bad is it otherwise?
  • Why do we study the others, then?
    • They are still useful if N is small or randomly ordered.
    • BinarySearchTree is the foundation (superclass) of some very efficient search structures, the balanced search trees, including Red Black Trees, covered in chapter 14.
    • The hash table is no good if we wish to traverse the set in alphabetical order. But a set has no order. :-)

11.2 Ordered Lists as Sets

• Example: [1, 3, 7, 21, 24, 27, 32] is an ordered list.
• It's implied that it is a linked ordered list; but why not an array list?

• How do these operations work?

  S = [1, 3, 7, 21, 24, 27, 32]
  
  S.contains(7)
  S.contains(23)
  S.add(18)
  S.remove(3)
  S.remove(23)
  S.size()
  

• Which operations are Θ(N)?
  • All of them.
• What if we used an ArrayList instead of a linked list?
  • Then we could use binary search, speeding up the contains method to Θ(log N).
  • Might be good, especially if add and remove are not frequently done.
• Of course an unordered list could also represent a set. When might this be desirable, and when not?
  • Elements of an ordered list must be comparable.
  • Most set operations are faster for ordered than for unordered lists (but still the same order, Θ(N)).
• Page 291: Why should the OrderedList class, which implements the Set interface, not be a subclass of LinkedList, which implements the List interface? Should it, instead, have a LinkedList, then?
• Summary:
  • Easy to implement
  • Θ(N) running times for the contains, add, remove, and size (easily fixed for size). methods.
  • Suitable only for small sets.

11.3 Binary Search Trees

• Definition: a binary search tree is a binary tree, with these further properties:
  • All elements < root are in the left subtree.
  • All elements > root are in the right subtree.²
  • The left and right subtrees are binary search trees.
• Not just a plain binary tree!

• Let S be the following binary tree:

  

  The binary tree S

  • Show that S is a binary search tree.

  • How do these operations work, in the given S (always restarting with the original S)?

    S.contains(7)
    S.contains(23)
    S.add(18)
    S.remove(7)
    S.remove(24)
    S.remove(27)
    S.remove(21)
    

    This could be done two ways: we can replace 21 with either (a) its inorder predecessor, 7, or (b) its inorder successor, 24. Any other element would violate the order property of the binary search tree. The predecessor is the rightmost descendant in the left subtree. The successor is the leftmost descendant in the right subtree.
• Implementation (see Fig. 11-16, p. 297):
  • Note that a binary search tree, in this implementation, has a, not is a, binary tree. Why?
    • If it were a binary tree, you could mutate it arbitrarily, making it not be a binary search tree.
    • Is this still a problem if we operate functionally? Why or why not?
• Good news:
  • If the binary search tree is reasonably well balanced (a perfect binary tree or something close to that), so that about 1/2 the nodes are in each subtree, then the contains, add, remove methods are all Θ(log N). The size method is still Θ(N), but it could easily be made Θ(1). How?
  • If the elements are inserted in random order, then (very probably) the binary search tree will be well balanced.
• Bad news:

  • If the binary search tree is poorly balanced (a linear binary tree or something similar)

    

    A badly unbalanced binary search tree

    then the contains, add, and remove methods all are Θ(N). Essentially, the tree is just a linked list.
  • If the binary search tree is built by inserting elements that are already in ascending or descending order, its shape will be linear.
• Recommendations:
  • Drake, p. 304: "Binary search trees should not be used in the plain form explained here."
  • I add: "Unless we know that it will be well balanced, i.e., we know that the insertions occur in random order, or the set is small, or it is used in a section of code that is not time-critical."

Binary Search Trees: A Functional Implementation

Haskell code:

• BinarySearchTree.hs
  • Introduces the compare method of Ord; similar to Java's Comparable; also allows <, <=, >, >=, max, min
    • By the way, Eq allows == and /= (not equal to)
  • Introduces (?) "don't care" variable _ for matching anything (in general, any variable name beginning with _ plays this role)
• TreeSet.hs
  • Encapsulation and information hiding: exports only the type constructor, not data constructor, of TreeSet, thereby hiding its internal structure.
  • instance declaration instead of automatically derived Show instance further supports information hiding
  • Possible exercises: add true set operations, including intersection, union, difference, subset (i.e., is A a subset of B?), equality (instance for Eq with a definition of ==; sets A and B are equal if each is a subset of the other).
• TreeSetTest.hs
  • An interactive main function for demonstrating the TreeSet
  • Demonstrates how "state" can be carried as the parameter(s) of a recursive function

Part B: Hash Tables, Java Collections Framework

11.4 Hash Tables

• The LetterCollection class (a collection of letters which allows duplicates, i.e., a bag) is based on an array of 26 ints. Since arrays have random access, or "direct access", the operation times are Θ(1).
• If we had to make a set of letters (no duplicate values allowed), we could use an array of 26 boolean elements. However, this only works for small sets. For very large sets, it would be wasteful, or even impossible, to allocate an array that's big enough — it would have to have an element for every possible value of the set.
  • And if a bag (duplicates allowed), then use an array of ints.
• Hashing is a method of using "direct addressing" (like arrays) that scales up well to sets with very large numbers of possible elements. (Of course, for the actual elements, we cannot get away from having to allocate some memory to store them!)
• A hash function maps an integer value to an array index. If we had a set of integers, we would try to store each element at the index that it's mapped to by the hash function.
• For sets of non-integers, using a hash function is still possible if we have a way of converting the elements to an integer value. Many of the Java built-in classes have a hashCode() method that does this.
  • In fact, strictly speaking, every Java class does, because the method is defined for the Object class and inherited.
  • But for this to work well, the hashcode has to be compatible with equals. That is, if a.equals(b), then we should have a.hashCode() == b.hashCode(). (Of course the converse is not true: two elements can have the same hash code but be different.)
  • The standard Java hash table classes use the hashCode and equals methods, which have to work compatibly. So if you are going to have a hash table of your custom-made class elements, make sure to override the hashCode and equals methods appropriately.

Collisions

• Ideally, the hash code and hash function assign each element of the set to a different array index. But in reality, some elements are assigned to the same "slot". These are called "collisions."

• Two principal methods of dealing with (resolving) collisions:

  • Chaining: each slot in the array is really a linked list of elements, so it can hold many elements.
    • In fact, it could be a binary tree, array list, or any type of storage structure.
    • Drake points out that chaining takes up extra space. Is that much of a problem? ....
  • Open addressing: when an element being inserted discovers that "its" slot is already occupied (collision), it looks for another, unoccupied slot in the array.
  • We will consider two forms of open addressing: "linear probing" and "double hashing."

Linear Probing

Suppose we want to insert k, and the hash function h gives h(k) = i. If slot i is unoccupied, we store k right there. Otherwise, we try slots i + 1, i + 2, etc., stop when we find an unoccupied slot, and store k there. If we reach the end of the array we wrap around to the beginning. If we come back to our starting point, the array is full.

We can deal with a full array³ by rehashing: "stretching" the array, as we did for ArrayList, and applying the hash function again (or a new one) to insert all the elements into the larger array.

The major problem with linear probing is clustering: groups of adjacent slots tend to fill up. This causes long searches just to find if an element is in the set, long searches for insertion (to find an empty slot), and long searches to find an element to be deleted.

A secondary complication of linear probing (in fact of any kind of open addressing) is that it makes deleting an element more complicated. Assuming "null" is the contents of an empty slot, when we delete an element, we cannot simply store "null" in the slot it occupied — because it might not be the last of the elements with the same hash value.

Example:

Assume h(A) = h(B) = h(C) = 3. Insert A, B, C:

If we now remove B by storing null into slot 4, what happens if we want to find C? ....

The solution is to store a special "deleted" value in the slot where items have been deleted, which is different from null and also different from every possible element value. Then when we are searching for C and come to a "deleted" slot, we know we have to keep looking.

Double Hashing

Not the same as rehashing! Avoid clustering by using a second hash function to determine the "increment" for address probing (in linear probing, the increment is always 1).

Let h₁ and h₂ be the two hash functions. If h₁(k) = i and h₂(k) = j, then (as usual) we first try slot i. If it is occupied, then instead of trying slots i + 1, i + 2, ..., we try slots i + j, i + 2j, .... We still wrap around from end to beginning of array if needed.

We need to choose our hash functions carefully to avoid early failures (premature cycles). For example, if there are 100 buckets and h₂(k) = 50, then we will try slots h₁(k), (h₁(k) + 50) % 100, (h₁(k) + 100) % 100 = h₁(k). We are quickly back where we started!

Drake's implementation avoids this problem by (1) making the array size always be a power of two, and (2) making the second hash function always return an odd number (how is that done?).

How would this work with 1024 slots and h₂(k) = 511? .... This looks good, but can we be sure it's always good? .... Relatively prime ....

Rehashing (when we run out of space in the array) works hand in hand with this strategy: we start with array size 1, and then every stretch doubles its size, so the sizes are 1, 2, 4, ... — always powers of two.

• Implementation details: Figures 11-36 ... 11-39, pp. 312-315:

  • Use of a special "deleted" value
  • the two hash functions
  • the contains method
  • insertion (add)
  • rehashing occurs when the "fullness" is 1/2 or greater. "Fullness" is the ratio of "occupied" (including "deleted"?) slots to the array's length.
  • removing an element

My weird perspective: chaining and open addressing are two varieties of the same thing! In both there is a "chain" or sequence of locations in which to search for (or insert, or delete) a given element. With chaining, these are off to the side and occupy additional space, including space for pointers to link the nodes. With open addressing, the sequence is embedded in the array and the pointers are not stored. See the diagrams:

• Chaining:

  

  Image of a hash table with chaining

• Linear probing:

  

  Image of a hash table with linear probing

• Double hashing:

  

  Image of a hash table with double hashing

• Analysis:
  • It is important to minimize collisions (good spread).
  • If the "fullness" is low (say, ≤ 1/2), then the average time for search/insert/delete is Θ(1), because there is only a short chain of elements for each hash value.
  • Rehashing keeps fullness low and gives us a high likelihood that operations are Θ(1).
  • This is wonderful! A search structure which can be searched, inserted, deleted in constant time — independent of the size of the set!
  • On the other hand, poorly designed hash tables with high "fullness" and lots of collisions are possible, and have worst case operation times Θ(N).
• Drake's summary:
  • Hash tables are really good: the best implementations have amortized time Θ(1) for insert, and average time Θ(1) for search and delete operations.
  • In the worst case, Θ(N), but this is less likely to happen for a hash table than for a binary search tree (p. 314) (Why?).
  • Disadvantage of hash tables: deleting is complex. [Yet Θ(1)?] A hash table may not be the fastest choice if there are a lot of deletions.
• Additional comments. Hash tables have a couple of other disadvantages compared to binary search trees:
  • A binary search tree is easily sorted: just traverse it inorder! In a sense it is already sorted.
  • A hash table is not in any sense already sorted, and provides no special support for sorting. We can sort it as we can a list or an array, and the best sorting algorithms take time Θ(N log N).
  • Hash tables support efficient "equals" lookup: e.g., we can efficiently find out whether there is an element in the set equal to 316.
  • Hash tables do not efficiently support inequality-based lookups. E.g., we cannot efficiently find all elements that are less than 316, or all elements between 316 and 341. Such a search would require linear time in a hash table.
  • The search algorithm for binary search trees is easily adapted to handle inequality-based lookups.
  • Summary: binary search trees provide better support than hash tables for sorting data and for queries involving inequalities.
  • For data that do not have to be sorted and where queries only involve equality, hash tables are (at least theoretically) more efficient for large N.
• Additional comments: chaining versus open addressing.
  • Although chaining takes up extra space, it does have the advantage that a search for k having h(k) = i does not involve looking at elements x having h(x) ≠ i.
  • Chaining and double hashing have better performance than linear probing when the "fullness" is high.
  • However, almost any method of resolving collisions will give us a fast hash table if the "fullness" is low, because there will be very few collisions, provided the hash function is well designed.

11.5 The Java Collections Framework Again

• The java.util package provides the interfaces Set and SortedSet, and the classes HashSet and TreeSet, which are similar to the data structures we have studied in this chapter.

• Maps are sets of keys with associated values (also called dictionaries or associative arrays).⁴ For example, a name-age map would enable us to find a person's age, given the person's name. We tell it the key (the name) and ask it to look up the value (age).

• Implementations of maps are similar to implementations of sets, but with the additional work of associating a value with each stored key.

• The java.util package also provides the interfaces Map and SortedMap, and the classes HashMap and TreeMap. (Note: HashSet implements Set; TreeSet implements SortedSet. Similarly, HashMap implements Map, and TreeMap implements SortedMap.)

• Figure 11-42, p. 319, summarizes the running times of data structures covered in this chapter, as well as a few to be covered later.

Footnotes