Я провел некоторое тестирование своего кода самостоятельно. Кто-нибудь знает, как избавиться от ошибок сегментации, вызванных, когда я вставляю тонну очень больших целых чисел без знака в мои списки ниже? Он не выдает ошибку сегмента, когда целые числа маленькие (я знаю, что программа работает нормально, когда я не добавляю 743677 к num в for-l oop, который я сделал в main.)
Я почти уверен, что мои forward_lists фактически не распределяются или не распределяются динамически. В моем отладчике размер lists равен нулю после выделения.
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <cstdint>
#include <forward_list>
#include <cmath>
using namespace std;
class HashTable {
protected:
uint32_t numTotalLists;
uint64_t hashVal;
virtual uint64_t hash(uint64_t) = 0;
public:
HashTable();
virtual ~HashTable() = default;
virtual void insert(uint64_t) = 0;
};
HashTable::HashTable() {
numTotalLists = 0;
hashVal = 0;
}
class TrivialHashTable : public HashTable {
private:
uint64_t hash(uint64_t) override;
uint32_t roundUpBaseTwo(uint32_t);
forward_list<uint64_t> * lists;
short numBitsToMask;
public:
explicit TrivialHashTable(uint32_t numIntegers) : HashTable() {
//Trivial hash algorithm uses a table size that is a power of two.
numTotalLists = numIntegers;
numTotalLists = roundUpBaseTwo(numTotalLists);
lists = new forward_list<uint64_t> [numTotalLists]; //Is this legal?
numBitsToMask = log2(numTotalLists);
}
~TrivialHashTable() override {
delete [] lists;
}
void insert(uint64_t) override;
};
void TrivialHashTable::insert(uint64_t val) {
hashVal = hash(val);
lists[hashVal].push_front(val);
}
//Trivial Hash Algorithm: mask bottom log2(tableSize) bits out of val
uint64_t TrivialHashTable::hash(uint64_t val) {
uint64_t mask = 1;
for (short i = 0; i < numBitsToMask; i++) {
mask = mask << 1;
mask += 1;
}
val &= mask;
return val;
}
//Function accepts a number, then rounds it up to the nearest number that is a power of two.
uint32_t TrivialHashTable::roundUpBaseTwo(uint32_t num) {
num--;
num |= num >> 1;
num |= num >> 2;
num |= num >> 4;
num |= num >> 8;
num |= num >> 16;
num++;
return num;
}
int main() {
HashTable * hashTableTrivial = new TrivialHashTable(10000);
cout << "Inserting into trivial hash table..." << endl;
for (uint64_t num = 0; num < 1000000; num++) {
hashTableTrivial->insert(num + 743677);
}
cout << "Inserted all data into trivial hash table." << endl;
return 0;
}