CS 245 Lab 7 – Hashing
First, if you have checkpoints left over from last lab, get them inspected during the first 15 minutes of this lab. No credit will be awarded past these 15 minutes.
Work in pairs, where possible. Prefer working with someone that you did not work with last lab. The exchange of new ideas and perspectives is not an opportunity you want to rob yourself of.
Synopsis
In this lab, you will explore the beauty of hashmaps, a data structure that expands the notion of arrays. Instead of indexing by ints, you can index by pretty much anything. Hashmaps let you create arbitrary associations from a key to a value, making the problem of lookup a cinch. In particular, you will use a hashmap to track how often a color appears in an image and visualize the color frequencies.
Checkpoint 1
Person A types.
Write a static method getColorHistogram. It returns a HashMap keyed on Color and whose value is some sort of counter. For the counter, you may create your own class or use Integer. (Each has its advantages that you may reason about.)
Your method accepts a File parameter for an image. Walk through all the pixels and use the hashmap to track how many times each color appears. The HashMap documentation describes what operations will help you accomplish this task.
Aside
One could use an array of ints for this task. Should we? Since colors are composed of three values in [0, 255], we’d need a three-dimensional array. That array would have 256 x 256 x 256 = 16777216 elements. In Java, an int is 4 bytes. The array would be 64 megabytes in size. This may or may not be a cost we can afford to pay in our application. Many of these elements might not ever be accessed. For sparse data, hashmaps trump arrays.
Checkpoint 2
Person B types.
Create a JFrame with a JSlider and a custom JPanel. Use the same structure from your stick figure lab or lecture code. Make the frame 256 x 256. Create a histogram for an image by calling your method described above.
In your JPanel‘s paintComponent method, draw a graph of your histogram. Since your histogram is high-dimensional [mapping (r, g, b) to int], this isn’t necessarily a straightforward task. We can eliminate a dimension by plotting only a plane of the histogram at a time. For example, let’s say we only care about the colors where blue is 103. We can use the red as our X coordinate and green as the Y coordinate:
for each color
if color.blue is 103
plot a dot at (color.red, color.green)
This doesn’t yet incorporate the frequency of the color. If the frequency for a color is high, let’s draw a bigger dot. Let’s also draw the dot using the color:
for each (color, frequency)
if color.blue is 103
radius = some function of frequency
set drawing color to color
plot a dot with given radius at (color.red, color.green)
Iterating through a hashmap can be done several ways. The most straightforward route is to get a list of all the keys with the keySet method. Iterate through that, and use each color key and the get method to access the color’s frequency. However, there’s a faster approach that eliminates the need to make a separate lookup:
for (Entry<KeyType, ValueType> entry : map.entrySet()) {
KeyType key = entry.getKey();
ValueType value = entry.getValue();
// do something with key and value
}
You’ll want to use your type and variable names.
Now, use the slider to change the blue value dynamically. In a ChangeListener attached to the slider, cause the panel to repaint, using the new value for blue.
Try your tool out on various images. What do you think?