为什么在将大整数插入我的自定义哈希 table 时出现段错误？

Question

我自己对代码进行了一些测试。有谁知道如何消除当我在下面的列表中插入大量非常大的无符号整数时引起的分段错误？当整数很小时它不会抛出段错误（我知道当我在 main 中创建的 for 循环中不将 743677 添加到 num 时程序工作正常。）

我很确定我的 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;
}

Answer 1

运行用 g++ -g -fsanitize=address 编译的程序显示堆溢出：

Inserting into trivial hash table...
=================================================================
==82429==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x7fae929a0808 at pc 0x559f40dfe0b9 bp 0x7ffe20f84330 sp 0x7ffe20f84328
READ of size 8 at 0x7fae929a0808 thread T0 ()
    #0 0x559f40dfe0b8 in std::_Fwd_list_node_base* std::_Fwd_list_base<unsigned long, std::allocator<unsigned long> >::_M_insert_after<unsigned long const&>(std::_Fwd_list_const_iterator<unsigned long>, unsigned long const&) /usr/include/c++/9/bits/forward_list.tcc:56
    #1 0x559f40dfddb7 in std::forward_list<unsigned long, std::allocator<unsigned long> >::push_front(unsigned long const&) /usr/include/c++/9/bits/forward_list.h:852
    #2 0x559f40dfd4ca in TrivialHashTable::insert(unsigned long) /tmp/t.cc:48
    #3 0x559f40dfd696 in main /tmp/t.cc:79
    #4 0x7fae9556abba in __libc_start_main ../csu/libc-start.c:308
    #5 0x559f40dfd209 in _start (/tmp/a.out+0x2209)

0x7fae929a0808 is located 0 bytes to the right of 131080-byte region [0x7fae92980800,0x7fae929a0808)
allocated by thread T750847 () here:
    #0 0x7fae95b3836f in operator new[](unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.5+0x10936f)
    #1 0x559f40dfd97e in TrivialHashTable::TrivialHashTable(unsigned int) /tmp/t.cc:37
    #2 0x559f40dfd5f2 in main /tmp/t.cc:75
    #3 0x7fae9556abba in __libc_start_main ../csu/libc-start.c:308

您似乎遇到了差一错误：崩溃点：

#7  0x00005555555564cb in TrivialHashTable::insert (this=0x604000000010, val=770048) at t.cc:48
48              lists[hashVal].push_front(val);
(gdb) p hashVal
 = 16384
(gdb) p numTotalLists
 = 16384

为什么在将大整数插入我的自定义哈希 table 时出现段错误？

Why am I getting a seg-fault when inserting large integers into my custom hash table?

c++

segmentation-fault

data-structures