CODEWITHSUNDEEP
javahash
Giiovanna
Giiovanna

Reputation: 442

Use Hash Table to create a dictionary of words

I am studying, by my self, about Hash Tables using the following course: http://algs4.cs.princeton.edu/34hash/

At the exercises part, I've found the followig:

Password checker. Write a program that reads in a string from the command line and a dictionary of words from standard input, and checks whether it is a "good" password. Here, assume "good" means that it (i) is at least 8 characters long, (ii) is not a word in the dictionary, (iii) is not a word in the dictionary followed by a digit 0-9 (e.g., hello5), (iv) is not two words separated by a digit (e.g., hello2world)

I think I am confused about how to use a Hash Table (HashMap). Suppose a easier exercise: We need only to check if the word is at the dictionary and I need to do this using a Hash Table. My guess is that I should add all the words in the dictionary using the word as key and, if I want to check if a given word is at the dictionary, I use the "get" method. If found, the word is not a good password. But:

1) What should be the value that I have to put associated with a given key?

2) What if two words hash to the same place? I know the collision part is solved using Linear Probing or Separate Chaining, so when I use get, it will be handled in the data structure?

I don't want you to write any code, I am just trying to understand how this works.

Thanks in advance!

@Edit: Another idea that I had is only make use of the hashCode. Suppose that I have an array of Strings with all the words of the dictionary. Then, if they have the same hash code, I must compare then (since hash must be consistent with equals). If I understood well, the value doesn't matter, in this case, I just should check if the word is at the dictionary. So I just should check if get returned me something.

Upvotes: 0

Views: 2402

Answers (1)

AdamSkywalker
AdamSkywalker

Reputation: 11609

1) What should be the value that I have to put associated with a given key?

If you look at java HashSet implementation, you will see that internally it uses a HashMap, items are added to map as keys, and value is a dummy object, shared by all entries. Your dictionary keys structure is more a HashSet than a HashMap, if you have no specific value (like popularity for example) to associate with a key.

2) What if two words hash to the same place? I know the collision part is solved using Linear Probing or Separate Chaining, so when I use get, it will be handled in the data structure?

Java HashMap implementation uses separate chaining, all items with same hash code are put in a linked list structure. You do not have to worry about collision resolving, when you use HashMap (unless your goal is to prevent hash attacks).

Upvotes: 1

Related Questions