Quadratic probing insert function help

[noellieb]

Hi all, i am trying to do a quadratic hashing but i am having some
difficulties probably because i am not in the right logic.using this
code:

#include <iostream>

using namespace std;

int find(int);
void insert(int);

const unsigned int size = 13;
int load = 0;	// number of slots currently occupied
int A[size];
/**
*returns the array index where the integer key x is found. 
* If x is not in the hash table, return -1  
*/
int find(int searchKey)
{
    int hash= searchKey % size; //hash formula 
    if(A[hash]== searchKey )
    	return hash;
    else
    	return -1; 
}

/**
 * inserts the key x in the hash table if it is possible.  
 * It does not insert x if either (a) x is already in the hash table 
 * or (b) inserting x will make the hash table more than half full
 *
 */
void insert(int newItem)// Please help not sure 
{
	int hashVal;
	if(find(newItem)!= -1)// call to find index exist
	{
		hashVal = find(newItem);// know the position or hash
  		while(A[hashVal]!= NULL)// check if position is empty
  		{
  			hashVal = hashVal + (int)Math.pow(load,2); 
                                                 //quadratically go to next cell 
        	                                hashVal %= size; 
        	                                A[hashVal]= newItem // insert new item at the position 
  			load++; // keep count of insert
  			cout << newItem <<" is inserted  to slot " << initPos << endl;  
  		}
  		A[hashVal]= newItem // insert new item at the position 
  		load++; // keep count of insert
  		cout << newItem <<" is inserted  to slot " << initPos << endl; 
	}
   	cout << newItem <<" is not  inserted  to slot to avoid load limit " << endl; 	
   		else 
   		 if (++load > size/2)
   		 {
   		 	need helP!!!!!!
	     }
}

[Narue]

>if(find(newItem)!= -1)
This doesn't make sense. You're only inserting into the table if the item already exists? :confused: I think you should avoid that confusion altogether and just hash straight from the insert function.

>if(find(newItem)!= -1)// call to find index exist
>hashVal = find(newItem);// know the position or hash
That's kind of silly, you're calling your find function twice for no good reason.

>A[hashVal]= newItem // insert new item at the position
>load++; // keep count of insert
>cout << newItem <<" is inserted to slot " << initPos << endl;
This is in entirely the wrong place. What you're doing now is overwriting whatever was already at that position. You need to find the right empty slot first, then add the new item to it.

>hashVal = hashVal + (int)Math.pow(load,2);
Are you trying to convert Java to C++ or something?

>if (++load > size/2)
You shouldn't dictate this. Give the caller a way to check the load and determine when they want to treat the table as too full. That way your hash table is more flexible.

Here's my suggestion:

/// <summary>
/// Insert a new item into the hash table
/// </summary>
/// <param name="newItem">The item to insert</param>
/// <returns>
/// True if successfully added, false otherwise
/// </returns>
bool insert ( int newItem )
{
  int h = newItem % size;

  for ( int step = 1; A[h] != EMPTY; step++ ) {
    // Check for a duplicate (if not allowed)
    if ( newItem == A[h] )
      return false;

    // Quadratic step to the next slot
    h = ( h + ( step * step - step ) / 2 ) % size;
  }

  // Insert the new item
  A[h] = newItem;
  ++load;

  return true;
}

I changed NULL to EMPTY in the slot check, because your items are integers, and NULL should only be used in a pointer context. Presumably 0 is a valid item, so that's also likely to be a bug in your implementation.