Use Hash Table to create a dictionary of words

Question

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.

What to add as a value is a good question. If you only need to check for the existence of a word, simply using a HashSet will do the trick. Otherwise, you may want to do some stat tracking (how many times a user tried to use a particular word), but for security reasons this probably isn't a good idea. — Alvin Thompson
– Alvin Thompson, Commented Jun 14, 2015 at 11:21

AdamSkywalker · Accepted Answer · 2015-06-14 11:22:02Z

1

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).

edited Jun 14, 2015 at 11:22

answered Jun 14, 2015 at 11:17

AdamSkywalker

11.6k3 gold badges41 silver badges78 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Giiovanna Over a year ago

Thank you for your reply. I didn't know about HashSet, and now I see it is exactly what I need.

Collectives™ on Stack Overflow

Use Hash Table to create a dictionary of words

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related