Refer to this example http://billmill.org/bloomfilter-tutorial/ 1) Using the 2 of the 9 hash functions you have, duplicate the process found in the above example. 2) Next create a file with random inputs and use all 9 hashes this time http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html 3) Choose several spots in the table with 9 hashes and confirm results with your program. False Positive -> (1-e^(-km/n))^k where n is the bit vector size k are the number of hashes m are the number of keys used in the hash to fill the vector. code c++ HashTest.cpp #include //iostrem #include //string #include //vector #include “GeneralHashFunctions.h” int main(int argc, char* argv[]) { const std::string key = “abcdefghijklmnopqrstuvwxyz1234567890”; std::cout << "General Purpose Hash Function Algorithms Test" << std::endl; std::cout << "By Arash Partow - 2002 " << std::endl; std::cout << "Key: " << key << std::endl; std::cout << " 1. RS-Hash Function Value: " << RSHash (key) << std::endl; std::cout << " 2. JS-Hash Function Value: " << JSHash (key) << std::endl; std::cout << " 3. PJW-Hash Function Value: " << PJWHash (key) << std::endl; std::cout << " 4. ELF-Hash Function Value: " << ELFHash (key) << std::endl; std::cout << " 5. BKDR-Hash Function Value: " << BKDRHash(key) << std::endl; std::cout << " 6. SDBM-Hash Function Value: " << SDBMHash(key) << std::endl; std::cout << " 7. DJB-Hash Function Value: " << DJBHash (key) << std::endl; std::cout << " 8. DEK-Hash Function Value: " << DEKHash (key) << std::endl; std::cout << " 9. FNV-Hash Function Value: " << FNVHash (key) << std::endl; std::cout << "10. BP-Hash Function Value: " << BPHash (key) << std::endl; std::cout << "11. AP-Hash Function Value: " << APHash (key) << std::endl; return 1; } GeneralHashFunctions.cpp #include "GeneralHashFunctions.h" unsigned int RSHash(const std::string& str) { unsigned int b = 378551; unsigned int a = 63689; unsigned int hash = 0; for(std::size_t i = 0; i < str.length(); i++) { hash = hash * a + str[i]; a = a * b; } return hash; } /* End Of RS Hash Function */ 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; } /* End Of JS Hash Function */ unsigned int PJWHash(const std::string& str) { unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8); unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4); unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8); unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth); unsigned int hash = 0; unsigned int test = 0; for(std::size_t i = 0; i < str.length(); i++) { hash = (hash << OneEighth) + str[i]; if((test = hash & HighBits) != 0) { hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits)); } } return hash; } /* End Of P. J. Weinberger Hash Function */ unsigned int ELFHash(const std::string& str) { unsigned int hash = 0; unsigned int x = 0; for(std::size_t i = 0; i < str.length(); i++) { hash = (hash << 4) + str[i]; if((x = hash & 0xF0000000L) != 0) { hash ^= (x >> 24); } hash &= ~x; } return hash; } /* End Of ELF Hash Function */ unsigned int BKDRHash(const std::string& str) { unsigned int seed = 131; // 31 131 1313 13131 131313 etc.. unsigned int hash = 0; for(std::size_t i = 0; i < str.length(); i++) { hash = (hash * seed) + str[i]; } return hash; } /* End Of BKDR Hash Function */ unsigned int SDBMHash(const std::string& str) { unsigned int hash = 0; for(std::size_t i = 0; i < str.length(); i++) { hash = str[i] + (hash << 6) + (hash << 16) - hash; } return hash; } /* End Of SDBM Hash Function */ unsigned int DJBHash(const std::string& str) { unsigned int hash = 5381; for(std::size_t i = 0; i < str.length(); i++) { hash = ((hash << 5) + hash) + str[i];...
Looking for solution of this Assignment?
WHY CHOOSE US?
We deliver quality original papers
|
Our experts write quality original papers using academic databases.We dont use AI in our work. We refund your money if AI is detected |
Free revisions
|
We offer our clients multiple free revisions just to ensure you get what you want. |
Discounted prices
|
All our prices are discounted which makes it affordable to you. Use code FIRST15 to get your discount |
100% originality
|
We deliver papers that are written from scratch to deliver 100% originality. Our papers are free from plagiarism and NO similarity.We have ZERO TOLERANCE TO USE OF AI |
On-time delivery
|
We will deliver your paper on time even on short notice or short deadline, overnight essay or even an urgent essay |