为什么在暴力遍历中，为什么数组转字典是优化计算速度？

[xzour]

自己数据结构比较薄弱，但我没想通 ArrayList<T> or List<T> 会比 Dic<int,T>慢？ 联动前贴： https://www.v2ex.com/t/736445

[xdeng]

哈希表

[Aoang]

例：
arr1, arr2, arr3
for range arr1{
for range arr2{
for range arr3{
// 处理
}
}
}

字典的话可能是
map1, map2, map3
for range map1{}
for range map1{}
for range map1{}

算法的复杂度比比就知道了

[Aesyt]

O(n) 和 O(1) 的区别？

[aijam]

1L 正解！！！

[sagaxu]

arraylist 遍历比 dict 更快才对

[weixiangzhe]

空间换时间，O(n^2) 和 O(2n) 的区别

[xx6412223]

抛开上下文，遍历 array 比 list 更快，array 是内存连续，list 一般不连续。而 map 的结构一般都是 list 来实现的

[xuanbg]

顺序遍历 array 肯定最快啊，查询才是 hashMap 快

[Moyudawang]

遍历的目的是为了精确查询？？？

[NexTooo]

字典走 hash，碰撞不多的情况下单次查询基本上是 O(1)，基本上就是空间换时间

[no1xsyzy]

因为你是嵌套遍历，而转字典的话内层改为查哈希表，就不用遍历了

[raaaaaar]

如果都是指查询的话，那么本质上就是顺序查找和 hash 查找的区别。顺序查找 O(n)，hash O(n)，自然 hash 快许多了。

原因是什么？因为无论是顺序查找，二分，索引，还是二叉平衡树，二叉查找树，甚至更高的红黑树这些，它们查找都是基于一个原则：比较。它们在查找的过程中会比较值和待查找值的情况，这个过程非常的大，也要算进时间复杂度，而 hash 是一种特殊的方法，它并没有比较这个过程，它参考了数组随机存取的思路，直接拿到目标内存的地址，直接查表。

那么这个地址是怎么拿到的？这就是 hash 函数的作用，但是有时候地址冲突怎么办？这就是 hash 冲突，所以怎么选取 hash 函数，怎么解决冲突，对时间复杂度都有很大的影响。

[raaaaaar]

楼上打错了，hash 是 o(1)，是平衡二叉树

[qwerthhusn]

简单说，查字典，是先看偏旁部首快，还是从第一页 啊阿吖嗄 开始一个一个找得快？

[xzour]

@raaaaaar 哈希查找 一般查找比对的值一般是在<T>里面的吧？哈希表也有优化吗？还是对 KEY 的优化？这是我疑惑的地方。

[zvl0reqglvd]

hash 吧，空间换时间

[raaaaaar]

@xzour #15

现在有一个 array，是这样的 [1,2,5,67,7,8,9]，要查看 7 这个值，如果我顺序查找，那么就只能遍历，先 1 和 7 比较，然后 2 和 7 比较，一直到 7 和 7 相等，这有比较的过程。

由于 hash table 是 key-value 的，现在假设我们最终的 hash table 就是 [1,2,5,67,7,8,9] 这个样子，我们要查看 7,假设 7 的 key 是 aaa，那么我们在 hash_table["aaa"] 这个过程发生了什么呢？

首先，hash_func("aaa") 进行处理，得到一个地址，就是 4,然后就变成 hash_table[4] 直接查找了。这个过程就是 array 的顺序查找，显然是没有比较过程的。

建议你自己实现一个 hash table，这是个很重要的数据结构。

[xzour]

@raaaaaar array 如果知道 index.是不是等同于哈希的速度呢？ 如果不知道 key 是 aaa，查找 7，是不是等同于顺序查找呢?

[raaaaaar]

@xzour #18 如果知道 index 是多少，那还能叫查找么，肯定就是 O(1) 呀，这就是数组比链表的优点所在嘛。

第二个问题你问得就有问题了，甚至不是一个问题。你需要自己学一下相关的知识。。建议直接用 c 实现一下，其实不难，一个下午就能理解个大概，但是对以后的帮助很大的。

[xzour]

@raaaaaar 看来第二个问题确实很重要，关于数据结构的理解，谢谢，我会抽空实现一下的！

[zhlssg]

@weixiangzhe 为啥你这时间复杂度和 3l 不一样啊

[weixiangzhe]

@zhlssg 我看成双层 for 循环了

[Nerv]

买本算法第四版，各种复杂度给你分析得透透得

[tlday]

这个帖子是完美的 X-Y 问题的例子。
建议回答的人先去看看楼主贴出的原帖，在"""""""暴力遍历"""""""（加粗加重）中，数组转字典可以优化计算速度是不存在的。

什么是 X-Y 问题： https://coolshell.cn/articles/10804.html

[tlday]

看了这么多楼都给我整懵了，看了原帖才发现，根本不是这么回事儿。

[Still4]

遍历每个客户
读取该客户的收款及发票
遍历收款，取发票一条一条核销，一条销完，换另一张发票，未销完，记录发票 INDEX 及剩余金额
最后将结果批量插入数据库。 大概 6000 多条核销明细花了我 30 分钟+ 不可忍受。

看了原贴，根源在于第二步和第三步有过滤
以第二步为例，你要遍历每个客户的数据，对应主楼的 arr2 和 map2 会进行筛选，当然是 map 更快

[jimliang]

一看就没学过数据结构的，转 Dic 的复杂度为 n，以后每次获取的复杂度就是 1 了。

[wangchonglie]

@tlday #24 感谢让我学会了什么叫 X-Y 问题

[fishenal]

我这个半调子程序员都知道，字典是 hash table，hash table 就是把值做 hash，放到 hash 过后这个内存位置，直接去寻址就找到了，array 遍历至少 o （ n ）

[786375312123]

hash table 的底层实现也是 array 。
你的问题描述有点问题

[raaaaaar]

@tlday #24 我今天才和别人说类似的情况，不过没有术语这么精准，没想到自己就完美体验了一次。