c++ - 为什么 '*' 比散列查找更快，C++

Question

刚学数据结构，谁能告诉我hash为什么慢，谢谢!

这道题来自 LeetCode: https://leetcode.com/problems/happy-number/

bool isHappy(int n) {
    unordered_map<int, int> M;
    M[0] = 0, M[1] = 1, M[2] = 4, M[3] = 9, M[4] = 16, M[5] = 25,\
    M[6] = 36, M[7] = 49, M[8] = 64, M[9] = 81;
    int temp, mark = 0;   //temp is next n, mark is for detect circle 
    while(n){
        temp = 0;
        if(n == 1) return true;
        if(n < 10){
            if(mark == n)
               return false;
            mark = n;
        }
        //calc next n
        while(n){
            temp += (n%10)*(n%10); // 4 ms
            //temp += M[n%10];       // 8 ms
            n /= 10;
        }
        n = temp;
    }
}

Answer 1

为什么不呢？哈希是有效的，因为它的平均提取时间是恒定的。就是这样。

不能保证它比 * 更快。请注意，您的 key 通常不直接用作哈希表的 key (这称为“直接地址表”，它有其自身的缺点)。一般来说，从你的key到hash key有一个计算:hash_key = hash(your_key)。所以时间完全取决于 hash 是如何实现的。一旦哈希键被计算出来，这只是索引表的问题。

事实上，最常见的散列实现涉及模数 (%) 运算，这很可能比“*”慢。试想一下:C = A % B 等同于 C = A – B * (A/B)。

您可能会问两个 %(如 * 情况)与一个 %(如 map 情况)怎么样？我的猜测是 n%10 被优化为在第一种情况下只计算一次。