**/***

*****

**NAME: Eric Amoh Adjei**

**DATE: 01/28/2024**

**Assignment 3: Create your own Hash function**

*****

***/**

**//This includes the standard input and output library in C++. It's used for operations like reading from and writing to the console.**

**#include <stdio.h>**

**// It provides functionalities for dynamic memory allocation, random number generation, communication with the environment, integer arithmetic, searching, sorting, and converting.**

**#include <stdlib.h>**

**// including iostream directive tells the preprocessor to include other contents file.**

**#include <iostream>**

**//Stream class to both read and write from/to files.**

**#include <fstream>**

**// with the include String, we can not display a string output or alphabetical characters.**

**#include <string>**

**// windows.h library allow coders to do more like adding delays like sleep for some seconds**

**#include <windows.h>**

**//algorithms library defines functions for a variety of purposes**

**#include <algorithm>**

**//Constructs a container with as many elements as the range**

**#include <vector>**

**//defines several general purpose functions, including dynamic memory management, random number generation and more**

**#include <cstdlib>**

**//Interprets the value pointed by timer as a calendar time and converts it to a C-string containing a human-readable version**

**#include <ctime>**

**//an array includes a certain value among its entries, returning true or false as appropriate**

**#include <array>**

**//defines variable types, two macro and various functions for manipulating date and time.**

**#include <time.h>**

**//declares a set of functions to classify and transform individual characters.**

**#include <cctype>**

**//This includes the standard library header file for the std::list container. std::list in C++ is a sequence container that allows non-contiguous memory allocation.**

**#include <list>**

**#include <random> // Include for random function**

**#include <cmath> // Include for sqrt function**

**#include <numeric> // Include for accumulate function**

**// using namespace std to avoid std:: cout repetitions in our code**

**using namespace std;**

**// Defining the size of the hash tables**

**vector<int> tableSizes = { 1000, 10000, 100000 };**

**// Hash Function 1: Simple Division Hash**

**int hashFunction1(int key, int size)**

**{**

**return key % size;**

**}**

**// Hash Function 2: Multiplication Hash**

**int hashFunction2(int key, int size)**

**{**

**double A = (sqrt(5) - 1) / 2.0; // A constant (phi - 1) / 2**

**return static_cast<int>(size * fmod(key * A, 1.0));**

**}**

**// Hash Function 3: DJB2 Hash (a popular hash function)**

**int hashFunction3(int key, int size) {**

**unsigned int hash = 5381;**

**string keyStr = to_string(key);**

**for (char c : keyStr) {**

**hash = ((hash << 5) + hash) + c;**

**}**

**return hash % size;**

**}**

**// Function to generate a hash table and calculate distribution**

**void generateAndAnalyzeHashTable(int (*hashFunction)(int, int), int size)**

**{**

**std::vector<int> hashTable(size, 0);**

**for (int i = 0; i < size; ++i)**

**{**

**int key = rand() % 1000000; // Generate random keys**

**int index = hashFunction(key, size); // Get the index from the hash function**

**hashTable[index]++;**

**}**

**// Calculate distribution statistics**

**int maxValue = *max_element(hashTable.begin(), hashTable.end());**

**int minValue = *min_element(hashTable.begin(), hashTable.end());**

**double avgValue = static_cast<double>(accumulate(hashTable.begin(), hashTable.end(), 0)) / size;**

**cout << "Maximum value in a slot: " << maxValue << endl;**

**cout << "Minimum value in a slot: " << minValue << endl;**

**cout << "Average value in a slot: " << avgValue << endl;**

**}**

**int main()**

**{**

**srand(static_cast<unsigned int>(time(nullptr)));**

**// Perform analysis for each hash function and table size**

**for (int size : tableSizes) {**

**cout << "Table Size: " << size << endl;**

**// Hash Function 1**

**cout << "Hash Function 1:" << endl;**

**generateAndAnalyzeHashTable(hashFunction1, size);**

**// Hash Function 2**

**cout << "Hash Function 2:" << endl;**

**generateAndAnalyzeHashTable(hashFunction2, size);**

**// Hash Function 3**

**cout << "Hash Function 3:" << endl;**

**generateAndAnalyzeHashTable(hashFunction3, size);**

**cout << "=====================================" << endl;**

**}**

**return 0;**

**}**