C++二次探测哈希表碰撞计数过高问题排查求助

数据老陈

2026-7-4

哈希表碰撞计数异常问题

正在完成一项哈希表相关作业，哈希表基础函数已提供，需实现重哈希大小统计、负载因子计算、碰撞计数器及拼写检查功能。目前除碰撞计数器外其余功能均已完成，但碰撞计数结果远高于预期值（预期42802，实际得到55535）。怀疑是哈希表采用的懒删除机制处理不当导致，但不确定具体原因。

相关代码

QuadraticProbing.cpp

#ifndef QUADRATIC_PROBING_CPP
#define QUADRATIC_PROBING_CPP

#include <iostream>
#include "QuadraticProbing.h"
using namespace std;


template <class HashedObj>
HashTable<HashedObj>::HashTable( int size )
  : array( nextPrime( size ) )
{
  makeEmpty();
}

template <class HashedObj>
void HashTable<HashedObj>::makeEmpty( )
{
  
  currentSize = 0;
  for( int i = 0; i < array.size( ); i++ )
    {
      array[ i ].info = EMPTY;
    }
}

template<class HashedObj>
double HashTable<HashedObj>::loadFactor() const{
  return static_cast<double>(currentSize) / array.size();
}

template <class HashedObj>
bool HashTable<HashedObj>::isPrime( int n )
{
    if( n == 2 || n == 3 )
        return true;

    if( n == 1 || n % 2 == 0 )
        return false;

    for( int i = 3; i * i <= n; i += 2 )
        if( n % i == 0 )
            return false;

    return true;
}

template <class HashedObj>
int HashTable<HashedObj>::nextPrime( int n )
{
    if( n % 2 == 0 )
        n++;

    for( ; !isPrime( n ); n += 2 )
        ;

    return n;
}


template <class HashedObj>
bool HashTable<HashedObj>::contains( const HashedObj & x ) const
{
  return isActive( findPos( x ) );
}


template <class HashedObj>
bool HashTable<HashedObj>::insert( const HashedObj & x, int &rehashCounter, int &sizeIncrease, int &collisionCount)
{
  
  // Insert x as active
  int currentPos = findPos( x );
  if( isActive( currentPos ) )
    return false;
  
  array[ currentPos ].element = x;
  array[ currentPos ].info = ACTIVE;

  // Rehash
  if( ++currentSize > array.size( ) / 2 ){
    
    int oldSize = array.size();
    vector<HashEntry> oldArray = array;
    rehash(rehashCounter, sizeIncrease, collisionCount);
    int newSize = array.size();

    for (int i = 0; i < oldSize; i++){
    int newPos = findPos(oldArray[i].element);
    if (oldArray[i].info == ACTIVE && newPos != currentPos) {
        // Check if the element from the old array collided with a different element
        collisionCount++;
    }
  }
    sizeIncrease += newSize - oldSize;
    cout << "Rehashing. New size is " << sizeIncrease << endl;
  }

  return true;
}

template <class HashedObj>
bool HashTable<HashedObj>::remove( const HashedObj & x )
{
  int currentPos = findPos( x );
  if( !isActive( currentPos ) )
    return false;
  
  array[ currentPos ].info = DELETED;
  return true;
}


template <class HashedObj>
bool HashTable<HashedObj>::isActive( int currentPos ) const
{
  return array[ currentPos ].info == ACTIVE;
}

template <class HashedObj>
int HashTable<HashedObj>::findPos( const HashedObj & x ) const
{
  int offset = 1;
  int currentPos = myhash( x );

  while( array[ currentPos ].info != EMPTY &&
     array[ currentPos ].element != x )
    {
      currentPos += offset;  // Compute ith probe
      offset += 2;
      if( currentPos >= array.size( ) )
    currentPos -= array.size( );
    }

  return currentPos;
}

