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个,其余的都是空的,非常浪费
|