由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - HashMap, HashTable and Array 有啥区别
相关主题
请教:C++, 忽略大小写的字符串比较AMAZON onsite 3月面经
一道算法题目贡献几道CS电面题
finding the majority element in an array?amazon 第一轮电话面试
[提议]算法coding题目需要太傻那样的黑宝书请教一个设计test case的问题
string permutation,怎么处理重复字母?Google Intern面经顺求bless~
Minimum Window SubstringGoogle实习第一轮电话面试总结
热腾腾的hulu面经G家电面被拒,请帮助分析原因
攒人品!发面经一道linkedin的题。
相关话题的讨论汇总
话题: array话题: hashtable话题: hashmap话题: hash
进入JobHunting版参与讨论
1 (共1页)
r**********1
发帖数: 292
1
我看到有人就用array来代替hashmap,比如有个问题是问字符串1是否包含字符串2的所
有字符的时候,有人用256大小的array来做,如果是hashMap的话,有啥区别?
这三者有啥区别啊?
l*****a
发帖数: 14598
2
if the input data has fixed scope, u can use array instead of hashmap
hash_map is a C++ template which contains key/value pairs
hashtable is the internal implementation of hash_map

【在 r**********1 的大作中提到】
: 我看到有人就用array来代替hashmap,比如有个问题是问字符串1是否包含字符串2的所
: 有字符的时候,有人用256大小的array来做,如果是hashMap的话,有啥区别?
: 这三者有啥区别啊?

i**********e
发帖数: 1145
3
HashMap 是 one to many relationship,hashtable one to one.
看情况,主要 hashtable 和 array 的区别在于前者比较 general:
比如,要计算一个字符串里每个字母的出现次数,用简单的 array 再也适合不过了。
如果只是 ascii 字符,那 256 的大小就够了。
那另外一个例子,如果要计算一本书里每个字的出现次数,那简单的 array 做不到了
。因为 key 是 word,不能直接以 index 来 hash,那就用比较general的hashtable来
做。
还有另一种情况 hashtable 是比 array 好的,就是节省空间。为什么呢?
比方你的 key 的range在于 1 - 1,000,000,但是最多你只会 insert 不超过 100 个
element。那用array来做,那相当于只用数组里的100个,其余的都是空的,非常浪费
空间。但是 hashtable就没有这个问题,因为是 dynamic 的数据结构。
r**********1
发帖数: 292
4
那array是hashtable的内部实现方式?

【在 l*****a 的大作中提到】
: if the input data has fixed scope, u can use array instead of hashmap
: hash_map is a C++ template which contains key/value pairs
: hashtable is the internal implementation of hash_map

i**********e
发帖数: 1145
5
恩,这是其中一种实现方式。
我准备面试最基本的实现 chaining,就是利用 vector (C++) + linked list 来实现。

【在 r**********1 的大作中提到】
: 那array是hashtable的内部实现方式?
r**********1
发帖数: 292
6
“那另外一个例子,如果要计算一本书里每个字的出现次数,那简单的 array 做不到了
。因为 key 是 word,不能直接以 index 来 hash,那就用比较general的hashtable来
做。”
我是想弄清出啊。对于这个例子,用hashtable是不是如下做法?
对于每个word,我算一个hash value, 比如把每个character的ascii码加在一块得到一
个sum值,我可以把这个sum值作为hash value。
然后,我建立一个大小为1000的数组,A,初始化为0。
然后,对于每个word,算出hash value,然后以它来作为index,把相应的A[hash]进行
++操作。
对于hash value 大于1000的,进行动态扩展数组,然后继续。
这么说来,hash table 似乎是高级的动态数组。
ihasleetcode,您觉得我的理解对吗?

【在 i**********e 的大作中提到】
: HashMap 是 one to many relationship,hashtable one to one.
: 看情况,主要 hashtable 和 array 的区别在于前者比较 general:
: 比如,要计算一个字符串里每个字母的出现次数,用简单的 array 再也适合不过了。
: 如果只是 ascii 字符,那 256 的大小就够了。
: 那另外一个例子,如果要计算一本书里每个字的出现次数,那简单的 array 做不到了
: 。因为 key 是 word,不能直接以 index 来 hash,那就用比较general的hashtable来
: 做。
: 还有另一种情况 hashtable 是比 array 好的,就是节省空间。为什么呢?
: 比方你的 key 的range在于 1 - 1,000,000,但是最多你只会 insert 不超过 100 个
: element。那用array来做,那相当于只用数组里的100个,其余的都是空的,非常浪费

r**********1
发帖数: 292
7
一个问题是,如果是vector实现,对于读取的效率是否影响? 似乎我们要求O(1)的
读取时间。

现。

【在 i**********e 的大作中提到】
: 恩,这是其中一种实现方式。
: 我准备面试最基本的实现 chaining,就是利用 vector (C++) + linked list 来实现。

