Chr*_*gis 12
哈希表至少包含数组和哈希函数.将对象添加到表中时,将在对象上计算散列函数,并将其存储在数组中计算的相应值的索引处.例如,如果hash(obj) = 2那么arr[2] = obj.
哈希表上的平均插入/查找是O(1).
但是,当对象计算相同的哈希值时,可能会发生冲突.
在一般情况下,在阵列的每个索引处存在"桶"以处理这些冲突.意思是,所有三个对象都存储在哈希表索引处的某些其他数据结构(可能是链表或另一个数组)中.
因此,在哈希表上查找的最坏情况是O(n)因为存储在哈希表中的所有对象可能已经冲突并存储在同一个桶中.
ggb*_*nch 10
散列表散列您的密钥并将其放入数组中.
例如,hash(x)= 3,其中x是你的密钥.然后表格将其放入数组[3].从数组访问是O(1).