什么是哈希表

散列表(Hash Table,哈希表),是根据键值(key,value)直接进行访问的数据结构。我们可以通过给定的key值计算目标value。

普通列表只能通过下标获取目标位置的值,但哈希表可以根据给定的key获取目标值。

列表查找中,一般都使用二分查找,时间复杂度为🍢哈希表 - 图1,并且这只适用于有序列表。普通的列表只能采用遍历查找,时间复杂度为🍢哈希表 - 图2。而理想的哈希表查找时间复杂度仅为🍢哈希表 - 图3

哈希表的实现