Hash为什么可以降低查找的时间复杂度

先看不用 Hash 的情况假设有 100 个用户id1001 id1002 id1003 ... id1100如果用数组存储[1001][1002][1003]......[1100]现在查找id1088最坏情况需要1001 1002 1003 ... 1088一直比较下去。时间复杂度O(n)O(n)O(n)100 个元素最坏比较 100 次。使用 Hash例如int index hash(id);假设hash(1088)37那么数据直接放到table[37]查找的时候也是hash(1088)37直接访问table[37]数组下标访问O(1)整个过程中没有遍历。结论Hash不是压缩数据。它只是建立了一种key → 数组下标的映射。