C ++中的哈希表？ STL？ [英] Hash table in C++? STL?

问题描述

大家好，

C ++ / STL是否有散列表我可以做的事情如下：


Hashtable h< int> ;;


h.store（" one"，1）;

h.store（" two"，2）;


然后检索它们如：


cout<< h.fetch（" one"）<< endl;


打印1


任何想法？


谢谢！

解决方案

" pembed2003" < PE ******** @ yahoo.com>在消息中写道

新闻：db ************************* @ posting.google.co m ... < blockquote class =post_quotes>大家好，
C ++ / STL是否有散列表我可以做的事情如下：

Hashtable h< int> ;;

h .store（" one"，1）;
h.store（" two"，2）;

然后检索它们，如：

cout<< h.fetch（" one"）<< endl;

打印1

任何想法？

谢谢！

它有一个具有与上面相同功能的地图（但是商店被称为

insert和fetch被称为find）。地图通常基于红黑树

算法。一些库实现者还提供了一个真正的哈希表

（称为hash_map），显然这个版本将使其成为该标准未来版本的

。


john

John Harrison写道：

它有一张地图与上面相同的功能（但商店名为
insert和fetch称为find）。地图通常基于红黑树算法。一些库实现者还提供了一个真正的哈希表
（称为hash_map），显然这个版本的某些版本将使其成为该标准的未来版本。

有谁知道需要提供什么才能在

特定类型上哈希？ std :: map需要一个小于比较操作 -

基于哈希的地图需要什么操作？


-Kevin

-

我的电子邮件地址有效，但会定期更改。

要联系我，请使用最近发布的地址。

" Kevin Goodsell" <我们********************* @ neverbox.com>写了

有谁知道需要提供什么才能在特定类型上散列？ std :: map需要比比较操作少 - 基于哈希的地图需要什么操作？

哈希函数并且平等操作是最低要求，但是需要进行关系比较（例如less_than）而不是相等的

将允许实施者进行某些优化（比如使用

a树状结构而不是桶的列表）。我不知道

标准是否需要相等或关系比较器。


遗憾的是，哈希函数是所有复杂性所在的地方而我如果超过1％的程序员知道是什么构成了一个好的散列函数，那么就会感到惊喜。由于糟糕的散列函数（以及一个天真的存储桶

策略），性能可能会迅速退化到比大数据集上的平衡

树更糟糕的情况。


Claudio Puviani

Hi All,
Does C++/STL have hashtable where I can do stuff like:

Hashtable h<int>;

h.store("one",1);
h.store("two",2);

and then later retrieve them like:

cout<<h.fetch("one")<<endl;

prints 1

any idea?

Thanks!

解决方案

"pembed2003" <pe********@yahoo.com> wrote in message
news:db*************************@posting.google.co m...

Hi All,
Does C++/STL have hashtable where I can do stuff like:

Hashtable h<int>;

h.store("one",1);
h.store("two",2);

and then later retrieve them like:

cout<<h.fetch("one")<<endl;

prints 1

any idea?

Thanks!

It has a map which has the same functionality as above (but store is called
insert and fetch is called find). Map is usually based on a red-black tree
algorithm. Several library implementers also offer a genuine hash table
(called hash_map) and apparently some version of this will make it into a
future version of the standard.

john

John Harrison wrote:

It has a map which has the same functionality as above (but store is called
insert and fetch is called find). Map is usually based on a red-black tree
algorithm. Several library implementers also offer a genuine hash table
(called hash_map) and apparently some version of this will make it into a
future version of the standard.

Does anyone know what will need to be provided in order to hash on a
particular type? std::map requires a less-than comparison operation --
what operations would a hash-based map need?

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

"Kevin Goodsell" <us*********************@neverbox.com> wrote

Does anyone know what will need to be provided in
order to hash on a particular type? std::map requires
a less-than comparison operation -- what operations
would a hash-based map need?

A hashing function and an equality operation are the minimum requirements, but
requiring a relational comparison (such as less_than) instead of equality would
allow for certain optimizations on the part of the implementers (such as using
a tree-like structure instead of lists for the buckets). I don''t know whether
the standard will require equality or a relational comparator.

Sadly, the hashing function is where all the complexity lies and I''d be
pleasantly surprised if more than 1% of programmers knew what constitutes a
good hashing function. With a bad hashing function (and a naive bucket
strategy), performance can quickly degenerate to much worse than a balanced
tree on large data sets.

Claudio Puviani

这篇关于C ++中的哈希表？ STL？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！