i**********e
发帖数: 1145
8
如果你的数组大小为 1000,hashvalue 不应该大于 1000.通常简单的就是把
hashvalue % 1000。
你基本对 hashtable 的理解差不多对了,但是漏了一个很重要的环节,就是
collision.你的hashfunction,也就是把 key 转换成 hashvalue 的,不能保证是绝对
一对一的转换。这意味着很有可能有多个不同的 key hash 成同一个 hashvalue。
例如: "ate" 和 "eat" 共享同一个 hashvalue。
那这样你要有个方法处理冲突,要不然你不能识别 "ate" 和 "eat" 个别的出现次数。
至于怎么处理冲突,这有很多方法。有比较简单的 probing,还有比较出名的
chaining. 可以上网查一查或者看看书。
另外,你的 hashfunction 虽然简单,但是你一旦用了就会发现很多问题。首先要确保
hashfunction 是分散得很均匀,而不是集中在一些地方。你说说看,以你这个
hashfunction,会有什么问题?

到了

【在 r**********1 的大作中提到】
: “那另外一个例子,如果要计算一本书里每个字的出现次数,那简单的 array 做不到了
: 。因为 key 是 word,不能直接以 index 来 hash,那就用比较general的hashtable来
: 做。”
: 我是想弄清出啊。对于这个例子,用hashtable是不是如下做法?
: 对于每个word,我算一个hash value, 比如把每个character的ascii码加在一块得到一
: 个sum值,我可以把这个sum值作为hash value。
: 然后,我建立一个大小为1000的数组,A,初始化为0。
: 然后,对于每个word,算出hash value,然后以它来作为index,把相应的A[hash]进行
: ++操作。
: 对于hash value 大于1000的,进行动态扩展数组,然后继续。

i**********e
发帖数: 1145
9
这无所谓,只是在 C++ 比较好写和安全而已。你用array也是可以的。另外,虽然
vector 会相对于 array 慢一些,但 vector 是保证 O(1) 的读取时间的。

【在 r**********1 的大作中提到】
: 一个问题是,如果是vector实现,对于读取的效率是否影响? 似乎我们要求O(1)的
: 读取时间。
:
: 现。

r**********1
发帖数: 292
10
“另外,你的 hashfunction 虽然简单,但是你一旦用了就会发现很多问题。首先要确保
hashfunction 是分散得很均匀,而不是集中在一些地方。你说说看,以你这个
hashfunction,会有什么问题?”
我的hashfunction的问题似乎如下:
1. 对于长度为1的words,集中在array的前方(因为sum比较小)
2. 对于长度位很长的比如25的words,集中在array的后方(因为sum比较大)
3. 对于很多适中长度的words,集中在中部。
这样看来,还比较分布均匀。但是如果考虑3的case比较多的话,我们就浪费了前后两
端的一些空间,而使得中部的conflicts比较多。
解决方案,似乎是可以用probe,就是在index附近找另外空的index,而不需要
chaining。
您看这个对不对?
另外,如果不用sum来作为每个words的hash value,那么那个函数更好一些?

【在 i**********e 的大作中提到】
: 如果你的数组大小为 1000,hashvalue 不应该大于 1000.通常简单的就是把
: hashvalue % 1000。
: 你基本对 hashtable 的理解差不多对了,但是漏了一个很重要的环节,就是
: collision.你的hashfunction,也就是把 key 转换成 hashvalue 的,不能保证是绝对
: 一对一的转换。这意味着很有可能有多个不同的 key hash 成同一个 hashvalue。
: 例如: "ate" 和 "eat" 共享同一个 hashvalue。
: 那这样你要有个方法处理冲突,要不然你不能识别 "ate" 和 "eat" 个别的出现次数。
: 至于怎么处理冲突,这有很多方法。有比较简单的 probing,还有比较出名的
: chaining. 可以上网查一查或者看看书。
: 另外,你的 hashfunction 虽然简单,但是你一旦用了就会发现很多问题。首先要确保

t*****s
发帖数: 124
11

这里谈论的HashMap和hashtable概念是什么语言的?

【在 i**********e 的大作中提到】
: HashMap 是 one to many relationship,hashtable one to one.
: 看情况,主要 hashtable 和 array 的区别在于前者比较 general:
: 比如,要计算一个字符串里每个字母的出现次数,用简单的 array 再也适合不过了。
: 如果只是 ascii 字符,那 256 的大小就够了。
: 那另外一个例子,如果要计算一本书里每个字的出现次数,那简单的 array 做不到了
: 。因为 key 是 word,不能直接以 index 来 hash,那就用比较general的hashtable来
: 做。
: 还有另一种情况 hashtable 是比 array 好的,就是节省空间。为什么呢?
: 比方你的 key 的range在于 1 - 1,000,000,但是最多你只会 insert 不超过 100 个
: element。那用array来做,那相当于只用数组里的100个,其余的都是空的,非常浪费

1 (共1页)
进入JobHunting版参与讨论
相关主题
一道linkedin的题。string permutation,怎么处理重复字母?
ebay电面面经,攒人品,求好运Minimum Window Substring
为什么我这段简单的程序segment fault热腾腾的hulu面经
问一道题攒人品!发面经
请教:C++, 忽略大小写的字符串比较AMAZON onsite 3月面经
一道算法题目贡献几道CS电面题
finding the majority element in an array?amazon 第一轮电话面试
[提议]算法coding题目需要太傻那样的黑宝书请教一个设计test case的问题
相关话题的讨论汇总
话题: array话题: hashtable话题: hashmap话题: hash