一个关于unordered_map/hashmap的问题 - 未名空间MITBBS历史存档

一个关于unordered_map/hashmap的问题# Programming - 葵花宝典

z*n2015-04-28 07:04

1 楼

1. SapphireSM Preferred Card –狂送$500现金或价值$625机票
http://goo.gl/jycFB
限时大特惠，Chase提供超高开卡50K points bonus，可以直接兑换$500支票或价值$
625机票,足以兑换两张美国国内往返，首年无年费。赶快申请，落袋为安！
Earn 50,000 bonus points after you spend $3,000 in the first 3 months- that'
s worth $625 toward airfare or hotel accommodations!
http://goo.gl/jycFB
2. Chase Freedom Card - $150 Bonus Cash Back + 5% Cashback on GAS, Airline
开户送$150现金，接下来这个季度7/1/11 - 9/30/11就是大家最喜欢的5% gas
cashback(up to $1,500 spent on GAS, HOTEL and AIRLINE )，如果还没有这个卡片
的赶紧申请哦.
http://goo.gl/29TB3
3. 信用分数知多少？750？免费查询，快速提升
creditreport提供免费查询信用分数，三大信用记录公司之一Experian的分数，记得在
free trial结束前取消。信用卡申请前先查询一下自己分数，提高申请通过率。
http://goo.gl/xRORF
4. Chase SapphireSM Card – 25000 Points
申请就送$250现金，买机票和旅馆住宿2%现金返回，无年费
http://goo.gl/hOF3Z
5. United Mileage Plus Card 30000miles offer+$50bonus只需要任意一笔消费
http://bankbonus.blog.163.com/
6. Chase continental onepass 30000miles offer+$50bonus 只需要任意一笔消费
http://bankbonus.blog.163.com/
7. Gift Card购买好去处！Plastic Jungle折扣购物卡, 最高 35% off
http://goo.gl/k27zx
8. 免费的Marriott Hotel 四晚酒店入住只需消费一笔无金额限制
http://bankbonus.blog.163.com/
最近申请chase家的这个信用卡会弹出一个页面，写着Before you go…We hope you
will reconsider 难不成他们家最近被人拿太多这个免费机票了不用对它客气，
赶紧点击Return&Apply，拿到落袋为安。更多详细情况请查看
http://bankbonus.blog.163.com/

k*l2015-04-28 07:04

2 楼

没在其他语言用过hashmap，想来这个问题应该不限于c++
我知道c++ unordered_map 可以自定义 hash function
hash function 要求要尽量没有collision, 然后最好不太大。
我的问题是多大会太大影响速度，如果我自定义一个hash function把6个大写字母
hash成一个唯一的int (0~2^30的任意数字)，这个hashmap岂不需要占据30位的内存空
间，这是不是太大了－－－还是我理解错了，unordered_map 到底如何占据内存？
多谢

w*g2015-04-28 07:04

3 楼

你想说什么？std::map存成树，每个节点至少两个指针吧，那就是128 bit，还要涂红
黑啥的，再加上动态分配节点底层malloc的开销，我估计会比unordered_map更加耗空
间。
unordered_map的overhead主要在构造时给的bucket count。如果和元素个数相比
bucket count太大则会浪费，太小的话性能又会下降。30位的hash值只是用来索引
bucket，本身并不会被存下来。像你我这种水平的，没事就上std::map，不够快就再试
试std::unorderd_map，要还不行，就是算法设计有问题了。

【在 k**l 的大作中提到】

: 没在其他语言用过hashmap，想来这个问题应该不限于c++
: 我知道c++ unordered_map 可以自定义 hash function
: hash function 要求要尽量没有collision, 然后最好不太大。
: 我的问题是多大会太大影响速度，如果我自定义一个hash function把6个大写字母
: hash成一个唯一的int (0~2^30的任意数字)，这个hashmap岂不需要占据30位的内存空
: 间，这是不是太大了－－－还是我理解错了，unordered_map 到底如何占据内存？
: 多谢

e*w2015-04-28 07:04

4 楼

还有一步hash -> bucket number，一般就对#buckets取模。并不是说你的hash有多少
位就需要这么大的内存空间。

【在 k**l 的大作中提到】

: 没在其他语言用过hashmap，想来这个问题应该不限于c++
: 我知道c++ unordered_map 可以自定义 hash function
: hash function 要求要尽量没有collision, 然后最好不太大。
: 我的问题是多大会太大影响速度，如果我自定义一个hash function把6个大写字母
: hash成一个唯一的int (0~2^30的任意数字)，这个hashmap岂不需要占据30位的内存空
: 间，这是不是太大了－－－还是我理解错了，unordered_map 到底如何占据内存？
: 多谢

