-
Notifications
You must be signed in to change notification settings - Fork 0
/
DataStructuresLab7hashMap.h
42 lines (36 loc) · 2.18 KB
/
DataStructuresLab7hashMap.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
* hashMap.h
*
* Created on: May 5, 2017
* Author: Christian Sutton
*/
#ifndef HASHMAP_H_
#define HASHMAP_H_
#include "hashNode.h"
using namespace std;
class hashMap {
friend class makeSeuss;
hashNode **map;
string first; // for first keyword for printing to a file
int numKeys;
int mapSize;
public:
hashMap(); // when creating the map, make sure you initialize the values to NULL so you know whether that index has a key in it or not already
void addKeyValue(string k, string v);
// adds a node to the map at the correct index based on the key string, and then inserts the value into the value field of the hashNode
// Must check to see whether there's already a node at that location. If there's nothing there (it's NULL), add the hashNode with the keyword and value.
// If the node has the same keyword, just add the value to the list of values.
//If the node has a different keyword, keep calculating a new hash index until either the keyword matches the node at that index's keyword, or until the
// map at that index is NULL, in which case you'll add the node there.
//This method also checks for load, and if the load is over 70%, it calls the reHash method to create a new longer map array and rehash the values
int getIndex(string k); // uses calcHash and reHash to calculate and return the index of where the keyword k should be inserted into the map array
int calcHash(string k); // hash function
void getClosestPrime(); // I used a binary search on an array of prime numbers to find the closest prime to double the map Size, and then set mapSize to that new prime. You can include as one of the fields an array of prime numbers, or you can write a function that calculates the next prime number. Whichever you prefer.
void reHash(); // when size of array is at 70%, double array size and rehash keys
bool isPrime(int number); // find prime numbers
int dblHash(int h, int i, string k); // for hashing when index is already full
int findKey(string k); //finds the key in the array and returns its index. If it's not in the array, returns -1
void printMap(); //I wrote this solely to check if everything was working.
~hashMap();
};
#endif /* HASHMAP_H_ */