jjzjj

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

coder 2024-02-04 原文

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

// 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

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

最佳答案

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

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

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

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

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

amp43intelementHashTablec++binary-search-tree

有关c++ - 我的哈希表比二进制搜索慢的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby-on-rails - 如何在我的 Rails 应用程序 View 中打印 ruby​​ 变量的内容？ - 2

    我是一个Rails初学者，但我想从我的RailsView(html.haml文件)中查看Ruby变量的内容。我试图在ruby​​中打印出变量(认为它会在终端中出现)，但没有得到任何结果。有什么建议吗？我知道Rails调试器，但更喜欢使用inspect来打印我的变量。 最佳答案 您可以在View中使用puts方法将信息输出到服务器控制台。您应该能够在View中的任何位置使用Haml执行以下操作:-puts@my_variable.inspect 关于ruby-on-rails-如何在我的R

  3. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  4. ruby - 如何在 Grape 中定义哈希数组？ - 2

    我使用Ember作为我的前端和GrapeAPI来为我的API提供服务。前端发送类似:{"service"=>{"name"=>"Name","duration"=>"30","user"=>nil,"organization"=>"org","category"=>nil,"description"=>"description","disabled"=>true,"color"=>nil,"availabilities"=>[{"day"=>"Saturday","enabled"=>false,"timeSlots"=>[{"startAt"=>"09:00AM","endAt"=>

  5. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  6. ruby - 我可以将我的 README.textile 以正确的格式放入我的 RDoc 中吗？ - 2

    我喜欢使用Textile或Markdown为我的项目编写自述文件，但是当我生成RDoc时，自述文件被解释为RDoc并且看起来非常糟糕。有没有办法让RDoc通过RedCloth或BlueCloth而不是它自己的格式化程序运行文件？它可以配置为自动检测文件后缀的格式吗？(例如README.textile通过RedCloth运行，但README.mdown通过BlueCloth运行) 最佳答案 使用YARD直接代替RDoc将允许您包含Textile或Markdown文件，只要它们的文件后缀是合理的。我经常使用类似于以下Rake任务的东西:

  7. jquery - 我的 jquery AJAX POST 请求无需发送 Authenticity Token (Rails) - 2

    rails中是否有任何规定允许站点的所有AJAXPOST请求在没有authenticity_token的情况下通过？我有一个调用Controller方法的JqueryPOSTajax调用，但我没有在其中放置任何真实性代码，但调用成功。我的ApplicationController确实有'request_forgery_protection'并且我已经改变了config.action_controller.consider_all_requests_local在我的environments/development.rb中为false我还搜索了我的代码以确保我没有重载ajaxSend来发送

  8. ruby - 在哈希的键数组中追加元素 - 2

    查看我的Ruby代码:h=Hash.new([])h[0]=:word1h[1]=h[1]输出是:Hash={0=>:word1,1=>[:word2,:word3],2=>[:word2,:word3]}我希望有Hash={0=>:word1,1=>[:word2],2=>[:word3]}为什么要附加第二个哈希元素(数组)？如何将新数组元素附加到第三个哈希元素？ 最佳答案 如果您提供单个值作为Hash.new的参数(例如Hash.new([])，完全相同的对象将用作每个缺失键的默认值。这就是您所拥有的，那是你不想要的。您可以改用

  9. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  10. ruby - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

随机推荐