哈希 Table - 条件跳转或移动取决于未初始化的值

Question

我正在为我的类之一使用双向链表编写哈希表，但是当我运行 valgrind 时我运行遇到错误。它说：有条件的跳跃或移动取决于未初始化的值。当我运行 --track-origins=yes 时，它说：

==11453== Conditional jump or move depends on uninitialised value(s)
==11453==    at 0x402904: LinkedList<std::string>::itemExists(std::string const&) (LinkedList.h:89)
==11453==    by 0x401FE6: HashSet<std::string>::find(std::string const&) (HashSet.h:85)
==11453==    by 0x401E42: HashSet<std::string>::add(std::string const&) (HashSet.h:39)
==11453==    by 0x4019D7: insert(std::string, std::basic_ifstream<char, std::char_traits<char> >&, std::basic_ofstream<char, std::char_traits<char> >&, std::string, HashSet<std::string>&) (main.cpp:64)
==11453==    by 0x4015B1: main (main.cpp:34)
==11453==  Uninitialised value was created by a heap allocation
==11453==    at 0x4C2B800: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==11453==    by 0x4024D8: HashSet<std::string>::rehash() (HashSet.h:131)
==11453==    by 0x401E69: HashSet<std::string>::add(std::string const&) (HashSet.h:45)
==11453==    by 0x4019D7: insert(std::string, std::basic_ifstream<char, std::char_traits<char> >&, std::basic_ofstream<char, std::char_traits<char> >&, std::string, HashSet<std::string>&) (main.cpp:64)
==11453==    by 0x4015B1: main (main.cpp:34)

所以我认为问题出在我的重新散列函数中，但我不知道它在哪里。你们能帮帮我吗？这是我的重新哈希函数：

void rehash()
{
    int old_size = tableSize;
    if (tableSize == itemsStored) {
        tableSize = tableSize * 2 + 1;
    }

    else if (itemsStored <= tableSize/2) {
        tableSize = tableSize / 2;
    }
        LinkedList<string>* newTable = new LinkedList<string>[tableSize];    -------> line 131
        for (int i = 0; i < old_size; ++i)
        {
            int table_size = 0;
            table_size = table[i].getSize();
            if(table_size != 0) {
                for (int j = 0; j < table_size; ++j) {
                        unsigned index = hashFunction(table[i].getItem(j)) % tableSize;
                        newTable[index].insert(newTable[index].getSize(), table->getItem(i));

                }
            }
        }
        LinkedList<string>* temp = table;
        table = newTable;
        delete [] temp;

}

这是我的哈希集构造函数：

HashSet()
{
    int tableSize = 0;
    table = new LinkedList<string>[tableSize];
}

这是我的 LinkedList 的构造函数：

LinkedList()
{
    size = 0;
}

谢谢！

Answer 1

我要在这里做个幸运的猜测：你的 LinkedList 包含一个 head 指针，你的 itemExists 函数在检查 size 之前加载该指针字段大于零。

类似

Node* node = head;
for (size_t i = 0; i < size; i++)
{
    if (node->hash == ...)
    ...
    node = node->next;
}

看起来无辜，因为如果 size == 0 指针没有被取消引用，但读取未初始化的指针本身就是 UB。

Answer 2

天哪，这很难发现。如果这不是@PaulGroke 已经建议的，那么这里还有一个潜在的问题：

HashSet()
{
    /* */int/* */ tableSize = 0; // HERE!
    table = new LinkedList<string>[tableSize];
}

根据您的 rehash 成员函数，我猜测您的散列集 class 有一个名为 tableSize 的成员。上面的构造函数有一个与 shadows 这个成员同名的局部变量。因此，成员字段永远不会被初始化，并且您有未定义的行为。删除标记的 int 应该可以解决这个问题。

一般来说，你应该使用初始化列表来编写你的构造函数：

HashSet()
 : tableSize(0), 
   table(new LinkedList<string>[tableSize]); {
}

虽然是否应该像我上面那样对分配进行此操作值得商榷，但通常你根本不应该在代码中使用原始 new 或 new []，更好的是 std::shared_pointer/std::unique_pointer 或 std::vector.

哈希 Table - 条件跳转或移动取决于未初始化的值

Hash Table - Conditional jump or move depends on uninitialised value(s)

c++

hashtable

valgrind