Creating an insert function for a specific hash table in c++

Question

I am trying to make a template hash table that uses an array of lists to store data. for the table I am trying to write an insert function for hash table that creates a new list if the hash index points to a section that does not already have a list in it.

here is the basics of the class:

template <class T>
class Hash
{
  public:
   Hash(int buckets);
   Hash(const Hash <T> & rhs);
   ~Hash() { delete [] table; }

   /*some functions removed for brevity*/ 

   void insert(const T & t);   //this is the function I am struggling with

   virtual int hash(const T & t) const = 0;

private:
   list <T> * table;
   int numElements;
   int numBuckets;
};

here is my attempt at the insert function:

//insert                                                                                         
template <class T>
void Hash <T> :: insert(const T & t)
{
        if (table[hash(t)] == NULL) // I am not comparing this right 
        {

        //compiler does not like this assignment                                                 
          table[hash(t)] = new list <T>; 
         //insert passed in value into new list                                                  
         table[hash(t)].insert(hash(t));
        }
       else
       {
          //insert passed in value into list                                                  
         table[hash(t)].insert(hash(t));
       }

      numElements++;

}

It is my understanding that my private variable list * table can act as an array.

My questions are: how do I look inside the table variable correctly to see if there is a list created there or not and how do I create a new list at the passed in hash index

edit here is my constructor definition and a hash class of ints:

I am using a non default constructor to get the number of "buckets" that the user wants in the hash table:

//non-default constructor                                                                  
template <class T>
Hash <T> :: Hash(int buckets)
{
   table = new list <T> [buckets];
   numElements = 0;
   numBuckets = buckets;

}

here is the integer hash class:

/****************************************                                                  
 * I HASH                                                                                  
 * A simple hash of integers                                                               
 ****************************************/
class IHash : public Hash <int>
{
public:
   IHash(int numBuckets)    : Hash <int> (numBuckets) {}
   IHash(const IHash & rhs) : Hash <int> (rhs)        {}

   // hash function for integers is simply to take the modulous                            
   int hash(const int & value) const
   {
      int index = abs(value) % capacity();
      assert(0 <= index && index < capacity());
      return index;
   }
};

you do not want to use std::vector or std::array, right? Then I would suggest you to learn about dynamic arrays first. Most importantly: a pointer is not an array — 463035818_is_not_a_number
Edit your question to include the constructor definitions and a class that shows an example hash calculation. — 1201ProgramAlarm
@formerlyknownas_463035818 what I mean by the pointer acting like an array is that is can be indexed like an array. — Megan
@1201ProgramAlarm I added the edits you suggested and I am noticing that I forgot to define the copy constructor which I'm sure is a whole other problem! — Megan
you can index into an array by using a pointer to the first element in an array, but still the distinction between array and pointer is important. You need to create an array first before you can work on it via a pointer. You are attempting to delete an array (delete [] table) but you never create one — 463035818_is_not_a_number

Joseph Larson Joseph Larson · Accepted Answer · 2019-12-05T17:07:09

This whole thing feels a little uncomfortable to me. But you said this line fails:

table[hash(t)] = new list <T>;

You've defined table as:

list <T> * table;

That is, table[0] is of type list NOT list *. I think you probably need to do this:

list<T> ** table;

Frankly, I wouldn't do it that way. I'd do this:

std::vector<list<T> *> table;

BUT you have a HUGE problem with this. What range can your hash() method return? Normally hash values can be really big, so now you're making an array with really huge values.

Your code has other problems, too. You've made table itself a pointer, but you don't show us where you allocate any space for it, nor do you show in your insert method where you expand the space as necessary.

I'll say this: there are reasons why hash table implementations do NOT use arrays. They tend to use btrees, or if not balanced trees, at least trees (because keeping btrees balanced is a pain in the ass).

Creating an insert function for a specific hash table in c++

2 Answers