hash
初学感受
hash 的主要作用是把一串字符或者数字本不能储存在数组中的数据类型进行 hash 之后储存至数组之中,以便操作,当然平衡树也可以实现此操作——map
,但是平衡树查询和改变需要 \(O(n \log n)\),但是 hash 的 unordered_map
只需要 \(O(n)\) 的改变和查询的 \(O(1)\),也就是说 hash 可以很大程度上优化时间复杂度。
hash 实际应用:
-
查找相同字符串,由于 hash 值只需要 \(O(1)\),但是直接比较字符串就需要 \(O(n)\),所以在 \(n\) 较大的情况下可以使用 hash。
-
hash 可以优化 dp 或者 搜索,可以把本来不可以储存的状态储存。
hash 的不可使用点:
数字按照一定规律排列,这时使用 hash 会使得 hash冲撞 变多,引起代码的错误。