template <class HashedObj>
void HashTable<HashedObj>::rehash(int &counter, int &sizeIncrease, int &collisionCount)
{
  
  vector<HashEntry> oldArray = array;
  int oldSize = array.size();

  // Create new double-sized, empty table
  array.resize( nextPrime( 2 * oldArray.size( ) ) );
  for( int j = 0; j < array.size( ); j++ )
    array[ j ].info = EMPTY;
  
  
  // Copy table over
  currentSize = 0;
  for( int i = 0; i < oldArray.size( ); i++ )
    if( oldArray[ i ].info == ACTIVE )
      insert(oldArray[ i ].element, counter, sizeIncrease, collisionCount);
}



template <class HashedObj>
int HashTable<HashedObj>::myhash( const HashedObj & x ) const
{
  int hashVal= hashKey(x); 
  
  hashVal %= array.size( );
  if( hashVal < 0 )
    hashVal += array.size( );
  
  return hashVal;
}

template <class HashedObj>
int HashTable<HashedObj>::hashKey( int key) const
{
  return key;
}

template <class HashedObj>
int HashTable<HashedObj>::hashKey(const string & key) const
{
  int hashVal = 0;

  for( int i = 0; i < key.length( ); i++ )
    hashVal = 37 * hashVal + key[ i ];
  
  return hashVal;
  
}


#endif

QuadraticProbing.h

#ifndef QUADRATIC_PROBING_H
#define QUADRATIC_PROBING_H

#include <vector>
#include <string>
using namespace std;



enum EntryType { ACTIVE, EMPTY, DELETED };

// QuadraticProbing Hash table class
//
// CONSTRUCTION: an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// bool insert( x )       --> Insert x
// bool remove( x )       --> Remove x
// bool contains( x )     --> Return true if x is present
// void makeEmpty( )      --> Remove all items
// int hash( string str ) --> Global method to hash strings

template <class HashedObj>
class HashTable
{
public:

  //constuctor, default size: 101
  HashTable(int size = 101);

  //Return true if x is present
  bool contains( const HashedObj & x ) const;

  //Remove all items from the hash table
  void makeEmpty( );
    
  //insert x
  bool insert( const HashedObj & x, int &rehashCounter, int &sizeIncrease, int &collisionCount);

  //remove x
  bool remove( const HashedObj & x );

  double loadFactor() const;

  
private:
  //hash table entry
  struct HashEntry
  {
    HashedObj element;
    EntryType info;
  };


  //hash table
  vector<HashEntry> array;

  //size of the hash table
  int currentSize;

  int collisionCount;

  //check to see if the given position is active
  bool isActive( int currentPos ) const;

  //find the position of given x
  int findPos( const HashedObj & x ) const;

  //rehash
  void rehash(int &counter, int &sizeIncrease, int &collisionCount);

  //return the hash table index of x
  int myhash( const HashedObj & x ) const;

  //find the next prime greater than n
  int nextPrime( int n );

  //check if n is prime
  bool isPrime( int n );

  //compute the hash key when x is integer
  int hashKey(int key) const;

  //compute the hash key when x is a string
  int hashKey(const string & key) const;

  
};

#include "QuadraticProbing.cpp"

#endif

main.cpp

#include <iostream>
#include <iomanip>
#include "QuadraticProbing.h"
#include <string>
#include <fstream>
using namespace std;

