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

[xzour]

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

[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 我今天才和别人说类似的情况，不过没有术语这么精准，没想到自己就完美体验了一次。