Chained hash table Insert function

[zspar]

Hello, I was assigned to create a chained hash table using a vector of vectors. It is designed to hold objects of type Entry. I have written all of the functions and the constructor but when I try to use the constructor that reads an input and then output it back to me I an missing some values. I believe its either a problem with my put function (inserts an entry into the table) or my overloaded << operator. But someone told me it might be my hash function as well. I was hoping for some insight to where I might be going wrong from someone with a little more experience. Thanks. Heres my code:

#ifndef entry_h
#define entry_h

// entry.h - defines class Entry              


#include <string>
#include <iosfwd>

class Entry {

public:
    // constructor                                          
    Entry(unsigned int key = 0, std::string data = "");

    // access and mutator functions                         
    unsigned int get_key() const;
    std::string get_data() const;
    static unsigned int access_count();
    void set_key(unsigned int k);
    void set_data(std::string d);

    // operator conversion function simplifies comparisons  
    operator unsigned int () const;

    // input and output friends                             
    friend std::istream& operator>>
    (std::istream& inp, Entry &e);
    friend std::ostream& operator<<
    (std::ostream& out, Entry &e);

private:
    unsigned int key;
    std::string data;
    static unsigned int accesses;
};

#endif /* entry_h */


//  table.h
//  
#ifndef table_h
#define table_h

#include <string>
#include <vector>
#include <algorithm>
#include "entry.h"

using namespace std;

class Table {

 public:
  Table(unsigned int max_entries = 100);
  //Builds empty table to hold 100 entries
  Table(unsigned int entries, std::istream& input);
  //Builds table to hold entries, reads and puts them 1 at a time
  ~Table();
  //Destructor
  void put(unsigned int key, std::string data);
  //Creates new entry for the table
  //Updates if key is used
  void put(Entry e);
  //Creates a copy of e in the table
  string get(unsigned int key) const;
  //Returns string associated with key
  //Returns empty string if key isnt used
  bool remove(unsigned int key);
  //Removes entry in given key
  //Returns true of removed, false of no entry
  int find(Entry e);
  //index in second array that e exists, 0 if not found
  friend std::ostream& operator<< (std::ostream& out, const Table& t);
  //Prints each entry in the table in order of their key
  
  
 private:
  int size;
  int num_entries;
  unsigned int hashkey(unsigned int key) const;
 
  vector<vector<Entry> > A;
};

#endif /* table_h */ 



//table.cpp

#include<iostream>
#include<vector>
#include<algorithm>
#include "table.h"

using namespace std;


Table::Table(unsigned int max_entries){
  max_entries = 100;
  size = max_entries * 2;
  A.resize(size);
}

Table::Table(unsigned int entries, std::istream& input){
  size = entries*2;
  A.resize(size);
  num_entries = entries;
  Entry temp;
  for (int i = 0; i < entries; i++) {
    input >> temp;
    put(temp);
  }
}

/*
Table::~Table() {
  for (int i = 0; i <size; i++) {
    for (int j = 0; j < A[i].size(); j++) {
      delete A[i][j];
    }
  }
  }*/

Table::~Table() {
  A.clear();
}

void Table::put(unsigned int key, std::string data){
  Entry e;
  e.set_key(key);
  e.set_data(data);
  put(e);
  num_entries++;
}

void Table::put(Entry e) {
  if (!A[hashkey(e.get_key())].empty()) {
  // if (find(e) != 0) {
    for(int i = 0; i < A[hashkey(e.get_key())].size(); i++) {
      if(A[hashkey(e.get_key())][i].get_key() == e.get_key()){
    A[hashkey(e.get_key())][i] = e;
    return;
      }
    }
  }
  else {
    A[hashkey(e.get_key())].push_back(e);
    num_entries++;
  }
}

string Table::get(unsigned int key) const {
  if( A[hashkey(key)].size() == 0) {
    return "";
  }
  else {
    for (int i = 0; i < A[hashkey(key)].size(); i++) {
      if (A[hashkey(key)][i].get_key() == key) {
    return A[hashkey(key)][i].get_data();
      }
      else {
    return "";
      }
    }
  }
}

