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

[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 看来第二个问题确实很重要，关于数据结构的理解，谢谢，我会抽空实现一下的！