C++中的哈希表等效实现

Question

我有一个应用程序（使用C++编程语言），在其中我需要有一组字符串和整数之间的配对，即：

("david", 0)
("james", 1)
("helen", 2)
... 

如果我们使用Java的(key, value)定义，我需要能够(1)搜索以查看映射中是否存在一个键，以及(2)检索与给定字符串(key)相关联的值。在Java中工作时，我发现HashMap类型可以处理我所需的一切。

我想在C++中做同样的事情。我在网上搜索了一下，发现在C++ 2011库中有一种unordered_map类型可以复制这个功能。我很好奇这是否是最好的方法。

在我的应用程序中，我对集合有以下规定:

1. 整数始终是顺序的(如示例所示)，并从0开始。
2. 整数值永远不会改变。
3. Map在应用程序启动时创建，不会更改，即它是不可变的。
4. 没有字符串键的重复。
5. 在创建映射时，我不知道要使用多少键(以及通过扩展整数值)，我的应用程序的参数之一是包含要使用的单词列表的文本文件的目录。
6. 我不关心与此相关的启动时间成本。我需要主要任务(即containsKey(..)和get(key))尽可能快。而且它将被频繁调用。该应用程序的重点是处理大型文本语料库(即Wikipedia)并在单词/文档之间形成共现矩阵。

我认为，与其同时存储整数和字符串，不如将字符串存储在某些列表类型中，然后返回索引，即data = {"david", "james", "helen", ...}，然后使用find_Map(data, key)来返回它所在的索引(值)。我认为这可以通过首先按升序排序并应用搜索算法来加速。但是，这只是一个猜测。

我确实知道这是一个常见的问题，有许多不同的方法存在。我将编写几个不同的想法，但认为最好先问一下小组，看看你们的想法。

- DavidG

---

你应该重新表述问题，因为你混淆了键和值——例如，当你说“检索与给定字符串相关联的键”时——我认为这个字符串就是键。 - davidbak

顺便提一下 - 假设您已经测量了程序并确定两个操作contains()和find()是时间消耗的原因，这就是为什么您需要尽可能快地使用它们 - 还有必要知道诸如成功查找与未命中查找之间的比率等信息。换句话说，搜索时是否更有可能找到键，还是没有找到？总的来说，除非您真的时间紧迫，否则unordered_map没有任何问题。 - davidbak

注意，在处理字符串时，字符串比较是很耗费资源的。有序映射使用哈希表进行操作，然后再通过字符串比较进行验证。如果您手动编写数据结构，则应该也要使用哈希表。但这就涉及到如何生成快速哈希值的问题，这取决于您的字符串。 - davidbak

@user3053801 - 在你上面的例子中，整数虽然紧凑，但在键方面并不是连续的（假设按字母顺序排序）。 （例如，“james”在字母表顺序中在“Helen”之后。）因此，按键（即字符串）排序的结构仍需要存储值（即int）。除非你的例子是错误的。 - davidbak

我建议删除Java标签，因为这与Java关系很小。并且在变量名称上保持一致：在C++中没有叫做Integer的东西。 - Passer By

Answer 1

你可以使用unordered_map<string,int>来进行相关的IT技术操作。

- Zaid Khan

Answer 2

根据您想要存储的数据量，有两种可能性：

• 对于中等数量的数据，我认为std::unordered_map<string, int>就可以胜任
• 如果您想处理大量的数据，则考虑更专门的字符串存储数据结构可能会有所帮助，例如tries，其中具有共同前缀的字符串被存储在共同子树中。这也可以提高您的空间利用率，因为数据会被“压缩”。我知道的最有效的实现是marisa-trie，也用于python pytries包。

- Tobias Ribizel

---

unordered_list 是什么？ - iehrlich

Answer 3

简单的答案当然是 std::unordered_map。然而，为了获取更多功能和自动索引一致性，我们可以使用 boost::multi_index_container。

例如：

namespace bmi = boost::multi_index;

// Define a custom container type
using my_map = boost::multi_index_container<
    // It holds StringValue objects
    StringValue,
    bmi::indexed_by<
        // first index is called by_string, is a unique hashed index with constant time lookuo
        bmi::hashed_unique<bmi::tag<by_string>, bmi::member<StringValue, std::string, &StringValue::str>>,

        // second index is called by_value, is a unique hashed index with constant time lookup
        bmi::hashed_unique<bmi::tag<by_value>, bmi::member<StringValue, int, &StringValue::value>>,

        // second index is called ordered_by_value, is a unique ordered index with logarithmic time lookup
        bmi::ordered_unique<bmi::tag<ordered_by_value>, bmi::member<StringValue, int, &StringValue::value>>
    >
