# Hashing function and bloom filter

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 <iostream> //iostrem
#include <string>   //string
#include <vector>   //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];
}

return hash;
}
/* End Of DJB Hash Function */

unsigned int DEKHash(const std::string& str)
{
unsigned int hash = static_cast(str.length());

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

return hash;
}
/* End Of DEK Hash Function */

unsigned int BPHash(const std::string& str)
{
unsigned int hash = 0;
for(std::size_t i = 0; i < str.length(); i++)
{
hash = hash << 7 ^ str[i];
}

return hash;
}
/* End Of BP Hash Function */

unsigned int FNVHash(const std::string& str)
{
const unsigned int fnv_prime = 0x811C9DC5;
unsigned int hash = 0;
for(std::size_t i = 0; i < str.length(); i++)
{
hash *= fnv_prime;
hash ^= str[i];
}

return hash;
}
/* End Of FNV Hash Function */

unsigned int APHash(const std::string& str)
{
unsigned int hash = 0xAAAAAAAA;

for(std::size_t i = 0; i < str.length(); i++)
{
hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ str[i] * (hash >> 3)) :
(~((hash << 11) + (str[i] ^ (hash >> 5))));
}

return hash;
}
/* End Of AP Hash Function */

GeneralHashFunctions.h

#ifndef INCLUDE_GENERALHASHFUNCTION_CPP_H
#define INCLUDE_GENERALHASHFUNCTION_CPP_H

#include

typedef unsigned int (*HashFunction)(const std::string&);

unsigned int RSHash (const std::string& str);
unsigned int JSHash (const std::string& str);
unsigned int PJWHash (const std::string& str);
unsigned int ELFHash (const std::string& str);
unsigned int BKDRHash(const std::string& str);
unsigned int SDBMHash(const std::string& str);
unsigned int DJBHash (const std::string& str);
unsigned int DEKHash (const std::string& str);
unsigned int BPHash (const std::string& str);
unsigned int FNVHash (const std::string& str);
unsigned int APHash (const std::string& str);

#endif

Pages (550 words)
Approximate price: -

Why Choose Us Quality Papers

We value our clients. For this reason, we ensure that each paper is written carefully as per the instructions provided by the client. Our editing team also checks all the papers to ensure that they have been completed as per the expectations. Over the years, our Acme Homework has managed to secure the most qualified, reliable and experienced team of writers. The company has also ensured continued training and development of the team members to ensure that it keep up with the rising Academic Trends. Affordable Prices

Our prices are fairly priced in such a way that ensures affordability. Additionally, you can get a free price quotation by clicking on the "Place Order" button. On-Time delivery

We pay strict attention on deadlines. For this reason, we ensure that all papers are submitted earlier, even before the deadline indicated by the customer. For this reason, the client can go through the work and review everything. 100% Originality

At Papers Owl, all papers are plagiarism-free as they are written from scratch. We have taken strict measures to ensure that there is no similarity on all papers and that citations are included as per the standards set. Our support team is readily available to provide any guidance/help on our platform at any time of the day/night. Feel free to contact us via the Chat window or support email: support@acmehomework.com.

Try it now!

## Calculate the price of your order

We'll send you the first draft for approval by at
Total price:
\$0.00

How it works? Fill in the order form and provide all details of your assignment. Proceed with the payment

Choose the payment system that suits you most. Our Services

Papers Owl has stood as the world’s leading custom essay writing services providers. Once you enter all the details in the order form under the place order button, the rest is up to us.  ## Essay Writing Services

At Papers Owl, we prioritize on all aspects that bring about a good grade such as impeccable grammar, proper structure, zero-plagiarism and conformance to guidelines. Our experienced team of writers will help you completed your essays and other assignments.  Be assured that you’ll definitely get accepted to the Master’s level program at any university once you enter all the details in the order form. We won’t leave you here; we will also help you secure a good position in your aspired workplace by creating an outstanding resume or portfolio once you place an order.    