乐趣区

关于leetcode:Leetcode刷题笔记哈希

哈希表实践根底

  • 用来疾速判断某个原生是否在汇合内 (疾速查找)
  • 哈希函数将传入的 key 映射到符号表的索引上
  • 哈希抵触解决多个 key 映射到符号表雷同索引上的问题,罕用的解决办法有拉链法和线性探测法
  • c++ stl 中有四种常见的哈希构造
  • 数组 std::array
  • 汇合 std::set std::multiset std::unordered_set
  • 映射 std::map std::multimap std::unordered_map
汇合 底层实现 是否有序 增删查的效率
std::set RB-Tree O(logn)
std::multiset RB-Tree O(logn)
std::unordered_set Hash O(1)
std::unordered_multiset Hash O(1)
映射 底层实现 是否有序 增删查的效率
std::map RB-Tree O(logn)
std::multimap RB-Tree O(logn)
std::unordered_map Hash O(1)
std::unordered_multimap Hash O(1)
退出移动版