Question

C++

Based upon the information provided on Hashing and Hash tables, create a Hash Table to store the data in the provided file which is a list of colors,ColorList.txt

Using the basic algorithm that adds the ASCII values of each letter in the color and then mods by your chosen number of bins. Determine the best size (number of bins) for your hash table that is close to Balanced with an average list length between 12-15 (NOTE: list lengths of 0 do not count in the average).

Your code should do the average list length calculations for you and provide the recommendation for the best array size.


ColorList.txt

Air Force blue Alice blue Alizarin crimson Almond Amaranth Amber American rose Amethyst Android Green Anti-flash white Antique brass Antique fuchsia Antique white Apple green Apricot Aqua Aquamarine Army green Arylide yellow Ash grey Asparagus Atomic tangerine Auburn Aureolin Auro Metal Saurus Awesome Azure Azure mist/web Baby blue Baby blue eyes Baby pink Ball Blue Banana Mania Banana yellow Battleship grey Bazaar Beau blue Beaver Beige Bisque Bistre Bittersweet Black Blanched Almond Bleu de France Blizzard Blue Blond Blue Blue Bell Blue Gray Blue green Blue purple Blue violet Blush

That's all the information I have on the assignment.

From what I understand. I need to.

load the text file in the program.

Convert each of those words into a ASCII value.

Then once that value has been converted have that value placed in a bin.

The bins should be between 12-15 on average length.

Answer 1

Structure of the answer

1. Explanation
2. Code Images and Text Format
3. Images of ColorList.txt and the output.

The load factor is a measure used to determine the trade-off between time and space costs.

A higher load factor value decreases the space requirements and increases the odds of a collision. A collision increases the amount of time needed to insert and retrieve the value in a hashtable The Ideal is O(1).

A lower load factor value increases memory requirements but decreases the odds of a collision.

In java, with class HashTable, the default load factor (.75) offers a good tradeoff between time and space costs.

A higher load factor value decreases the space requirements and increases the odds of a collision. A collision increases the amount of time needed to perform a get() and put(...).

A lower load factor value increases disk/memory space requirements, causing lots of reserved space that is permanently unused. The increased number of bins decreases the odds of a collision.

So a load factor of (.75) means the HashTable bins are 75% full. If you have 75 elements to store, the number of bins in your HashTable should be 100. Therefore given N the number of items in your case the colour in the .txt file, the size of hashtable should be 1.33 * N

Note: Since the colours were provided in a single line I had to manually google the name of each colour becz. some colours have more than 1 words in their names. In doing this I found that the total no. of colours was 48. Don't worry if that's not the actual number the programme should programmatically calculate the best no of bins.

In your case N = 48. (the one I obtained)

and Size = 1.33 * N => 64 (round it)

The load factor = 48 / 64 = 0.75 or 75% which is good

Code:

File Edit Selection View Go Run Terminal Help hashtable.cpp -project-api - Visual Studio Code X fo E- hashtable.cpp X E ColorFile.txt C: > Users > CLIVE > Desktop > G+ hashtable.cpp > main() 1 /* 2 To calculate the best array size (no. of bins ) we use load factor 3 4 5 The best way to calculate load factors is 6 7 if n = 'no. of elements to store' 8 9 then no. of bins = 1.33 * n 10 11 */ 12 13 #include <iostream> 14 #include <fstream> 15 #include<math.h> 16 using namespace std; 17 18 19 int hash_function(string color){ 20 21 int hashvalue = 0; 22 23 for(int i =0;i<color.length();i++) 24 بها بها 25 if(color[i] == ' ') 26 continue; 27 28 hashvalue += color[i] ; 29 30 31 return hashvalue; 32 33 } A Select Python Interpreter Ⓡ3 AO Type here to search Ln 73, Col 38 Spaces: 4 UTF-8 CRLF C++ Go Live Win32 11:49 19-05-2020 1 It j e ^^x ENG

