哈希表插入/查找时间存疑：长键哈希为何复杂度为O(k)却实际很快

• 哈希表插入的O(1)时间复杂度，是建立在哈希码计算时间为恒定常数的假设上的。
• 像keccak256、SHA这类哈希函数，计算哈希值时必须完整遍历整个键的所有字节（长度为k），这个过程的时间复杂度是O(k)。
• 你实际测试时感觉快，是因为现代硬件处理几万个字节的速度极快，但从算法复杂度的理论定义来看，这个时间是和键的长度k线性相关的，不是真正的常数时间。
• 哈希表插入的总耗时包含哈希计算和后续的桶操作，当哈希计算占主导且为O(k)时，整体插入时间就会从理论上的O(1)变为O(k)。

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