小编use*_*508的帖子

我已经实现了二进制搜索,线性搜索和哈希表来比较每个时间复杂度.问题是,当我测量查找素数的时间时,我的哈希表比二进制搜索慢得多.以下是我的代码:

// Make the hash table 20 times the number of prime numbers
HashTable::HashTable(std::vector<int> primes)
{
    int tablesize = primes.size() * 20;
    table = new std::list<int>[tablesize];
    size = tablesize;
    for (auto &prime : primes)
        this->insert(prime);
}

// Hash function
int HashTable::hash(int key)
{
    return key % size;
}

// Finds element
int HashTable::find(int key)
{
    // Get index from hash
    int index = hash(key);

    // Find element
    std::list<int>::iterator foundelement = std::find(table[index].begin(), table[index].end(), key);


    // If element has been found return …