CSC 207 CSC 207.01 & .02- Algorithms and Object-Oriented Design Spring 2022 Home Schedule Class Slides Labs Assignments Resources Lab: Hash Map Overview The goal of this lab is to implement linear probing, which is used as a technique for resolving collisions when accessing or inserting elements in a hash map. Preparation There is no starter code for this lab. You may work in Eclipse or write your code using a text editor such as Emacs. You may want to use the Pair class given below, or you may write your own. Before you start, make sure you read over the whole lab, particularly items 2 and 3!! Counting Letters 1. Write a program in a file called CountLetters.java that reports the occurrence of each of the 26 letters used in English and found in the /usr/share/dict/words file. The program should display one letter and its count on a separate line, e.g., a: 205807. Note that letters are not case-sensitive. In addition, the program should ignore any character that is not an English letter. Remember that UNICODE (which Java uses) recognizes thousands of characters as a letter in some language (including fictional languages such as Elvish and Klingon). You will not be able to rely upon the Java library function isAlphabetic. Use an array to maintain these counts. How can you map English letters to the indices of this array? Can the above program be applied to files with arbitrary character sets used in other languages, given the fixed array size that you used in the above exercise? Counting Characters Because of the limited array size, the above program does not work for counting the occurrence of arbitrary characters. A technique to address this problem is to determine the array index (hash code) through computing the mod of the character value by the length of the array. That way, every element has a proper index in the array. However, this technique needs to account for collisions that arise from inserting characters that map to the same index. 2. Write a class called CountChars.java that maps arbitrary characters to their counts. Your class should support the following methods: CountChars ( ): creates a new empty array. Each array entry stores a key-value pair represented by the Pair class. (Use the Pair class below or write your own. Note that your Pair class does not need to be generic.) Implement getter and setter methods inside your Pair class. The initial capacity of the hash array is 26. Its size will be 0 (containing no Pairs). int find (char ch): returns the index of an entry in the array. For the key ch, the entry contains either a Pair or null. This method calculates the desired index for the key ch and starts from that index to scan the array until it it finds an entry (using linear probing) that already contains the Pair or finds an open spot for placing a Pair. Integer get (char ch): returns a value for key ch if it exists in the map. This method returns null if there is not a mapping for ch yet. Integer put (char ch, int v): associates key ch with its value v in the map. It updates (overrides) buthe value for the prior entry with ch, if it exists, and returns the old v. It returns null if there is not a mapping for ch. The put method may need to call rehash() if the size of the hash array becomes greater than the capacity of the array. Note: put() will usually be called after get() has returned the current value, if any, for the number of times the character has been seen so far. So, you will increment the value inside the application/driver/tester program and store the new value using put(). rehash( ): doubles the hash array length if there is not an unused entry in the array for placing a new key-value Pair. getArray( ): returns the array that contains the key-value Pairs. To resolve collisions, use the linear probing method. Do not use java.util.Map in your implementations. 3. Create a driver program to read in a file and count the number of occurances of each character. This program will do more than our usual driver programs do. It should: Read a line from a file Process the line one character at a time Check if the hash array already has an entry for that charater (using the get method) Put the character and the (updated) count into the hash array It might need to call rehash as part of putting in a character for the first time Test your program by displaying characters and their counts for /usr/share/dict/words. You MAY want to try it with a smaller file of your own creation first so that you know how many instances should be found for each character. The Pair Class
public class Pair {
private char key; private int value;
public Pair(char key, int value) {
this.key = key; this.value = value;
}
public char getKey() {
return key;
}
public int getValue() {
return value;
}
public void setKey(char key) {
this.key = key;
}
public void setValue(int value) {
this.value = value;
} } Lab Writeup There is no lab submission for this lab. However, keep in mind that portions of this code may appear in the final exam. Acknowledgements This lab is based on a material made by Peter-Michael Osera. This derivative work is used and licensed under a Creative Commons Attribution-NonCommercialShareAlike 4.0 International license. This course is adapted from prior courses taught by Shervin Hajiamini, John Stone, Sam Rebelsky, Anya Vostinar, and Jerod Weinman and used by permission. Other authors' contributions are noted when used or adapted.
