哈希表二次探测碰撞次数与预期不符问题排查求助

问题描述 #

实现了包含线性探测和二次探测的哈希表程序，线性探测功能正常，但二次探测的碰撞次数始终与预期值不一致。

预期输出 #

Linear:
Hash table size: 8087
Number of collisions with a = 33: 6240629
Hash table size: 8087
Number of collisions with a = 37: 4817906
Hash table size: 8087
Number of collisions with a = 39: 6686453
Hash table size: 8087
Number of collisions with a = 41: 7423747
Quadratic:
Hash table size: 8087
Number of collisions with a = 33: 1145326
Hash table size: 8087
Number of collisions with a = 37: 1182048
Hash table size: 8087
Number of collisions with a = 39: 1127766
Hash table size: 8087
Number of collisions with a = 41: 1152208

实际输出 #

Hash table size : 8087
Number of collisions with a = 33: 1134428

Hash table size : 8087
Number of collisions with a = 37: 1166882

Hash table size : 8087
Number of collisions with a = 39: 1184105

Hash table size : 8087
Number of collisions with a = 41: 1159074

代码文件 #

main.cpp #

#include <iostream>
#include <fstream>
#include <string>
#include <cctype>
#include <sstream>
#include "HashType - Copy.h"

using namespace std;

void buildHashTable(ifstream &inFile,
                    HashType<string> &hashTable,
                    int type,
                    int Prime)
{
    string word;
    int length;
    if (inFile.is_open())
    {
        while (inFile >> word)
        {
            length = word.size();
            
            for (int i = 0; i < length;)
            {
                unsigned char ch = word[i]; // Cast to unsigned char to handle characters safely
                if (ch < ' ' || ispunct(ch))
                { // Check for control characters and punctuation
                    word.erase(i, 1);
                    length = word.length(); // Update length after modifying the string
                }
                else
                {
                    ++i; // Only increment if no deletion was made
                }
            }
            if (type == 1)
            {
                hashTable.InsertItemLinear(word, Prime);
            }
            
            if (type == 0)
            {
                hashTable.InsertItemQuadratic(word, Prime);
            }
            
        }
    }
    
    cout << "\n" << "Hash table size : " << hashTable.GetSize() << endl;
    cout << "Number of collisions with a = " << Prime << ": "
            << hashTable.GetCollisions() << endl;
    hashTable.MakeEmpty();
    hashTable.resetCollisions();
    
}

int main()
{
    for (int b : { 33, 37, 39, 41 })
    {
        ifstream inFile("hashText1.txt");
        if (!inFile)
        {
            cerr << "Error opening file." << endl;
            return 1;
        }
        
        int primeSize;
        
        string line;
        
        if (getline(inFile, line))
        {
            stringstream ss(line);
            ss >> primeSize;
        }
        
        HashType<string> hashTable(primeSize);
        
        buildHashTable(inFile, hashTable, 0, b);
        
    }
    
    return 0;
}

HashType - Copy.h #

#ifndef HASHTYPE_H
#define HASHTYPE_H
// File ItemType.h must be provided by the user of this class. 
//  ItemType.h must contain the following definitions: 
//  MAX_ITEMS:     the maximum number of items on the list 
//  ItemType:      generic data type

#include <string>
#include <cmath>
#include <iostream>
#include <bitset>
#include <vector>

const int MAX_ITEMS = 5;
using namespace std;

