2

I am working on the hashmap implementation for the PSET5 Speller problem and seem to keep encountering problems. I have already created a couple of other solutions to the problem (a-z style hashmap minus the hash, 2D array) but am having issues with the actual hashing process.

I tried to use a hash function that I found (shift-add-XOR hash) but the problem that I keep realizing is that the dictionary is sorted but any hash that I use then makes the dictionary...not sorted. Seems kind of pointless to do that as then I have to use bubble sort (which I tried already) and it takes forever to run in the load section of my code. After realizing this, I just got my code working with a linear search though it is very very slow IMO...runs in 39 seconds on dracula.txt. I can not imagine this being even close to a good time since my array implementation did all 4 sections of dictionary.c in 0.20s on dracula.txt.

So, the question... Where is my time best spent going forward trying to get the hashmap implementation down to a reasonable speed? I would like to binary search once the array is sorted (or hopefully leave it sorted) but then I need a more focused hash function. Right now even trying to make my own hash function (that would be bad but functional) seems like it may have more problems than I am anticipating. I pasted my code below so that you can see where I am stumbling at. The code does work properly, just slow. Any help is appreciated!

https://gist.github.com/anonymous/be20f7ccb77e911ec40a1e4d7aa24109

3

This is an ineffective use of a hash function. In essence, your load function simply inserts each word sequentially into an array, along with a hash number, and the check function is doing a linear search. It might as well be implemented without the hashing, at least it would be a little faster. Bottom line is this is incredibly inefficient.

The purpose of a hash function is to assign a number to each word that can be used to quickly find it by searching a subgroup of the dictionary, not the whole dictionary. Think about it this way. A linear search breaks the dictionary into one single group of 14k elements. It will take a long time to search just one group. Now, if you were to divide the dictionary up into 26 groups based on the first letter, you would only have to search one group. Since the average size of a group is 14k/26 (give or take), the average speed is 26 times faster. Now, if you could divide the dictionary into, say, 1000 different groups, using some hash function, then the average group size would be 14k/1k or 14 words per group. This would run a lot faster because you could then use the hash function to go straight to that group and quickly search those 14 or so words. Even if the group is many times that size, it's still going to be a lot faster than a linear search of the dictionary!

The technique for using a hash function is to create a root array that serves as the starting point of all the buckets. Each bucket is a linked list. The hash value for a word tells which bucket to use. In other words, the hash value returned is the array index to use. For example, a word has a hash value of 538. The word should be added to the linked list that starts at array[538]. The hash value does not need to be stored in the node. Since the idea is to keep the length of the linked list to a minimum, having a sorted list will have little impact on the performance of check, but sorting of the list will impact load, probably more than it benefits. So, it only remains to decide how to add a node to the list. In practice, it is more efficient to add it to the beginning of the list than anywhere else. I'll let you contemplate why. ;-)

A couple of other issues I saw. First, your hash function is not bounded. It can produce very large hash numbers. If you wish to implement the concepts I've described, you will need to limit the size of the hash so that the number produced is within the bounds of the dictionary table range. This would be easily done with a modulo operation.

return h % HASH_MAP_BIN_SIZE;

This guarantees that the hash number is in the desired range.

Next, you have HASH_MAP_BIN_SIZE defined, but then have used 143091 in the code. You should use HASH_MAP_BIN_SIZE and not hard code the number in the code. This has the added benefit of playing with the size of the hash by changing the value in one place at the top of the file to see what impact it has on performance.

As for hashing to exactly 143091, the number of words in the dictionary, you'll find it difficult to get a perfect hash. (google "perfect hash" and you can get a fuller explanation.) Simply put, once the hash range gets to a certain point, diminishing returns sets in - increasing the range uses up more and more resources while producing less and less benefit in speed. I'll leave it to you to play with the number of bins to see the effect.

That's a pretty long overview of what's happening in your code. Hope it helps.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

