# Recursive Insertion in Hash Table (Linear Probing)

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);
}

• Welcome to Code Review! That's an interesting question, I hope you get some good reviews! – Phrancis Dec 26 '14 at 16:57

• 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.

• 1. The commenting idea is good. Thanks. 2. Okay, but how will it actually make a difference if the implementation of fill_n() also uses a loop. The time complexity will remain the same, doesn't it? 3. I only need to read/write the contents of the array with O(1) and position matters. I really can't think of any advantage of vector class. Mind telling me? and "std::vector (dynamic) or std::array (static)" Didn't I use an array? O.O – Tehmas Dec 26 '14 at 18:27
• Using loops anyway isn't a big deal here, but using this function can leave a little less room for error, especially if bounds-checking wasn't done well. Yes, you've used an array, but it's one used in C and not so much in C++. Many will still tell you to stop using them, especially when passing them to functions. – Jamal Dec 26 '14 at 18:38
• 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.

• 1. Alright :) 2. Now that is really an advantage. Thanks for telling. 3 & 4. Yeah you are right. I didn't notice that while writing the code. 5. The compiler defaults to a return 0 but isn't it better to write to ensure that the code can also easily work on other compilers? 6. Thanks for telling about the different styles. ) – Tehmas Dec 27 '14 at 9:13
• @Tehmas, the default return 0 is required by the standard, so a compiler that misses it is broken. There is a discussion here. That point was mainly informational, since having the explicit return is not a bad thing. Some might argue that it is boilerplate code, though I don't consider it to be harmful. – glampert Dec 27 '14 at 13:57
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) {
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.

• 1. That algorithm was just used to test linear probing. 2. Sir! What you told about Doxygen is indeed awesome! 3. Creating a class is really a good idea. 4. Yeah I know it doesn't need to be done recursively but I'm did recursively to see how the things turn out at the end. However as I have said in the question, I don't think that that is "good recursion". Thanks @fluffy! – Tehmas Dec 27 '14 at 9:05
• @Tehmas You can also apply that particular looping construct to a separate index_finder if you like. – fluffy Dec 27 '14 at 20:09