chapter_hashing/hash_map/ #78
Replies: 59 comments 80 replies
-
大佬,在”哈希表优势“那一小节中,在“有序数组: 将 1. 中的数组按照学号从小到大排序”中,“1.”找不到对照。4种数据结构用有序列表列出会不会更好一些? |
Beta Was this translation helpful? Give feedback.
-
文章中对比五种数据结构各操作的时间复杂度中,链表的插入元素应该是O(n)。 |
Beta Was this translation helpful? Give feedback.
-
数据结构操作时间复杂度那,链表删除不是O(1)吗? |
Beta Was this translation helpful? Give feedback.
-
在初始化哈希表中(JavaScript 代码): |
Beta Was this translation helpful? Give feedback.
-
这一块儿 typescript 代码是不是不对?获取所有键值对,看起来只 push 了键? |
Beta Was this translation helpful? Give feedback.
-
哈希表底层实现是数组、链表、二叉树,那为什么效率可以更高呢 |
Beta Was this translation helpful? Give feedback.
-
问一下,为什么不使哈希函数f(x) = x 呢。这样就不会有冲突了。 |
Beta Was this translation helpful? Give feedback.
-
受教了,才知道哈希表算的是key和数组下标的关系,之前居然还以为是key 和 value的关系,实在是一点不懂啊哈哈 |
Beta Was this translation helpful? Give feedback.
-
array_hash_map.java
|
Beta Was this translation helpful? Give feedback.
-
哈希表是一个神奇的数据结构。但其实需要细较下它的复杂度,我们仅拿查找 key 为例,人人都说是常数时间复杂度,实际上是过于笼统了,因为没有考虑求 key 的哈希值的复杂度。 比如对于key类型为 string 的哈希表,要在其中找到一个 key,首先需要对这个key做一次哈希计算,字符串的话至少要遍历一次这个字符串,也就是哈希计算的复杂度为 O(m),m 指key的长度,总的查询复杂度也是 O(m)。 当然,对于 int 类型的key,哈希计算的复杂度确实是常数级。 综上,如果 key 是 string 或复合类型(元组等)且 key 的平均长度很长,用哈希表效率非常低。 |
Beta Was this translation helpful? Give feedback.
-
有个疑惑,hash表 时间复杂度为啥是O(1),不应该是O(n) 吗? |
Beta Was this translation helpful? Give feedback.
-
上面数组,链表和哈希表的对比表看蒙了,应该明确一点。数组如果根据下标查询应该是O(1),而插入元素平均复杂度也应该是O(n),怎么就成了O(1)。链表的插入元素的复杂度为啥是O(1),不是应该是O(N)吗? |
Beta Was this translation helpful? Give feedback.
-
我感觉哈希冲突示例图那里容易引起误会。哈希冲突是在添加新元素时发生的,新的元素可能顶掉旧元素,而不是查找时发生的。图里面呈现的是查找过程。 |
Beta Was this translation helpful? Give feedback.
-
打卡,手敲了一遍哈希表的数组实现,对index和key才真正分清楚 |
Beta Was this translation helpful? Give feedback.
-
也就是理解为哈希表比数组链表拥有更小的时间复杂度是用更大的空间复杂度换的吗? |
Beta Was this translation helpful? Give feedback.
-
请问这里内存释放为什么需要传入引用 |
Beta Was this translation helpful? Give feedback.
-
想问一下,关于void pairSet(ArrayHashMap* hmap, MapSet* set),此函注中首次出现“MapSet”类型,但是我没有找到该类型的定义。我使用的是C语言版代码。 |
Beta Was this translation helpful? Give feedback.
-
这哈希表我觉得写的一坨啊 |
Beta Was this translation helpful? Give feedback.
-
请问为什么我在CLion运行源文件 array_hash_map.c 会报错: 添加完成后,哈希表为 进程已结束,退出代码为 -1073741819 (0xC0000005) |
Beta Was this translation helpful? Give feedback.
-
这个哈希表就算我容量很大,如果我就只有两个值,哈希函数key % 100,刚好都是36这样,那如何保证准确性啊 |
Beta Was this translation helpful? Give feedback.
-
/* 获取所有键值对 */
vector<Pair *> pairSet() {
vector<Pair *> pairSet;
for (Pair *pair : buckets) {
if (pair != nullptr) {
pairSet.push_back(pair);
}
}
return pairSet;
}
/* 获取所有键 */
vector<int> keySet() {
vector<int> keySet;
for (Pair *pair : buckets) {
if (pair != nullptr) {
keySet.push_back(pair->key);
}
}
return keySet;
} 这两个函数的函数名和里面的变量名是一样的,这样是可以的吗? |
Beta Was this translation helpful? Give feedback.
-
go语言版本map写的是链式寻址,查了一下,好像是开放寻址 |
Beta Was this translation helpful? Give feedback.
-
你好, 作者: |
Beta Was this translation helpful? Give feedback.
-
buckets= vector<Pair * > (100) 这只是给buckets确定容量,这样确定容量的方式好像 不怎么常见。为什么不用buckets.reserve(100)的方式确定容量? |
Beta Was this translation helpful? Give feedback.
-
话说,我直接用数组索引当key,不就不用hash了吗 |
Beta Was this translation helpful? Give feedback.
-
为什么不直接把学号当做数组的索引呢 |
Beta Was this translation helpful? Give feedback.
-
哈希表是不是不适用于python呀?python的字典本身就是用哈希表实现的,操作性更强,还不会有冲突,时间复杂度O(1) |
Beta Was this translation helpful? Give feedback.
-
Mapset是什么类别? |
Beta Was this translation helpful? Give feedback.
-
为什么添加操作里还要为pair->val开辟一块空间,直接将两个指针像等不就可以了吗? |
Beta Was this translation helpful? Give feedback.
-
您好! 收到————张贤平
|
Beta Was this translation helpful? Give feedback.
-
chapter_hashing/hash_map/
Your first book to learn Data Structure And Algorithm.
https://www.hello-algo.com/chapter_hashing/hash_map/
Beta Was this translation helpful? Give feedback.
All reactions