>;

在这个例子中，my_map 被定义为一个容器，它具有以下特点：

• 保存 StringValue 对象

• 通过对象的 str 成员维护一个哈希唯一索引

• 通过对象的 value 成员维护一个哈希唯一索引

• 通过对象的 value 成员维护一个有序唯一索引，以便我们可以按值枚举（例如）

完整示例：

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/indexed_by.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/ordered_index.hpp>

#include <boost/format.hpp>
#include <string>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <type_traits>

// define a value object
struct StringValue
{
    std::string str;
    int         value;
};

// provide a way to stream the pair to an ostream
std::ostream& operator <<(std::ostream& os, StringValue const& sv)
{
    static const char fmt[] = R"__({ "str": %1%, "value": %2% })__";
    return os << boost::format(fmt) % std::quoted(sv.str) % sv.value;
}

struct by_string
{
};
struct by_value
{
};
struct ordered_by_value
{
};

namespace bmi = boost::multi_index;

// Define a custom container type
using my_map = boost::multi_index_container<
    // It holds StringValue objects
    StringValue,
    bmi::indexed_by<
        // first index is called by_string, is a unique hashed index with constant time lookuo
        bmi::hashed_unique<bmi::tag<by_string>, bmi::member<StringValue, std::string, &StringValue::str>>,
        // second index is called by_value, is a unique hashed index with constant time lookup
        bmi::hashed_unique<bmi::tag<by_value>, bmi::member<StringValue, int, &StringValue::value>>,
        // second index is called ordered_by_value, is a unique ordered index with logarithmic time lookup
        bmi::ordered_unique<bmi::tag<ordered_by_value>, bmi::member<StringValue, int, &StringValue::value>>
    >
>;

template<class Array>
struct ArrayEmitter
{
    const Array& array;

    friend std::ostream& operator<<(std::ostream& os, ArrayEmitter const& em) {
        const char* sep = " ";
        os << "[";
        for (auto&& item : em.array) {
            os << sep << item;
            sep = ", ";
        }
        return os << " ]";
    }
};

template<class Array>
auto emit_as_array(Array&& arr)
{
    return ArrayEmitter<std::remove_cv_t<Array>> { arr };
}

int main()
{
    my_map mm { { "B", 3 }, { "D", 1 }, { "A", 4 }, { "C", 2 } };

    // assert that we can't violate the indecies
    auto ib = mm.insert(StringValue{"E", 1});
    assert(ib.second == false);

    // iterate by string
    std::cout << "print by value index:\n";
    std::cout << emit_as_array(mm.get<by_string>()) << std::endl;

    std::cout << "\nprint by value index unordered:\n";
    std::cout << emit_as_array(mm.get<by_value>()) << std::endl;

    std::cout << "\nprint by value index ordered:\n";
    std::cout << emit_as_array(mm.get<ordered_by_value>()) << std::endl;

    std::cout << "\nfind an element by value in constant time:\n";
    auto&& name = mm.get<by_value>().find(2)->str;
    std::cout << name << std::endl;
}

期望输出：

print by value index:
[ { "str": "B", "value": 3 }, { "str": "D", "value": 1 }, { "str": "A", "value": 4 }, { "str": "C", "value": 2 } ]

print by value index unordered:
[ { "str": "B", "value": 3 }, { "str": "D", "value": 1 }, { "str": "A", "value": 4 }, { "str": "C", "value": 2 } ]

print by value index ordered:
[ { "str": "D", "value": 1 }, { "str": "C", "value": 2 }, { "str": "B", "value": 3 }, { "str": "A", "value": 4 } ]

find an element by value in constant time:
C

文档：

http://www.boost.org/doc/libs/1_62_0/libs/multi_index/doc/tutorial/index.html

- Richard Hodges

---

非常感谢您的帖子！ 我对C++还很陌生，所以我需要多读几遍（有些语法我还不熟悉）。 但再次感谢 - 我希望我能很快“阅读”并理解这个。 - DavidG