关于哈希表的一些看法一、为什么需要哈希表我们都知道通过数组查找某一个特定元素时是依靠下标从0到n-1进行遍历的。显而易见遍历一维数组的时间复杂度是O(n)遍历二维数组的时间复杂度则是O(n²)那么有没有一种方法可以在更短的时间内完成查找呢这时哈希表Hash Table出现了。二、C中的哈希表在 C 中常用的哈希表结构是unordered_map从英文名称来看map意为“映射”unordered意为“无序”结合起来unordered_map就是“无序映射”的意思。顾名思义我们可以把它理解为一个通过映射关系存储数据的数据结构。三、为什么哈希表查找速度快既然哈希表也类似于数组为什么它的查找时间复杂度可以达到平均O(1)呢原因在于哈希表拥有一种特殊的映射机制——哈希函数。普通数组查找普通数组查找元素时需要通过下标逐个遍历a[0], a[1], a[2]......a[n-1]时间复杂度O(n)哈希表查找哈希表并不需要遍历。它会通过哈希函数根据key键计算出对应的存储位置然后直接访问目标元素。可以这样理解数组下标 → 元素哈希表key → value其中key键类似数组中的下标用于定位数据value值类似数组中的元素是实际存储的数据四、unordered_map 示例例如unordered_mapint,intmp;mp[3]100;其中3是 key100是 value当我们访问mp[3]时哈希表会通过内部的哈希函数快速找到对应的位置从而得到 value。因此哈希表在平均情况下的查找复杂度为 O(1)。五、哈希冲突问题不过哈希表也并不是完全没有问题。在理想情况下一个 key → 一个唯一的位置但是由于哈希函数的映射范围有限有时不同的 key 可能会映射到同一个存储位置。这种情况称为哈希冲突Hash Collision哈希冲突示例假设哈希函数为key % 5现在有两个 key3 % 5 3 8 % 5 3虽然3 ≠ 8但是经过哈希函数计算后得到相同的哈希地址这就是哈希冲突。注意哈希冲突并不是多个 key 对应同一个 value。而是多个 key 经过哈希函数计算后得到了相同的存储位置。六、解决哈希冲突的方法为了解决哈希冲突哈希表通常采用以下方法1. 链地址法将发生冲突的数据存储在同一个链表中。例如地址3 3 → 8 → 132. 开放寻址法当当前位置已经被占用时寻找其他空位置进行存储。在 C 标准库中unordered_map已经帮我们实现好了哈希函数冲突处理机制我们只需要直接调用即可。七、自定义哈希函数当然我们也可以根据需求自定义哈希函数实现更加特殊的映射规则用于解决一些特殊场景的问题。八、哈希表的其他形式实际上哈希表还有其他形式例如unordered_set在算法题中也有非常广泛的应用。九、哈希表在算法中的应用掌握哈希表后可以更好地理解和解决两数之和字符频率统计滑动窗口缓存设计等经典算法问题。总结哈希表的核心思想利用哈希函数建立 key 和存储位置之间的映射从而实现快速查找。相比数组数据结构查找方式时间复杂度数组遍历查找O(n)哈希表哈希映射定位平均 O(1)掌握哈希表是解决大量算法问题的重要基础。