// Simple main
int main( )
{
  std::cout << std::setprecision(2);
  int rehashCount = 0;
  int sizeIncrease = 101;
  int collisionCount = 0;
  int wordLength;
  string word, wordOriginal;
  bool check1 = false;
  bool check2 = false;
  bool check3 = false;
  vector<string> s;
  HashTable<string> table3;
  char alpha[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
                'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
  string myText;
  char c = 0;

  cout << "Insert words\n";
  std::ifstream myReadFile("words.dat");
  while(std::getline(myReadFile, myText)){
    table3.insert(myText, rehashCount, sizeIncrease, collisionCount);
  }

  cout << "\nThe load factor is " << table3.loadFactor() << "." << endl;
  cout << "Collision count: " << collisionCount << endl;

  
  
  for (char &c : word) { //Convert to lowercase for search
    c = tolower(c);
  }

  while(true){

  s.clear();

  cout << "\nEnter a word for spell checking (enter done to exit):  ";
  cin >> word;

  if(word.find("done") != std::string::npos){
    break;
  }
  
  if(table3.contains(word))
  {
    cout << "Correct! " << endl;
    break;
  }
    //logic when word not found, and word is just missing character
    wordLength = word.length();

    wordOriginal = word;
    for(int j = 0; j < 25; j++){

      word = wordOriginal;

      word.insert(0, 1, alpha[j]);

      for (int i = 0; i < wordLength; i++){

        c = word[i];
        word[i] = word[i + 1];
        word[i + 1]= c;
        if(table3.contains(word)){
          s.push_back(word);
          break;
        } 
      }
  }
  
    //logic for when word not found, and word has extra character
    word = wordOriginal;
    for(int i = 0; i < wordLength; i++){
      word = word.erase(i, 1);
      if(table3.contains(word)){
        s.push_back(word);
        
      }
      word = wordOriginal;
      
    }
  
  
    word = wordOriginal;
    int counter = 0;
  
  for(int i = 0; i < wordLength; i++){
    word = wordOriginal;
    
    for(int j=0; j < 25; j++){
      word = word.replace(i, 1, 1, alpha[j]);
      if(table3.contains(word)){
        
        s.push_back(word);
        
      }
    }
  }
  cout << "Suggestions: \n";
  for (const auto& element : s){
    cout << element << " ";
  }

  

  }
  cout << "Bye. ";
  
}

问题分析与解决方案

核心错误点

insert函数中rehash后的错误碰撞统计
在insert函数的rehash分支里，这段代码完全不符合碰撞计数的逻辑：

for (int i = 0; i < oldSize; i++){
    int newPos = findPos(oldArray[i].element);
    if (oldArray[i].info == ACTIVE && newPos != currentPos) {
        collisionCount++;
    }
}

这里的currentPos是当前插入元素在旧表中的位置，和旧数组元素在新表中的位置newPos没有关联，这段代码会错误地将所有旧元素在新表的位置与当前元素旧位置不同的情况都算作碰撞，导致大量无效计数，这是碰撞数远超预期的主要原因。

碰撞计数逻辑缺失
原代码没有在元素插入时的探测过程中正确统计碰撞，仅靠上述错误代码计数，导致计数逻辑完全错误。

修复步骤

步骤1：移除错误的碰撞统计代码

直接删除insert函数中rehash后的那段循环统计代码，避免无效计数。

步骤2：在findPos中正确统计碰撞

修改findPos函数，添加可选参数来统计探测过程中的碰撞次数（每次探测代表一次碰撞）：

template <class HashedObj>
int HashTable<HashedObj>::findPos( const HashedObj & x, int* collisionCount = nullptr ) const
{
  int offset = 1;
  int currentPos = myhash( x );

  while( array[ currentPos ].info != EMPTY &&
     array[ currentPos ].element != x )
    {
      // 每次进入循环说明需要探测，碰撞计数+1
      if (collisionCount != nullptr) {
          (*collisionCount)++;
      }
      currentPos += offset;
      offset += 2;
      if( currentPos >= array.size( ) )
          currentPos -= array.size( );
    }

  return currentPos;
}

步骤3：修改insert函数调用findPos时传入碰撞计数器

在insert函数中调用findPos时，传入collisionCount的地址：

int currentPos = findPos( x, &collisionCount );

步骤4：修改contains函数的findPos调用

contains函数不需要统计碰撞，直接调用无参数的findPos(x)即可，因为我们给参数设置了默认值nullptr，所以无需修改contains的代码。

修复后效果

完成上述修改后，碰撞计数会准确统计元素插入时因哈希冲突需要探测的次数，同时避免了错误的重复计数，结果会接近预期的42802。

内容的提问来源于stack exchange，提问作者imnapr

C++二次探测哈希表碰撞计数过高问题排查求助

相关代码 #

QuadraticProbing.cpp #

QuadraticProbing.h #

main.cpp #

问题分析与解决方案 #

核心错误点 #

修复步骤 #