|
|---|
|
|
|
|
|
|
k**l
发帖数: 2966 | 1 没在其他语言用过hashmap，想来这个问题应该不限于c++
我知道c++ unordered_map 可以自定义 hash function
hash function 要求要尽量没有collision, 然后最好不太大。
我的问题是多大会太大影响速度，如果我自定义一个hash function把6个大写字母
hash成一个唯一的int (0~2^30的任意数字)，这个hashmap岂不需要占据30位的内存空
间，这是不是太大了－－－还是我理解错了，unordered_map 到底如何占据内存？
多谢 | w***g
发帖数: 5958 | 2 你想说什么？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*****w
发帖数: 144 | 3 还有一步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*********e
发帖数: 14401 | 4 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******n
发帖数: 12088 | 5 理解错误。散列表大小和元素个数成线性。
看看散列表的基本概念吧。
【在 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******n
发帖数: 12088 | 6 不可能。红黑树比散列表省内存，但以查询/增删时间变长为代价。
【在 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**y
发帖数: 151 | 7 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 到底如何占据内存？
: 多谢
|
|
|
|
|
|
|
|
