当我们在哈希表中插入/查找键时,教科书上说它的时间复杂度为O(1)。然而,如何可能实现O(1)的查找时间呢?如果哈希表将键存储在向量中,则需要O(N)的时间,如果存储在二叉树中,则需要O(logN)的时间。我就是无法想象某些数据结构可以具有O(1)的访问时间。
谢谢!
当我们在哈希表中插入/查找键时,教科书上说它的时间复杂度为O(1)。然而,如何可能实现O(1)的查找时间呢?如果哈希表将键存储在向量中,则需要O(N)的时间,如果存储在二叉树中,则需要O(logN)的时间。我就是无法想象某些数据结构可以具有O(1)的访问时间。
谢谢!
哈希表会将您的键进行哈希处理,并放入数组中。
例如,假设哈希(x) = 3,其中x是您的键。然后哈希表会将其放入array[3]中。从数组访问的时间复杂度为O(1)。
最基本的哈希表由数组和哈希函数组成。将对象添加到表中时,计算对象的哈希函数,并将其存储在该值对应的索引处的数组中。例如,如果hash(obj) = 2
,则arr[2] = obj
。
哈希表上的平均插入/查找时间为O(1)
。
然而,当对象计算出相同的哈希值时,可能会发生冲突。
在一般情况下,数组每个索引处都有“桶”来处理这些冲突。这意味着所有三个对象都存储在哈希表索引处的某些其他数据结构(可能是链表或另一个数组)中。
因此,哈希表查找的最坏情况是O(n)
,因为所有在哈希表中存储的对象都可能发生冲突并存储在同一个桶中。
O(n)
гҖӮиҖғиҷ‘пјҡhash(x) = 3
пјҢhash(y) = 3
пјҢhash(z) = 3
зӯүзӯүгҖӮ - Chris Dargis