The java program hashCodeString.java in the collection of Course Files , illustr
ID: 3581793 • Letter: T
Question
The java program hashCodeString.java in the collection of Course Files, illustrates the Java hashCode()method applied to strings. It shows how a small change in a string object can produce a significant change in the object’s hash code.
Since Java’s hashCode() method produces (only) a 32-bit integer, it should be possible to find two different words that have the same hash code. Try to do it this way:
Create a map in which the Key Set consists of Integers, and the Value Set consists of sets of String objects. You can use
Map<Integer, HashSet<String>> or
Map<Integer, TreeSet<String>>
Populate the map by reading a very large file of words. When you read a word, compute its hash code, h, and then add the word to the set whose key is h. Finally, iterate through all the keys and print the sets whose size is greater than one.
Of course you should test your program on a small file of words before you try it on a very large file.
This is actually a very easy program to write. The problem is finding a very large file of words and having the time and space resources to run your program.
Hand-in our source code, a link to the file of words that you used, and tell us which words you found that have the same hash code. (Please don’t try to submit the file of words! Just tell us where to find it)
Explanation / Answer
public class hashCodeString {
public static void main(String[] args) {
String str1 = "Hii we are chegg team?";
int hashcode1 = 0;
int hashcode2 = 0;
for(int i=0;i<str1.length();i++) {
hashcode1 = 31*hashcode1 + str1.charAt(i);
hashcode2 = (hashcode2 << 5) - hashcode2 + str1.charAt(i);
}
System.out.println("Hashcode1 : " + hashcode1);
System.out.println("Hashcode2 : " + hashcode2);
String str2 = unhash(hashcode1);
System.out.println("Unhashed String From Hashcode : " + str2);
int hashcode3 = 0;
int hashcode4 = 0;
for(int i=0;i<str2.length();i++) {
hashcode3 = 31*hashcode3 + str2.charAt(i);
hashcode4 = (hashcode4 << 5) - hashcode4 + str2.charAt(i);
}
System.out.println("Hashcode3 : " + hashcode3);
System.out.println("Hashcode4 : " + hashcode4);
}
public static String unhash(int target) {
StringBuilder answer = new StringBuilder();
if (target < 0) {
answer.append("u0915u0009u001eu000cu0002");
if (target == Integer.MIN_VALUE)
return answer.toString();
// Find target without sign bit set
target = target & Integer.MAX_VALUE;
}
unhash0(answer, target);
return answer.toString();
}
private static void unhash0(StringBuilder partial, int target) {
int div = target / 31;
int rem = target % 31;
if (div <= Character.MAX_VALUE) {
if (div != 0)
partial.append((char)div);
partial.append((char)rem);
} else {
unhash0(partial, div);
partial.append((char)rem);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.