gpt4 book ai didi

c++ - 我的哈希表比二进制搜索慢

转载 作者:塔克拉玛干 更新时间:2023-11-02 23:33:59 25 4
gpt4 key购买 nike

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

// 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 index
// If not, return -1
if (foundelement != table[index].end())
return index;
else
return -1;
}



// Adds element to hashtable
void HashTable::insert(int element)
{
// Get index from hash and insert the element
int index = hash(element);
table[index].push_back(element);
}

哈希表.h

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <list>
#include <iostream>
#include <vector>

class HashTable
{
private:
// Each position in Hashtable has an array of lists to store elements in case of collision
std::list<int>* table;

// Size of hashtable
int size;

// Hashfunction that returns the array location for the given key
int hash(int key);

public:

HashTable(int tablesize);
HashTable(std::vector<int> primes);

// Adds element to hashtable
void insert(int element);

// Deletes an element by key
void remove(int key);

// Returns an element from hashtable for a given key
int find(int key);

// Displays the hashtable
void printTable();

// Display histogram to illustrate elements distribution
void printHistogram();

// Returns the number of lists in hash table
int getSize();

// Returns the total number of elements in hash table
int getNumberOfItems();

// De-allocates all memory used for the Hash Table.
~HashTable();
};

#endif

我已经尝试超过表的大小来消除冲突,但我没有注意到任何差异。

This is the result

最佳答案

哈希表实现的一些次优之处:

  • primes.size() * 20过多 - 你会得到比必要更多的缓存未命中;尝试 1 到 ~2 之间的一系列值以找到最佳点

  • primes.size() * 20总是偶数,所有你用 key % size 散列的素数很奇怪,所以你永远不会散列到一半的桶中,浪费空间并降低缓存性能

  • 您处理与链表的冲突:这意味着您始终遵循至少一个远离表的连续内存的指针,这很慢,并且对于冲突,您在内存中与列表中的每个节点跳来跳去;使用 std::vector<int>存储冲突值会在哈希表外的 1 个内存区域限制跳跃,或者您可以使用封闭哈希/开放寻址和位移列表通常在附近的哈希表桶中找到元素:我的基准测试发现大约一个顺序类似的幅度更快 int值(value)观。

关于c++ - 我的哈希表比二进制搜索慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34123282/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com