How to get the length of the maximum chain of a hash table?

Question

I have a hash table program shown below

#include<bits/stdc++.h> 
#include <algorithm>
std::string fileName;
std::fstream readFile;
const int arraySize = 100;
int storeFile[arraySize]; 

class Hash 
{ 
    std::list<int> *table; 
    std::list<int>::iterator anItetator;
public:  
    int count = 0;
    int mod = 100; 
    Hash();
    Hash(int Value);  

    void insertItem(int key); 

    int hashFunction(int key) { 
        return (key % mod); 
    } 
  
    void loopHash(); 

    void displayHash(); 
};

Hash::Hash(){

} 

Hash::Hash(int b) 
{ 
    this->mod = b; 
    table = new std::list<int>[mod]; 
} 
  
void Hash::insertItem(int key) 
{ 
    int index = hashFunction(key); 
    table[index].push_back(key);  
} 

void Hash::displayHash() { 
  for (int i = 0; i < mod; i++) { 
    std::cout << i; 
    for (auto x : table[i]) 
      std::cout << " --> " << x; 
    std::cout << std::endl; 
  } 
}

void Hash::loopHash() {

for(anItetator = table->begin(); anItetator != table->end(); ++anItetator){

   if(table->empty()==true) {
    count++;
    }

   std::cout << "Total number of empty entries is: " << count;
   std::cout << "The largest chain is: "  << *std::max_element(table->begin(),table->end());
}

}

int main(int argc, char *argv[])
{
     int n = arraySize;

     Hash h(h.mod); 

     std::cout << "Please enter the name of the file: " << std::endl;
     std::cin >> argv[0];                                            

     fileName = argv[0];

     std::cout << "Attempting to read file " << fileName << std::endl;

     readFile.open(fileName); 

for(int i = 0; i < n; i++) {
 
     while (readFile >> storeFile[i])
     {
        h.insertItem(storeFile[i]); 
     }
}
     //h.displayHash();     
     h.loopHash();
     readFile.close();
     return 0;
}

However theres specific information i need from the results that im not quite sure how to find. These are 2 outputs

The number of empty elements in the hash table
The length of the longest chain

Ive attempted to do something like this with my void Hash::loopHash() however this function prints no values.

If anyone knows about hash-tables and can help me with this that would be great.

Unrelated to your problem, but please don't use online competition sites as a way to learn good code-style and good habits, because they teach the opposite. I also suggest you get [a few good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) or take a few classes to learn C++ properly, because your `loopHash` function contains a couple of pretty serious logical problems. Not to mention your really bad use of `argv[0]` as a temporary storage. Where or who taught you that? — Some programmer dude, Sep 10 '20 at 07:14
I guess you need to use `anItetator` somehow in the `if` condition in `loopHash`?! It's spelled ite**r**ator, by the way. — mkrieger1, Sep 10 '20 at 07:16
It’s been popular lately to use `argv[0]` for storing things. Don’t do it — that’s not what it’s for. Just write `std::cin >> fileName;` — molbdnilo, Sep 10 '20 at 07:53
@molbdnilo: I assume that's a symptom of copy&paste programming. One person does something strange/wrong and suddenly you're seeing it more and more. — President James K. Polk, Sep 10 '20 at 20:25

score 0 · Answer 1 · answered Sep 11 '20 at 02:32

for(anItetator = table->begin(); anItetator != table->end(); ++anItetator){ iterates over the elements in the first std::list, because table is a pointer to a list<> (but that list is expected to the first of mod such lists effectively forming an array of lists).

What you should do to inspect each bucket in the hash table is access table as an array, using the array length you know you called new with to allocate the memory; e.g.

int num_empty_buckets = 0;
int longest_chain = 0;
for (int index = 0; index < mod; ++index) {
    if (table[index].empty())
        ++num_empty_buckets;
    longest_chain = std::max(table[index].size(), longest_chain);
}
// print 'em...

How to get the length of the maximum chain of a hash table?

1 Answers1