File Edit Selection View Go Run Terminal Help hashtable.cpp -project-api - Visual Studio Code х نہا } E. { E- hashtable.cpp X e ColorFile.txt c> Users > CLIVE > Desktop > G+ hashtable.cpp > maino 28 hashvalue += color[i] ; 29 30 go 31 return hashvalue; 32 33 34 35 36 37 38 09 39 int main() 40 41 42 43 44 string color; 45 46 // Read from the text file 47 ifstream MyReadFile("ColorFile.txt"); 48 49 50 int counter=0; 51 52 // Use a while loop together with the getline() function to read the file line by line 53 while(getline (MyReadFile, color)) { 54 counter++; 55 56 MyReadFile.close(); 57 58 int best_bin_size = round(1.33 * counter); 59 A Select Python Interpreter 3 A 0 Type here to search } Ln 73, Col 38 Spaces: 4 UTF-8 CRLF C++ Go Live Win32 11:49 19-05-2020 Ö 1 E ^^x ENG

File Edit Selection View Go Run Terminal Help hashtable.cpp - project-api - Visual Studio Code х } G+ hashtable.cpp X E ColorFile.txt C: > Users > CLIVE > Desktop > G+ hashtable.cpp > maino 51 52 // Use a while loop together with the getline() function to read the file line by line 53 while(getline (MyReadFile, color)) { 54 counter++; go 55 56 MyReadFile.close(); 57 58 int best_bin_size = round(1.33 * counter); 59 60 cout<<< "No. of Colors = "<<counter << "\n"; 61 cout<< "best bin size = "<< best_bin_size<<"\n"; 62 09 63 64 string HashTable[best bin size]; 65 66 ifstream MyReadFile("ColorFile.txt"); 67 68 while(getline (MyReadFile2, color)) { 69 70 int index = hash_function(color) % best_bin_size; 71 72 //uncommnet this to check for any collisions; 73 cout<< index<<" "<<color<<"\n"; 74 75 HashTable[index] = color; 76 77 78 79 80 81 MyReadFile2.close();|| 82 return 0; 83 } A Select Python Interpreter 3 A 0 Type here to search } Ln 81, Col 25 Spaces: 4 UTF-8 CRLF C++ Go Live Win32 11:49 19-05-2020 1 j ^x ENG

 /* To calculate the best array size (no. of bins ) we use load factor The best way to calculate load factors is if n = 'no. of elements to store' then no. of bins = 1.33 * n */ #include <iostream> #include <fstream> #include<math.h> using namespace std; int hash_function(string color){ int hashvalue = 0; for(int i =0;i<color.length();i++) { if(color[i] == ' ') continue; hashvalue += color[i] ; } return hashvalue; } int main() { string color; // Read from the text file ifstream MyReadFile("ColorFile.txt"); int counter=0; // Use a while loop together with the getline() function to read the file line by line while(getline (MyReadFile, color)) { counter++; } MyReadFile.close(); int best_bin_size = round(1.33 * counter); cout<< "No . of Colors = "<<counter << "\n"; cout<< "best bin size = "<< best_bin_size<<"\n"; string HashTable[best_bin_size]; ifstream MyReadFile2("ColorFile.txt"); while(getline (MyReadFile2, color)) { int index = hash_function(color) % best_bin_size; //uncommnet this to check for any collisions; //cout<< index<<" "<<color<<"\n"; HashTable[index] = color; } MyReadFile2.close(); return 0; }

The Colorlist.txt file I Used.

File Edit Selection View Go Run Terminal Help ColorFile.txt - project-api - Visual Studio Code х 0 - go C- hashtable.cpp E ColorFile.txt x c > Users > CLIVE > Desktop > E ColorFile.txt 1 Air Force blue 2 Alice blue 3 Alizarin crimson 4 Almond 5 Amaranth Amber 6 American rose 7 Amethyst 8 Android 9 Green 10 Anti-flash white 11 Antique brass 12 Antique fuchsia 13 Antique white 14 Apple green 15 Apricot 16 Aqua 17 Aquamarine Army green 18 Arylide yellow 19 Ash grey 20 Asparagus 21 Atomic tangerine 22 Auburn 23 Aureolin Auro 25 Metal 26 Saurus 27 Awesome 28 Azure 29 Azure mist/web 30 Baby blue 31 Baby blue 32 eyes 33 Baby pink A Select Python Interpreter 3 AO Type here to search 24 Ln 43, Col 12 Spaces: 4 UTF-8 CRLF Plain Text Go Live 11:50 19-05-2020 1 I e 1 ADOX ENG

File Edit Selection View Go Run Terminal Help ColorFile.txt - project-api - Visual Studio Code х do E. 6- hashtable.cpp E ColorFile.txt x c> Users > CLIVE > Desktop > B ColorFile.txt 21 Atomic tangerine 22 Auburn 23 Aureolin 24 Auro 25 Metal 26 Saurus 27 Awesome 28 Azure 29 Azure mist/web 30 Baby blue 31 Baby blue 32 eyes 33 Baby pink 34 Ball Blue 35 Banana Mania 36 Banana yellow 37 Battleship grey 38 Bazaar Beau blue 39 Beaver Beige Bisque 40 Bistre Bittersweet Black 41 Blanched Almond Bleu 42 de France Blizzard Blue 43 Blond Blue | 44 Bell Blue 45 Gray Blue 46 green Blue 47 purple Blue 48 violet Blush Ln 43, Col 12 Spaces: 4 UTF-8 CRLF Plain Text A Select Python Interpreter 3 A 0 Type here to search Go Live 11:50 19-05-2020 1 1 ADOX ENG

Output: You can comment out the line (read the comments) in the 2nd while loop if you don't want the index and colour printing per line but this helps is detecting any collisions

File Edit Selection View Go Run Terminal Help hashtable.cpp -project-api - Visual Studio Code X Code A 99 PROBLEMS 2 OUTPUT TERMINAL DEBUG CONSOLE Luonej exited with code=0 in 1.519 seconas E. [Running] cd "c:\Users\CLIVE\Desktop\" && g++ hashtable.cpp -o hashtable && "c:\Users\CLIVE\Desktop\"hashtable No. of Colors = 48 best bin size = 64 do 51 Air Force blue 6 Alice blue 53 Alizarin crimson 27 Almond 19 Amaranth Amber 25 American rose 15 Amethyst 1 Android 49 Green 40 Anti-flash white 50 Antique brass 58 Antique fuchsia 56 Antique white 3 Apple green 18 Apricot 8 Aqua 46 Aquamarine Army green 38 Arylide yellow 19 Ash grey 39 Asparagus 26 Atomic tangerine 45 Auburn 63 Aureolin 23 Auro 51 Metal 3 Saurus 17 Awesome 7 Azure 49 Azure mist/web A Select Python Interpreter ® 2 A 0 Ln 72, Col 55 Spaces: 4 UTF-8 Type here to search CRLF C++ Go Live Win32 11:53 19-05-2020 1 1 ^x ENG