相关疑难解决方法(0)

我需要将原始键(int,可能很长)映射到高性能哈希映射数据结构中的struct值.

我的程序将有几百个这样的地图,每个地图通常最多只有几千个条目.但是,地图会不断地"刷新"或"翻腾"; 想象一下处理数百万add和delete消息.

C或C++中的哪些库具有适合此用例的数据结构？或者,您会如何建议自己建造？谢谢!

C++ STL unordered_map如何解决冲突？

查看http://www.cplusplus.com/reference/unordered_map/unordered_map/,它显示"唯一键容器中没有两个元素可以具有等效键."

这应该意味着容器确实解决了碰撞.但是,该页面并没有告诉我它是如何做到的.我知道一些解决冲突的方法,比如使用链表和/或探测.我想知道的是c ++ STL unordered_map如何解析它.

我还没有读过C++标准,但这就是我觉得c ++的unordered_map假设可行的方式.

• 在堆中分配内存块.
• 对于每个put请求,散列对象并将其映射到此内存中的空间
• 在此过程中通过链接或开放寻址来处理碰撞处理.

我很惊讶我找不到有关unordered_map如何处理内存的信息.是否存在unordered_map分配的特定初始内存大小.如果我们说我们分配了50个内存并且我们最终插入5000整数会怎么样？

这将是很多碰撞,所以我认为应该有一种像重新散列和重新调整大小的算法,以在达到一定程度的碰撞阈值后减少碰撞次数.由于它们是作为成员函数显式提供给类的,因此我假设它们也在内部使用.有这样的机制吗？

在使用Go代码时,我发现地图值不可寻址.例如,

package main
import "fmt"

func main(){
    var mymap map[int]string = make(map[int]string)
    mymap[1] = "One"
    var myptr *string = &mymap[1]
    fmt.Println(*myptr)
}

生成错误

mapaddressable.go:7:不能取mymap的地址[1]

然而,代码,

package main
import "fmt"

func main(){
    var mymap map[int]string = make(map[int]string)
    mymap[1] = "One"
    mystring := mymap[1]
    var myptr *string = &mystring
    fmt.Println(*myptr)
}

工作得非常好.

为什么会这样？为什么Go开发人员选择使某些值无法解决？这是语言的缺点还是一个特征？

编辑:从C++背景来看,我不习惯这种not addressable似乎在Go中流行的趋势.例如,以下代码可以正常工作:

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
    map<int,string> mymap;
    mymap[1] = "one";
    string *myptr = &mymap[1];
    cout<<*myptr;
}

如果有人能指出为什么在Go中无法实现(或故意未实现)相同的可寻址性,那将是很好的.

我正在处理一些非常大std::unordered_map的(数亿条目),需要将它们保存到文件中并从文件中加载它们.我目前这样做的方法是迭代地图并一次读取/写入每个键和值对:

std::unordered_map<unsigned long long int, char> map;

void save(){
    std::unordered_map<unsigned long long int, char>::iterator iter;
    FILE *f = fopen("map", "wb");
    for(iter=map.begin(); iter!=map.end(); iter++){
        fwrite(&(iter->first), 8, 1, f);
        fwrite(&(iter->second), 1, 1, f);
    }
    fclose(f);
}

void load(){
    FILE *f = fopen("map", "rb");
    unsigned long long int key;
    char val;
    while(fread(&key, 8, 1, f)){
        fread(&val, 1, 1, f);
        map[key] = val;
    }
    fclose(f);
}

但是有大约6.24亿条记录,从文件中读取地图需要9分钟.写入文件速度更快但仍需要几分钟.有更快的方法吗？

我正在解决LeetCode上的问题，但是没有人能够解释我的问题。

问题是这样的：

给定一个任意的赎金票据字符串和另一个包含所有杂志字母的字符串，编写一个函数，如果可以从杂志中构造赎金票据，则该函数将返回true；否则，它将返回false。

杂志字符串中的每个字母只能在赎金记录中使用一次。

注意：您可以假定两个字符串都只包含小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

