TLE 同时使用 hashmap 但不使用 map[256]={}
TLE whileusing hashmap but not while using map[256]={}
我正在做 this code，当我尝试使用像 unordered_map<char,int> m 这样的哈希图解决这个问题时，我得到 TLE（超出时间限制），但是每当我使用hashamp 这样 map[256]={0} 然后我的代码运行正常。为什么会这样？ unordered_map 的工作方式与访问时间复杂度为 O(1) 的数组不同吗？
unordered_map 是渐进的 O(1) 但实际上它通常比数组慢得多。
这是出于几个原因。哈希函数需要一些时间来计算数组不需要的内容，并且您需要处理哈希冲突，相比之下，这可能非常昂贵。数组是连续的内存，可以大大减少缓存未命中。
主要的收获是渐近 O 表示法是性能的近似值，但仅适用于大输入并且不关心常量。所以一个 O(1) 可以比另一个 O(1) 快 100 倍。
另一个要点是，如果你没有充分的理由不这样做，你应该总是更喜欢数组或向量而不是其他数据结构。
如果您的 Key-Space 对于数组来说太大了，例如 unordered_map<long long, int>.
，哈希映射会很好
我正在做 this code，当我尝试使用像 unordered_map<char,int> m 这样的哈希图解决这个问题时，我得到 TLE（超出时间限制），但是每当我使用hashamp 这样 map[256]={0} 然后我的代码运行正常。为什么会这样？ unordered_map 的工作方式与访问时间复杂度为 O(1) 的数组不同吗？
unordered_map 是渐进的 O(1) 但实际上它通常比数组慢得多。
这是出于几个原因。哈希函数需要一些时间来计算数组不需要的内容，并且您需要处理哈希冲突，相比之下，这可能非常昂贵。数组是连续的内存，可以大大减少缓存未命中。
主要的收获是渐近 O 表示法是性能的近似值，但仅适用于大输入并且不关心常量。所以一个 O(1) 可以比另一个 O(1) 快 100 倍。
另一个要点是，如果你没有充分的理由不这样做，你应该总是更喜欢数组或向量而不是其他数据结构。
如果您的 Key-Space 对于数组来说太大了，例如 unordered_map<long long, int>.