Data Structures in C++, Hash Functions Hello Chegg expert, I am a computer scien

Question

Data Structures in C++, Hash Functions

Hello Chegg expert, I am a computer science student and I'm currently learning about hash functions in C++.

I am currently struggling to implement the code in this assignment.

I must build some hash functions and test them to basically see which one is the more efficient one.

There are some of the information you would need to do the assignment so I'm attaching the links in the bottom.

This assignment is for my class server so you will probably need the links for some of the information below.

1. Text file containing 100000 English words: http://staffwww.fullcoll.edu/aclifton/files/words.txt

- You can just pretend that I downloaded the text file to my server and copied them to my code using ifstream dictionary("word.txt");

2. This is the link for the full distribution if you would need them: https://sourceforge.net/projects/boost/files/boost/1.63.0/

I know that this is definitely not an easy assignment which may take some time, but I really would like to get this one down before I end the semester.

I will really appreciate your help and effort if you could code them successfully.

Thank you in advance!

In this assignment you are going to test various hash functions to see how good they are, in terms of how many collisions they have. Your input will be strings, in fact, all the strings that are defined in the systems dictionary. This is located in /usr/share/dict/words you can download a copy to your local computer for testing here. (If you try to download it your browser may say that its a binary file, but it is in fact a text file, with one word per line.) Note that if you try to open the system copy of the dictionary in your code on the server, you will have to open it for reading only, otherwise opening the file will fail. This file contains just under 100,ooo English words, which were going to use to test the uniformity of various hash functions. Your hash functions will hash strings into 16-bit (not 32-bit) int s. This is important, because were going to keep a table of the number of collisions for each hash value. With 16-bit ints there are only 65,536 possible hash values, so this table will easily fit in memory. If we used 32-bit ints then there would be 4,294,967,296 possble hashes, a more troublesome amount. For C++, you can get a 16-bit unsigned int type by doing Hinclude cstdint uint16_t x; x has exactly 16 bits and is signed

Explanation / Answer

unsigned int RSHash(const std::string& str)
{
unsigned int b = 234561;
unsigned int a = 5500;
unsigned int hash = 0;

for(std::size_t i = 0; i < str.length(); i++)
{
hash = hash * a + str[i];
a = a * b;
}
return (hash & 0x7FFFFFFF);
}
unsigned int JSHash(const std::string& str)
{
unsigned int hash = 1315423911;

for(std::size_t i = 0; i < str.length(); i++)
{
hash ^= ((hash << 5) + str[i] + (hash >> 2));
}

return (hash & 0x7FFFFFFF);
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.