我的代码（需要32毫秒）：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if(ransomNote.size() > magazine.size()) return false;
        unordered_map<char, int> m;

        for(int i = 0; i < magazine.size(); i++)
            m[magazine[i]]++;

        for(int i = 0; i < ransomNote.size(); i++)
        {
            if(m[ransomNote[i]] <= 0) return false;
            m[ransomNote[i]]--;
        }
        return true;
    }
};

代码（我不知道为什么会更快-需要19毫秒）：

bool canConstruct(string ransomNote, string magazine) {
        int lettersLeft = ransomNote.size(); // Remaining # of …

我有点困惑,unordered_map是如何工作的,什么是桶以及如何管理它们.

在这篇博文中,unordered_map是向量的向量.

我的问题是:

• 假设桶是"内部"向量是正确的吗？
• 因为每个桶(向量)可以包含多个元素,由哈希表上的哈希冲突("外部"向量)给出,并且由于我们必须扫描这个内部向量(在线性时间内),假设我们是正确的必须在密钥类型上定义相等的方法(对哈希运算符成瘾)才能找到桶内的密钥？
• 默认情况下外部向量(哈希表)大小是多少？
• 默认情况下内部矢量大小是多少？
• 如果一个桶中的元素数量变得太大会发生什么呢？换句话说,当重新发生时？

很抱歉这些问题,但我没有找到任何详细解释这个结构是如何工作的(例如在cppreference.com上).

我试图弄清楚是否有可能std::unordered_map使用 Cuckoo Hashing、Hopscotch Hashing 和 Robin Hood Hashing 等技术构建现代 C++ 的合规、高效实现，这些技术允许非常紧凑的表、高负载因子并保持高性能。这些技术的特别之处在于，它们涉及潜在地移动一些元素来为其他元素腾出空间，而不仅仅是链接或探测直到找到一个开放的插槽（如在线性或二次探测中）或。

来自insert http://www.cplusplus.com/reference/unordered_map/unordered_map/insert/

1. 迭代器有效性在大多数情况下，容器中的所有迭代器在插入后仍然有效。唯一的例外是当容器的增长迫使重新散列时。在这种情况下，容器中的所有迭代器都将失效。

2. 如果插入操作后新容器的大小增加到超过其容量阈值（计算为容器的 bucket_count 乘以其 max_load_factor），则强制重新散列。

3. 对 unordered_map 容器中元素的引用在所有情况下都保持有效，即使在重新哈希后也是如此。

而对于erase http://www.cplusplus.com/reference/unordered_map/unordered_map/erase/

4. 只有迭代器和对被删除元素的引用无效。

5. 其余不受影响。

6. [仅限 c++14] 保留未由操作删除的元素的相对迭代顺序。

其他引用在这两个操作中通常保持有效的要求似乎需要一个涉及驱逐的探测方案来处理表结构，该表结构将分配的节点与数组分开并指向它们。也许实现可以保留一个单独的元素数组，表中的条目可以索引到这些元素，以避免额外的动态分配，但这仍然增加了额外的间接性。有没有更有效的方法来满足这个要求？

insert即使在重新散列之后，元素引用仍然有效的要求似乎意味着即使对于链接或非移动开放寻址设计，也需要动态节点分配或类似上述间接数组的东西。那正确吗？

一般来说，标准所提出的要求是否unordered_map强制执行间接或哈希表实现中的其他某种低效率？

我想以指针为键映射数据。我应该选择哪个容器，map 还是 unordered_map？关于这个主题的 stackoverflow 有多个问题，但是当我们需要迭代所有键值对时，它们都没有涵盖性能方面。

std::map<classKey* , classData*> myMap;
std::unordered_map<classKey* , classData*> myUnorderedMap;

for (auto & iter : myMap) { //loop1
    display(iter.second);
}

for (auto & iter : myUnorderedMap) { //loop2
    display(iter.second);
}

loop1 与 loop2 哪个提供更好的性能。 替补马克商提供@ RetiredNinja

对于 size = 10,000,000 我们得到以下基准结果：

我试图比较stl map和stl unordered_map进行某些操作.我在网上看了一下,这只会增加我对哪一个整体更好的疑虑.所以我想根据他们执行的操作来比较这两者.

哪一个表现得更快

插入,删除,查找

哪一个占用更少的内存,更少的时间从内存中清除它.任何解释都热烈欢迎!

提前致谢