template<class ItemType>
class HashType
{
public:
    HashType();
// Constructor
    HashType(int s);
//Dynamic size constructor
    void SetHashType(bool flag);
    void MakeEmpty();
// Function: Returns the list to the empty state.
// Post:  List is empty.
    bool IsFull() const;
// Function:  Determines whether list is full.
// Pre:  List has been initialized.
// Post: Function value = (list is full)
    int GetNumItems() const;
// Function: Determines the number of elements in list.
// Pre:  List has been initialized.
// Post: Function value = number of elements in list
    void RetrieveItem(ItemType item, bool &found);
// Function: Retrieves list element whose key matches item's key (if
//           present).
// Pre:  List has been initialized.
//       Key member of item is initialized.
// Post: If there is an element someItem whose value matches
//       item's value, then found = true and item contains the contents of
//       the item if it is found.
//      otherwise found = false and item is returned unchanged.
//       List is unchanged.
    void Insert(ItemType item);
// Function: Adds item to list and uses a linear probing technique to
// resolve collisions.  If the flag is true, a random hash method will be used.
//If the flag is false, the division method will be used.
// Pre:  List has been initialized.
//       List is not full.
//       item is not in list.
// Post: item is in list.
    void DeleteItem(ItemType item);
// Function: Deletes the element whose key matches item's key.
// Pre:  List has been initialized.
//       Key member of item is initialized.
//       One and only one element in list has a key matching item's key.
// Post: No element in list has a key matching item's key.
    int Hash(ItemType item, int a) const;
//This is the hash function for this class. If the flag is true, a random hash method will be used.
//If the flag is false, the division method will be used.
    
    unsigned long int GetCollisions() const;
//return the number of collisions that occured during the build of the hash table
    template<class Item>
    friend ostream& operator<<(ostream &out, const HashType<Item> &items);

    void InsertItemLinear(ItemType Item, int Prime);

    void InsertItemQuadratic(ItemType Item, int Prime);

    int GetSize();

    void resetCollisions();

private:
    bool hashType; //false is division method, true is a random folding method. default is false.
    unsigned long int numCollisions;
    int numItems;
    int size;
    ItemType *info;
    ItemType emptyItem = "";
};

template<class ItemType>
void HashType<ItemType>::resetCollisions()
{
    numCollisions = 0;
}

template<class ItemType>
int HashType<ItemType>::GetSize()
{
    return size;
}

template<class ItemType>
void HashType<ItemType>::SetHashType(bool flag)
{
    hashType = flag;
}

template<class ItemType>
HashType<ItemType>::HashType()
{
    hashType = false;
    numCollisions = 0;
    numItems = 0;
    size = MAX_ITEMS;
    info = new int[size];
    for (int i = 0; i < size; i++)
        info[i] = emptyItem;
}

template<class ItemType>
HashType<ItemType>::HashType(int s)
{
    hashType = false;
    numItems = 0;
    numCollisions = 0;
    size = s;
    info = new ItemType[size];
    for (int i = 0; i < size; i++)
    {
        info[i] = emptyItem;
    }
}

template<class ItemType>
bool HashType<ItemType>::IsFull() const
{
    return (numItems == size);
}

template<class ItemType>
int HashType<ItemType>::GetNumItems() const
{
    return numItems;
}

template<class ItemType>
void HashType<ItemType>::MakeEmpty()
// Post: list is empty.
{
    numItems = 0;
    for (int i = 0; i < size; i++)
        info[i] = emptyItem;
}

//Updated IT via Dale 1/31/2019
template<class ItemType>
void HashType<ItemType>::DeleteItem(ItemType item)
{
    int location = 0;
    int startLoc;
    
    startLoc = Hash(item);
    location = startLoc;
    do
    {
        if (info[location] == item || info[location] == emptyItem)
        {
            info[location] = -1;
            numItems--;
            return;
        }
        else
            location = (location + 1) % size;
    } while (location != startLoc);
    
    if (location == startLoc)
    {
        cout << "Item to delete not found." << endl;
    }
}

template<class ItemType>
int HashType<ItemType>::Hash(ItemType item, int a) const
// Post: Returns an integer between 0 and MAX_ITEMS -1.
{
//Complete code here
    int hash = 0;
    int n = item.length();
    for (int i = 0; i < n; i++)
        hash = a * hash + item.at(i);
    return abs(hash % size);
    
    return 0;
}

template<class ItemType>
unsigned long int HashType<ItemType>::GetCollisions() const
{
    return numCollisions;
}

template<class ItemType>
void HashType<ItemType>::Insert(ItemType item)
// Post: item is stored in the array at position item.Hash()
//       or the next free spot.
{
    if (numItems / size > 0.70)
    {
//rehash//resize
    }
    int location;
    location = Hash(item);
    
    info[location] = item;
    numItems++;
}

