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

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