Outline of Class 37: Associative Arrays

Miscellaneous

• I'd like to remind you once again that Tuesday at 7:30 is the "I was a 70's math junkie" confessional in the forum coffeehouse.
• On Thursday, December 4, at 4:30 in Science 2413, Marc Chamberland will be talking about Dinosaur Hunting and the Mathematical Contest on Modeling.
• An advance warning: I will be gone between the afternoon of Friday, December 12 and the afternoon of Tuesday, December 16 so that I can help Michelle drive back from Maine. Get your questions about the final to me before then!
• I'm still not sure when I'll get grading done this week. I'll do my best to get grade summaries to you early next week.
• If you haven't handed in your printed evaluation of someone else's homework (your assignment four), please do so today.
• On Wednesday, we'll be talking about genetic algorithms (hmm ... who has heard of genetic algorithms?)
• On Friday, I'll do my best to give a course wrapup.
• Next week, we'll have presentations. Presentation guidelines are available. Here's the initial schedule (let me know if you have a good reason to change your slot).
  • Monday: The Mail Groups: 25% Omar (BlitzMail) and Java Beans (NiceMail)
  • Wednesday: The Misc. Groups: Us (Blackboard), Super Bozos (Steganography)
  • Friday: The Game Groups: The Group Formerly Known as U (Fantasy Football), Bob (Crime Spree)
• Project reports are due at the beginning of the final, although I'd appreciate receiving them earlier.
• I was generally happy with your status reports, although I would have preferred to see better preparation (particularly for the group the left only one member in class).

Background: Some Interesting Problems

• Many issues in computing deal with text rather than numbers.
• Here are some examples, from a variety of domains.
• Text Analysis. Identify characteristics of a text (or group of texts). This is sometimes used as a first step in determining authorship.
  • Determine the number of times each word appears in a text.
  • Determine the number of different words used in a text (and, possibly, the ratio of appearances to size of the text).
• Graph Analysis. Given a graph in which each node is labeled with a text string (e.g., a map with labeled cities), determine some property of that graph.
  • Topological sort.
  • Reachability (particularly useful for hypertexts).
  • ...
• Dictionary and Database Support. Given a number of word/definition pairs, provide efficient access to definitions based on words.
• Code Analysis
  • Determine indirect dependencies in included modules.
  • Determine caller/callee structure.
  • Identify potentially recursive functions.

Filter-based Solutions

• Note that some of these problems (particularly the text analysis and dictionary problems) can be solved with a clever set of filters.
• To count the number of different words in a text,
  • split the line at each word boundary (using tr)
  • sort, removing duplicate (sort -u)
  • count the number of words (wc -l)
• To get dictionary entries
  • search for the line that starts with the word (using grep)
  • remove the word, if desired (using sed)

Associative Arrays

• More commonly, these problems are solved by means of a data structure known as the associative array.
• Associative arrays are arrays that are, in effect, indexed by words (or objects) rather than by numbers.
• Using these arrays, we can quickly solve many of the earlier problems.
• To find the number of different words in a document (and the count of each), use something like the following pseudo-Java

  AssociativeArray words = new AssociativeArray();
  while (!stdin.eof()) {
    word = stdin.readString();
    ++words[word];
  }
  System.out.println("There are " + words.size() + "words.");
  for each word in words {
    System.out.println(word + " appears " + words[word] + " times.");
  }
  

• Some questions
  • How do associative arrays differ from normal arrays?
  • How do associative arrays differ from dictionaries?
  • How do associative arrays differ from hash tables?
• I'm not sure what language introduced associative arrays, although one early language that they appeared in is SNOBOL. They have since appeared in Awk and Perl.

Hash Tables in Java

• Because many modern languages provide associative arrays of some form or another, and because they are so useful, Java also provides them (but as hash tables).

• Because hash tables are so common, Java has support for hash tables built in in a number of ways.
• There is a Hashtable class (in java.util).
  • These are expandable hash tables; when you exceed a load factor, they automatically increase in size.
• One of the standard Object methods is hashCode(), which is used to compute the hash value of each object.
  • When you create your own objects, you should override this method.
  • I have no idea what the default is, but it's probably based on the address of the object.
• I've been told by one of the designers of Java that one of the few platform-dependent things in Java was that the initial size of the hash table wasn't specified, which could then effect the order in which the iterator corresponding to that hash table returned stuff.
• Is there anything interesting you note in the description of the Hashtable class?

• Is there anything interesting you note in the description of the Hashtable class?

Problems, Revisited

• Let's see how we might solve some of the previously mentioned problems using associative arrays.
• We've already examined the simple text-analysis problems.
• Bentley gives an interesting version of topological sort.
• Determining calling and inclusion patterns similarly reduces to the implementation of a graph algorithm (cycle detection, this time).

Some Thoughts

• How do associative arrays differ from normal arrays?
  • Obvious: they index by object/string rather than by number.
  • You don't need to predeclare their size.
  • It may be more difficult to get "all the items" in an associative array.
  • ...
• How do associative arrays differ from dictionaries?
  • In name only, in my opinion.
• How do associative arrays differ from hash tables?
  • Arguably, hash tables are a particular implementation of associative arrays, but not the only one.