g*e2015-04-28 07:04

5 楼

unorderedmap 很快的比俺手写的mmap里的哈希表快

【在 w***g 的大作中提到】

: 你想说什么？std::map存成树，每个节点至少两个指针吧，那就是128 bit，还要涂红
: 黑啥的，再加上动态分配节点底层malloc的开销，我估计会比unordered_map更加耗空
: 间。
: unordered_map的overhead主要在构造时给的bucket count。如果和元素个数相比
: bucket count太大则会浪费，太小的话性能又会下降。30位的hash值只是用来索引
: bucket，本身并不会被存下来。像你我这种水平的，没事就上std::map，不够快就再试
: 试std::unorderd_map，要还不行，就是算法设计有问题了。

n*n2015-04-28 07:04

6 楼

理解错误。散列表大小和元素个数成线性。
看看散列表的基本概念吧。

【在 k**l 的大作中提到】

: 没在其他语言用过hashmap，想来这个问题应该不限于c++
: 我知道c++ unordered_map 可以自定义 hash function
: hash function 要求要尽量没有collision, 然后最好不太大。
: 我的问题是多大会太大影响速度，如果我自定义一个hash function把6个大写字母
: hash成一个唯一的int (0~2^30的任意数字)，这个hashmap岂不需要占据30位的内存空
: 间，这是不是太大了－－－还是我理解错了，unordered_map 到底如何占据内存？
: 多谢

n*n2015-04-28 07:04

7 楼

不可能。红黑树比散列表省内存，但以查询/增删时间变长为代价。

【在 w***g 的大作中提到】

: 你想说什么？std::map存成树，每个节点至少两个指针吧，那就是128 bit，还要涂红
: 黑啥的，再加上动态分配节点底层malloc的开销，我估计会比unordered_map更加耗空
: 间。
: unordered_map的overhead主要在构造时给的bucket count。如果和元素个数相比
: bucket count太大则会浪费，太小的话性能又会下降。30位的hash值只是用来索引
: bucket，本身并不会被存下来。像你我这种水平的，没事就上std::map，不够快就再试
: 试std::unorderd_map，要还不行，就是算法设计有问题了。

s*y2015-04-28 07:04

8 楼

std::map和std::unordered_map都是container class容器类，里面保存了你加进去的
一对对的pair。
std::map是用一个比较function来通过Key排序／查找pair。
std::unordered_map是用一个hash function来通过Key查找pair。
所以std::map或std::unordered_map需要占据多大内存，取决于你有多少数据pair,T>加进这个容器，这个内存大小和比较function或hash function本身无关。
hash function需要把你的每一个可能的Key转变成对应的T value，并且（1）转化快速
少用额外内存；（2）所有可能的T values尽量紧凑；（3）不同T values尽可能少出现
碰撞。
以你的6个大写字面为例子，假定每个字母是在26个字母里随机抽取。
6个大写字母字符串是Key，有26^6＝308,915,776种可能性。而T是int，按你的要求，
一个(0~2^30)的int有2^30=1,073,741,824个数字。所以把你的每一个字符串转变成（
映射成）不同的int数字，并且没有碰撞，是有可能达到的。
一个可能的hash function实现是这样的，如果‘A'=0，'Z'=25，那么每个字符可以用5
个bit来表示：‘A'=00000, 'Z'=11001. 这样我们就可以把这六个字符的5-bit值塞进
一个30bit的int中。
如果字符串是std::string, size=6, 其中每个字符都是大写字母，那么
int get_hash(const std::string& key)
{
const char *str = key.c_str();
int hash_value =
(str[0]-0x41)<<25 + (str[1]-0x41)<<20 +
(str[2]-0x41)<<15 + (str[3]-0x41)<<10 +
(str[4]-0x41)<< 5 + (str[5]-0x41) ;
return hash_value;
}
这个hash function不会产生任何碰撞。

【在 k**l 的大作中提到】

: 没在其他语言用过hashmap，想来这个问题应该不限于c++
: 我知道c++ unordered_map 可以自定义 hash function
: hash function 要求要尽量没有collision, 然后最好不太大。
: 我的问题是多大会太大影响速度，如果我自定义一个hash function把6个大写字母
: hash成一个唯一的int (0~2^30的任意数字)，这个hashmap岂不需要占据30位的内存空
: 间，这是不是太大了－－－还是我理解错了，unordered_map 到底如何占据内存？
: 多谢