C++：HASHと衝突技術の適切な使用

Question

ハッシュテーブルの大きさの大きさには制限がありますか？

ハッシュテーブルのサイズが小さすぎて問題が発生するのはなぜか分かりませんが、ハッシュテーブルが大きすぎると、プローブがSigエラーを投げてしまうように見えますか？誰かがハッシュテーブルの経験があるなら、私のコードはここにあります。私は確かに（してください、代わりに編み物を取っ超えて）あなたが提供しなければならない何かアドバイスに感謝：

#include <iostream> 
#include <stdlib.h> 
#include <stdio.h> 
#include <time.h> 
#include <math.h> 

using namespace std; 

struct TABLE{ 
    int key; 
    TABLE* next; 
}; 
const int MAX_KEYS = 5000; 
const int RANDOM = 30000; 

int randNUMS(int *rand); 
int hashTableSize(); 
int HASH(int key,int listSIZE); 
void threeHashMethods(int *randARRAY,int tbSIZE); 
int* openAddressing(int *randARRAY,int tbSIZE); 
int seperateCHAINING(); 
int linearPROBE(int address,int *HASH,int probeTHIS,int load,int& probe); 
int doubleHASH(int key,int tbSIZE); 
void listSEARCH(int *randARRAY,int *HT,int tbSIZE); 

int main(){ 
    int tbSIZE = 0; 
    int randARRAY[MAX_KEYS]; 
    for(int a = 0; a <= MAX_KEYS; a++){ 
    randARRAY[a] = 0; 
    } 

    ///create random array of 5,000 unique int 
    ///they will be of values between 1-30000 
    randNUMS(randARRAY); 
    ///get hash table size from user 
    ///table must be larger than 6500 int 
    tbSIZE = hashTableSize(); 
    ///driver function for all three 
    ///collision resolution techniques 
    threeHashMethods(randARRAY,tbSIZE); 

    return 0; 
} 
int HASH(int key,int listSIZE){ 
    int address = 0; 
    address = key % listSIZE; 
    return address; 
} 
int doubleHASH(int key,int tbSIZE){ 
    int address = 0; 
    address = (key % (tbSIZE - 2)) + 1; 
    return address; 
} 
int hashTableSize(){ 
    int userCHOOSE = 0; 

    cout << "Enter desired hash table size." << endl; 
    cout << "NOTE: hash table size must exceed 6500: " << endl; 
    cin >> userCHOOSE; 
    if(userCHOOSE < 6500){ 
    cout << "Whoops " << userCHOOSE << " is to small!" << endl; 
    hashTableSize(); 
    } 
    return userCHOOSE; 
} 
int randNUMS(int *randARRAY){ 
    ///temporary fix for randARRAY array of numbers till hash is running 
    int check = 0; 
    int index = 0; 
    int loop = 0; 

    srand (time(NULL)); 
    for(index = 0; index < MAX_KEYS; index++){ 
    check = rand() % RANDOM + 1; 
    while(randARRAY[loop] != 0){ 
     if(check == randARRAY[index]){ 
    check = rand() % RANDOM + 1; 
    loop = 0; 
     } 
     loop++; 
    } 
    randARRAY[index] = check; 
    } 

    return *randARRAY; 
} 
void threeHashMethods(int *randARRAY,int tbSIZE){ 
    int *HT; 


    ///this menu will allow user to select collision method 
    HT = openAddressing(randARRAY,tbSIZE); 
    listSEARCH(randARRAY,HT,tbSIZE); 
} 
int* openAddressing(int *randARRAY,int tbSIZE){ 
    int key = 0, 
    address = 0, 
    prb = 0, 
    hashTABLE[tbSIZE * 2], 
    *HT = hashTABLE; 
    int percent = (5000.00/tbSIZE) * 100; 
    int load = (5000.00/tbSIZE) * 10; 
    int loadFACTOR = (tbSIZE * load)/10; 

    if(percent > 0){ 

    for(int a = 0; a < tbSIZE; a++){ 

    hashTABLE[a] = 0; 
    } 

    while(randARRAY[key] != 0){ 
    ///get a purposed address 
    ///and move through indexes 
    ///in array of random int till 
    ///empty index is found 
    if(randARRAY[key] > tbSIZE){ 
    address = HASH(randARRAY[key],loadFACTOR); 
    } 
    ///if address is available 
    ///grab the key 
    if(hashTABLE[address] == 0){ 
     hashTABLE[address] = randARRAY[key]; 
    } 
    ///if a collision is the result run 
    ///a linear probe until available address is found 
    else{ 
     address = linearPROBE(address,hashTABLE,0,tbSIZE,prb); 
     hashTABLE[address] = randARRAY[key]; 
    } 
    if(hashTABLE[address] == randARRAY[key]){ 
    key++; 
    } 
    } 
    cout << key << " items loaded into a " << tbSIZE << " element hash table." << endl; 
    cout << "Load Factor = " << percent << "%" << endl; 
    cout << "Results from searching for 2500 items." << endl; 
    } 
    else{ 
    cout << "Load Factor is maxed out." << endl; 
    } 

    return HT; 
} 
int linearPROBE(int address,int *HASH,int probeTHIS,int load,int& probe){ 
    while(HASH[address] != probeTHIS){ 
    address = (address + 1); 
    probe++; 
    if(address >= load){ 
     address = 0; 
    } 
    } 
    return address; 
} 
void listSEARCH(int *randARRAY,int *HT,int tbSIZE){ 
    int key = 0, 
    address = 0, 
    probe = 0, 
    found = 0, 
    attempts = 0; 

    while(randARRAY[key] != 0){ 
    address = HASH(randARRAY[key],tbSIZE); 
    while(HT[address] != randARRAY[key] && attempts < tbSIZE){ 
     address = linearPROBE(address,HT,randARRAY[key],tbSIZE,probe); 
     found++; 
     attempts++; 
    } 
    key = key + 2; 
    attempts = 0; 
    } 
    found = probe/found; 

    cout << "Linear Probing." << endl; 
    cout << probe << " items examined "; 
    cout << "(avg = " << found << " items examined per search.)" << endl; 
} 

Answer 1

ずつオフ。これは、randARRAYの最初のMAX_KEYS + 1要素を塗りつぶします。

for(int a = 0; a <= MAX_KEYS; a++){ 
    randARRAY[a] = 0; 
    } 

これは、以前のuserCHOOSE値を再度使用するかどうかを確認します。あなたはその後、本当の問題return hashTableSize();

if(userCHOOSE < 6500){ 
    cout << "Whoops " << userCHOOSE << " is to small!" << endl; 
    hashTableSize(); 
    } 

たい：openAddressingでは、randARRAY[key] != 0ながらスキャンします。あなたのrandARRAYは0で終了していません（メインのtbSIZEを設定すると、以前のoff-by-oneのrandARRAY [5000]が上書きされます）。次に、listSearchで、5000より大きいキーのrandARRAY [key]にアクセスします。これは、あなたが "ガベージ"データを読み込んでいることを意味します。負の数です。それをハッシュ（モジュラス）し、それは負のままです。その後、HT [負の値]にアクセスしてクラッシュします。

EDIT：修正：

int randARRAY[MAX_KEYS+1]; 

これは、オフずつを防ぐため、あなたの0で終了するスキャン作業を行い、正しい値5000