| improve this answer | |
  • The problem that I still encounter is more about what is optimal for a hashmap.In the case of this pset, is optimal for searching thru 143,091 words in the dictionary going to be having every one of them in an array of nodes uniquely?I have done a hashmap implementation with the 26 alphabetic characters as bins (because no words can start with apostrophe) and this worked somewhat well. The problem was still that once I got to the correct "bin", I was still linear searching.Then I wanted to try 143,091 bins sorted numerically so I could binary search. Seems like an array or trie is just better. – Zach B Aug 24 '16 at 16:50
  • 1
    With 143091 hash bins, you're trying to get a perfect hash where there is exactly one word in each bucket. The problem with that is that there will be words with the same hash number and there will be buckets with no words. To get down to one word per bucket (there would still be empty buckets), you would need to have several times more buckets than words. The reality is that it really isn't worth it. In most cases, performance will be sufficient once the average number of words in each bucket is small. (continues...) – Cliff B Aug 24 '16 at 17:06
  • 1
    (...cont'd.) It's up to you to decide wha's sufficient performance, but the return on investment in resources and effort shrinks as the number of buckets increases. For example, just going from 1 linked list to 26 will dramatically increase performance, while going from 1000 buckets to 5000 may only produce incremental performance improvement, and going from 5k to 10k or from 14k to 56k may not see much improvement at all. It's really about what is considered sufficient vs. resources needed to attain that level. However, anything that requires a linear search of the whole dictinoary is bad. – Cliff B Aug 24 '16 at 17:10
2

As usual, Cliff B has explained things very well in his answer. I'd just like to add a more succinct explanation. Your problem is that you want to keep the dictionary sorted alphabetically and also use a hash table. But if you use a hash table, you can safely let go of the alphabetization.

A hash map is a different way of sorting the words -- one that is less intuitive for a human to understand, but much more efficient for a computer to use. Trying to use both of them at once is fundamentally inconsistent, and this is the root cause of your troubles.

EDIT: I stand corrected (see comment from @MARS below). I think "Fundamentally inconsistent" is too strong of a way to word what I was trying to say. "At cross purposes" might be better. You can certainly mix and match sorting and hashing -- e.g., you can have 26 hash tables in an array indexed from 0 to 25, one table for each letter of the alphabet, and search in the appropriate table based on the initial letter. And you can have a sorted binary tree.

My point was more that if you're using a linked list, it doesn't matter what order the items are in since you can't index into it, you will need a linear search anyway -- in which case, the goal is to have your dictionary items spread out evenly throughout your hash buckets, so that you don't have one really long linked list, or too many really short linked lists.

I am certainly not an authority on these things -- I haven't even finished CS50 yet myself! :)

| improve this answer | |
  • 1
    I do not want you to see it as a criticism, but so that users do not have an idea wrong a hash table is fully compatible with a list sorted, I think that's the idea that have in mind Zach B "that the dictionary is sorted" though execute it incorrectly – MARS Aug 24 '16 at 21:11
  • @MARS: No offense taken! I certainly don't feel harshly criticized, and I also feel like I could have expressed my thoughts more clearly. I edited my comment above to reflect that. – hotwebmatter Aug 24 '16 at 22:56
  • 2
    "..., so that you don't have one really long linked list, or too many really short linked lists." Actually, too many short lists is not a problem, it's the goal. Ideally, all the lists should be short, so that any search algorithm of a particular list runs in roughly the same time, making a linear search roughly as efficient as any other. But you are absolutely right that long lists are bad because the longer the lists, the more it will impact run time and the significance of the choice of search type, particularly since anything other than linear requires a lot more design. – Cliff B Aug 25 '16 at 5:30
  • Right -- a "perfect hash" with one item in each bucket would be much faster to search, but picking the right hash function to spread things out evenly among buckets is a bit of a black art, and you can't solve it just by adding more buckets because there are diminishing returns. – hotwebmatter Aug 25 '16 at 11:17
  • Also, even though it's possible to gain some search time by sorting things, that is offset by the time it takes to sort them in the first place. A well-tuned hash function will only touch each data item once as it hashes it and stuffs it in the corresponding bucket, and the linear search won't incur much time penalty because there will only be a few items per bucket. – hotwebmatter Aug 25 '16 at 11:36
1

From where I see it, if you want to have an array for all the words, and use a linked list, so that you can use a binary search, you have 2 options:

  1. Make an array of strings, and store the words themselves, in alphabetical order. Then use strcmp() for your binary search algorithm to find in which half you have to search next. Keep in mind that you might not be able to store all the words in the stack memory, so you should use the heap instead.
  2. Keep hashing the words with your current hash function, and then sort() the hashed unsigned long values. Then you can use binary search. This will probably require less memory, but with a hit in performance. I'm not sure, I'll leave the testing to you, and hope you inform me with a comment when you find out!

If you have more questions, leave a comment bellow! Till then, Happy Coding! :)

| improve this answer | |

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .