Recursive Insertion in Hash Table (Linear Probing)

Question

I was practicing implementing a hash function. I tried to use linear probing to insert in hash table. The insertion is working alright but I am not satisfied with the recursion. It doesn't feel like "good recursion". The Linear_Probing function instead of being recursive itself uses two other functions (excluding hash function) for recursive insertion: Index_Finder() and its auxiliary function.

Is there any way I can do the recursion better in this code for inserting into a hash table?

int Hash(int number); //<Hash function returns index by adding the first and last digit of a number;
bool Linear_Probing(int array[], bool flags [], int MAX_SIZE, int number, int &collisions); //<This function if possible inserts the number in the Hash Table 
int Index_Finder(int number, bool flags[], int MAX_SIZE, int &collisions); //<This function finds the index where the number should be inserted. It returns -1 if no empty slot is found.
int Index_Finder(bool flags[], int MAX_SIZE, int index, int limit, int &collisions); //<This is an auxilary function


int main()
{
    const int MAX_SIZE = 11;
    int collisions = 0;
    int array[MAX_SIZE];
    bool flags[MAX_SIZE];

    for (int i = 0; i < MAX_SIZE; i++)
    {
        array[i] = 0;
        flags[i] = false;

    }

    //<Inserting numbers in hash table using linear probing
    Linear_Probing(array, flags, MAX_SIZE, 67, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 19, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 3, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 808, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 337, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 1, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 86, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 38, collisions);

    return 0;
}

bool Linear_Probing(int array[], bool flags[], int MAX_SIZE, int number, int &collisions)
{
    int dummy_collisions = 0;
    int index = Index_Finder(number, flags, MAX_SIZE, dummy_collisions);

    if (index == -1)
        return false;

    else
    {
        collisions += dummy_collisions;

        array[index] = number;
        flags[index] = true;
        return true;
    }
}

int Index_Finder(int number, bool flags[], int MAX_SIZE, int &collisions)
{
    int index = Hash(number);

    if (index < MAX_SIZE && !flags[index])
        return index;

    if (index >= MAX_SIZE)
    {
        index = 0;

        if (!flags[index])
            return index;

        else
            collisions++;
    }

    else
    {
        collisions++;
    }

    int limit = index;

    return Index_Finder(flags, MAX_SIZE, ++index, limit, collisions);

}

int Index_Finder(bool flags[], int MAX_SIZE, int index, int limit, int &collisions)
{
    if (limit == index)
        return -1;

    if (index == MAX_SIZE)
        index = 0;

    if (!flags[index])
        return index;

    else
    {
        collisions++;
        return Index_Finder(flags, MAX_SIZE, ++index, limit, collisions);
    }
}


int Hash(int number)
{
    int first_digit = 0, last_digit = 0;
    bool first_time = true;

    while (number > 0)
    {
        if (first_time)
        {
            first_digit = number % 10;
            number -= (number % 10);
            number /= 10;
            first_time = false;
        }

        else
        {
            last_digit = number % 10;
            number -= (number % 10);
            number /= 10;
        }
    }

    return (first_digit + last_digit);
}

Answer 1

• When commenting to describe a function's purpose, it's more common to have them on top of the signature of the function definition. Having them next to the prototypes like that makes those lines harder to read and increases the code'd horizontal length.

• Your curly brace usage with single-line statements is inconsistent. It's also better to use them for all statements like these and can prevent some bugs and ease maintenance.

• Instead of initializing the arrays with a loop, you can use std::fill_n():

  std::fill_n(array, MAX_SIZE, 0);
  std::fill_n(flags, MAX_SIZE, false);
  

  While it may not matter in smaller programs, it's still more concise and can be safer.

• You're passing C-arrays to functions, which shouldn't be done in C++ as this will cause them to decay to pointers. Instead, pass in an object of a container class such as std::vector (dynamic) or std::array (static). Choose whichever best gets the job done for you.

Answer 2

• You should definitely reduce the length of those lines where you declare the function prototypes. Just as @Jamal said, put the comments in the line above each function signature.

• Another advantage of using std::array or std::vector is that you can ditch that MAX_SIZE constant and function parameters with the same name, since the standard containers know their lengths via the size() method.

• Speaking of MAX_SIZE, all uppercase is fine for constants, but shouldn't be used in other places precisely because that notation is frequently associated with constants and macros, thus using it for a function parameter name is liable to cause confusion.

• When you write an if/else pair where both paths return, such as here:

  if (index == -1)
      return false;
  
  else
  {
      collisions += dummy_collisions;
  
      array[index] = number;
      flags[index] = true;
      return true;
  }
  

  Don't make that an if/else chain. Just return in the first if and omit the else statement. That will avoid unnecessary nesting.

• return 0 at the end of main() is optional. If you omit it, the compiler defaults to a return 0.

• Minor point, just FYI, your naming convention for functions is somewhat unusual. Windows-centric code usually applies PascalCase to function names, without that underscore between words. camelCase and snake_case are also very popular for method naming.

Answer 3

1. That seems like a really terrible hashing algorithm. 1001 and 10001 will have the same value. The more traditional hashing function to use is a simple modulus, although depending on your data domain that might not necessarily be the case (but it's very unlikely that your provided algorithm will be even remotely useful except in the most contrived scenarios).

2. As others have said, you should format your doxygen comments completely differently; I'd go with a style like this: (I am making a lot of assumptions regarding your parameters, incidentally, the avoidance of which being the entire point to using Doxygen in the first place...)

   /*! Inserts the number in the hash table
    *
    *  @param array The hash table values
    *  @param flags The occupancy flags
    *  @param MAX_SIZE The size of the hash table
    *  @param number The number to insert
    *  @param[out] collisions The number of collisions that occurred
    *  @returns whether insertion was successful
    */
   bool Linear_Probing(int array[], bool flags[], int MAX_SIZE, int number, int &collisions);
   

3. Instead of using separate arrays that you pass into things on each call, this is a perfect opportunity to use objects to encapsulate things. For a partial example:

   //! Hash table class
   class HashTable {
   public:
       //! Construct a hash table of a specific size
       HashTable(size_t size);
   
       //! Attempt to insert this number, tracking the number of collisions
       bool insert(int number, size_t& collisions);
   
       //! Attempt to insert this number, discarding the collision count
       bool insert(int number) {
           size_t c; // discarded
           return insert(number, c);
       }
   
   private:
       std::vector<int> mValues;
       std::vector<bool> mOccupancy;
   };
   

   Then when you implement your constructor, you'd have:

   HashTable::HashTable(size_t size): mValues(size), mOccupancy(size) {}
   

   to allocate the arrays. You could also consider providing the hashing function as a template or constructor argument and have it just default to simple modulus (for example).

4. There is no reason to do Index_Finder recursively, or even as a separate function from insert; it is just a simple iterative loop. Consider doing this in your insert function:

   bool insert(int n, size_t& collisions) {
       size_t start = n % mValues.size(); // or a call to your hashing function etc.
       size_t pos = start;
       collisions = 0;
       do {
           if (!mOccupancy[pos]) {
               mValues[pos] = n;
               mOccupancy[pos] = true;
               return true;
           }
           ++collisions;
           pos = (pos + 1) % mValues.size();
       } while (pos != start);
       return false;
   }
   

   This implements simple linear probing as part of insert without any need for any crazy code flow.