为何哈希表解法查找数组奇数次元素的时间复杂度为O(N)？

你这里的核心误解是对HashMap的put()、get()和containsKey()操作的时间复杂度判断错了——这些操作的平均时间复杂度是O(1)，而不是O(N)，这也是哈希表这种数据结构的核心优势之一。

先回顾一下问题场景：我们要找出数组int arr[]= {1, 2, 3, 2, 3, 1, 3}中出现奇数次的元素（结果是3），采用的HashMap解法代码如下：

// function to find the element occurring odd 
// number of times 
static int getOddOccurrence(int arr[], int n) { 
    HashMap<Integer,Integer> hmap = new HashMap<>(); 
    // Putting all elements into the HashMap 
    for(int i = 0; i < n; i++) { 
        if(hmap.containsKey(arr[i])) { 
            int val = hmap.get(arr[i]); 
            // If array element is already present then 
            // increase the count of that element. 
            hmap.put(arr[i], val + 1); 
        } else 
            // if array element is not present then put 
            // element into the HashMap and initialize 
            // the count to one. 
            hmap.put(arr[i], 1); 
    } 
    // Checking for odd occurrence of each element present 
    // in the HashMap 
    for(Integer a:hmap.keySet()) { 
        if(hmap.get(a) % 2 != 0) 
            return a; 
    } 
    return -1; 
}

接下来拆解时间复杂度：

• 第一个遍历数组的循环：执行N次（N是数组长度），每次循环里的containsKey()、get()、put()操作，在哈希表的平均情况下都是O(1)——哈希表通过哈希函数直接计算出元素对应的桶位置，不需要遍历整个表，所以单次操作的时间是常数级。这部分的总时间复杂度是O(N * 1) = O(N)。
• 第二个遍历HashMap键集合的循环：HashMap中最多会存储N个不同的键（如果数组所有元素都不重复），但实际数量肯定≤N，每个get()操作同样是平均O(1)，所以这部分的时间复杂度也是O(N)。

把两部分加起来，总时间复杂度是O(N) + O(N) = O(N)，完全符合题目要求的时间复杂度。

需要补充说明的是：哈希表的最坏情况时间复杂度确实是O(N)（比如所有元素的哈希值都相同，导致所有元素都落在同一个桶里，变成链表结构），但这种情况在实际应用中非常罕见，而且现代编程语言的HashMap实现（比如Java 8及以后的版本）会在链表长度超过阈值时自动转为红黑树，把最坏情况的时间复杂度降到O(logN)，就算是这种情况，整体时间复杂度也会是O(N logN)，远低于你担心的O(N²)。

所以结论是，因为HashMap的核心操作平均时间复杂度是O(1)，所以整个算法的时间复杂度是O(N)。

内容的提问来源于stack exchange，提问作者Plain_Dude_Sleeping_Alone