bool Table::remove(unsigned int key) {
  for (int i = 0; i < A[hashkey(key)].size(); i++) {
    if (A[hashkey(key)][i].get_key() == key) {
    swap(A[hashkey(key)][i],A[hashkey(key)][A[hashkey(key)].size() - 1]);
    A[hashkey(key)].pop_back();
    num_entries--; 
        return true;
      }
      else {
    return false;
      }
  }
}
 
int Table::find(Entry e) {
  for (int i = 0; i < A[hashkey(e.get_key())].size(); i++) {
      if (A[hashkey(e.get_key())][i] == e) {
    return i;
      }
      else {
    return 0;
      }
  }
}
      
ostream& operator << (ostream& out, const Table& t) {
  vector<Entry> order;
  for( int i = 0; i < t.A.size(); i++) {
    for (int j = 0; j < t.A[i].size(); j++) {
      order.push_back(t.A[i][j]);
    }
  }
  sort(order.begin(), order.end());
  for(Entry k: order) {
    out << k << endl;
  }
  return out;
}

unsigned int Table::hashkey(unsigned int key) const{
  const double c = 1.61803;
  // return key % size;
  return (int)(size*((key * c) - (int)(key * c)));
}

[TheIdeasMan]

Hi,

Consider using a member initializer list in your constructor, rather than assignment:
http://en.cppreference.com/w/cpp/language/initializer_list

Make sure you initialise all the member variables, and in the same order as in the class definition.

I put your code into cpp.sh, and turned on all 3 warning levels. There are a number of warnings:

Lots of sign compare warnings on lines 112, 142, 160, 172, 186. The size functions return a std::size_t so you should use this type in the for loops:
for(std::size_t i = 0; i < A[hashkey(e.get_key())].size(); i++) {

Several control reaches end of non-void function on lines 169, 183, 194

Somehow, there will be a path in the if else chain that doesn't return anything.

I think it is about time you didn't have using namespace std; , you have several header files, so run an increased risk of name clashes. It may not be a problem right now, but it will be one day.

Also a good idea is to put your own code in it's own namespace.

[TheIdeasMan]

Also, there are more places you could use const, especially for function parameters.

Pass class arguments by reference, with const if you can.

[zspar]

Thanks for the suggestions I'll try to work on that. Any idea if its the put function or the << operator thats messing stuff up? Or a combo of both?

[TheIdeasMan]

Hi,

Try using the debugger in your IDE. Set a breakpoint, a watchlist of variables, step through 1 line at a time, keep an eye on the value of the variables, deduce where it goes wrong.

[Thomas1965]

Why don't you test each piece separately?
Much easier to see where the problem is.
An easy to use test framework is doctest.
https://www.codeproject.com/Articles/1156938/doctest-the-lightest-Cplusplus-unit-testing-framew

[dhayden]

Line 101: you leave num_entries uninitialized

Line 110: you set num_entries here, but the call to put() at line 114 increments it too.

Table::put(unsigned int key, std::string data) always increments num_entries, but it also calls put(Entry) which sometimes increments num_entries.

Yuck. My advice is to decide who will increment num_entries and then fix to code to keep with your policy.

put(Entry): Suppose the hash bucket is not empty, but the Entry isn't in there. In that case you will never insert it.

void Table::put(Entry e) {
  if (!A[hashkey(e.get_key())].empty()) {
  // if (find(e) != 0) {
    for(int i = 0; i < A[hashkey(e.get_key())].size(); i++) {
      if(A[hashkey(e.get_key())][i].get_key() == e.get_key()){
    A[hashkey(e.get_key())][i] = e;
    return;
      }
    }
  }
  else {
    A[hashkey(e.get_key())].push_back(e);
    num_entries++;
  }
}

The underlined value doesn't change so do yourself a favor and just put it in a local variable:

void Table::put(Entry e) {
    unsigned int hash = hashkey(e.get_key());
  if (!A[hash].empty()) {
  // if (find(e) != 0) {
    for(int i = 0; i < A[hash].size(); i++) {
      if(A[hash][i].get_key() == e.get_key()){
    A[hash][i] = e;
    return;
      }
    }
  }
  else {
    A[hash].push_back(e);
    num_entries++;
  }
}

The same comment applies in other places too.

Lines 160-167: The first time through the loop, the function will return at line 162, or it will return at line 165. What if the value you seek is the second one in the hash bucket?

Your remove() and find() functions seem to have the same problem: a loop that contains an if/else statement that returns in both branches. So the loop only ever executes once.