template<class ItemType>
void HashType<ItemType>::RetrieveItem(ItemType item, bool &found)
{
    int location;
    int startLoc;
    bool moreToSearch = true;
    
    startLoc = Hash(item);
    location = startLoc;
    do
    {
        if (info[location] == item || info[location] == emptyItem)
            moreToSearch = false;
        else
            location = (location + 1) % size;
    } while (location != startLoc && moreToSearch);
    found = (info[location] == item);
    if (found)
        item = info[location];
}

template<class Item>
ostream& operator<<(ostream &out, const HashType<Item> &items)
{
    out << "[ ";
    for (int i = 0; i < items.numItems; i++)
    {
        if (i == 0)
            out << items.info[i];
        else
            out << ", " << items.info[i];
    }
    out << " ]" << endl;
    return out;
}

#endif

问题分析与修复方案 #

核心问题1：二次探测插入函数未实现 #

在提供的HashType - Copy.h中，仅声明了InsertItemQuadratic函数，但没有编写具体实现逻辑，同时InsertItemLinear函数也未实现，这会导致程序行为异常（可能触发链接错误或调用未定义行为）。

核心问题2：二次探测的碰撞计数与探测逻辑错误 #

假设你之前有未完善的二次探测实现，常见错误点包括：

• 探测步长计算错误：二次探测的标准步长应为i²或i + i²（i为探测次数），需确保步长计算正确且在哈希表范围内取模。
• 碰撞计数逻辑错误：每次尝试插入时，若当前位置已被占用，需递增numCollisions，直到找到空位置。
• 哈希表填满判断：二次探测需要确保哈希表大小为质数且装填因子不超过0.5，否则可能无法找到空位置。

修复后的InsertItemLinear和InsertItemQuadratic实现 #

在HashType - Copy.h末尾添加以下实现：

// 线性探测插入实现
template<class ItemType>
void HashType<ItemType>::InsertItemLinear(ItemType item, int Prime)
{
    if (IsFull()) {
        cerr << "Hash table is full." << endl;
        return;
    }
    int startLoc = Hash(item, Prime);
    int location = startLoc;
    // 寻找空位置
    while (info[location] != emptyItem) {
        numCollisions++;
        location = (location + 1) % size;
        // 防止死循环（理论上不会触发，因为已判断IsFull）
        if (location == startLoc) {
            cerr << "No empty slot found." << endl;
            return;
        }
    }
    info[location] = item;
    numItems++;
}

// 二次探测插入实现
template<class ItemType>
void HashType<ItemType>::InsertItemQuadratic(ItemType item, int Prime)
{
    if (IsFull()) {
        cerr << "Hash table is full." << endl;
        return;
    }
    int startLoc = Hash(item, Prime);
    int location = startLoc;
    int i = 1;
    // 寻找空位置，步长为i²
    while (info[location] != emptyItem) {
        numCollisions++;
        // 二次探测公式：(startLoc + i*i) % size
        location = (startLoc + i * i) % size;
        // 处理负数情况（如果哈希值为负）
        if (location < 0) location += size;
        i++;
        // 若探测次数超过表大小，说明无法找到空位置
        if (i > size) {
            cerr << "No empty slot found." << endl;
            return;
        }
    }
    info[location] = item;
    numItems++;
}

额外注意事项 #

• 哈希表装填因子：二次探测的装填因子应控制在0.5以内，否则会出现无法找到空位置的情况。可以在插入时判断numItems * 2 > size时触发扩容。
• 哈希函数的溢出问题：当前哈希函数中hash = a * hash + item.at(i)可能导致整数溢出，建议使用unsigned long类型存储哈希值避免溢出：

template<class ItemType>
int HashType<ItemType>::Hash(ItemType item, int a) const
{
    unsigned long hash = 0;
    int n = item.length();
    for (int i = 0; i < n; i++)
        hash = (unsigned long)a * hash + item.at(i);
    return hash % size;
}

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