我在《Go编程语言》(The Go Programming Language)中读到,"可以检索给定的密钥……平均使用恒定数量的密钥比较,无论哈希表有多大."不过,我不确定这对其内部实施意味着什么.这是否意味着它会搜索每个键,直到找到匹配项,还是内部使用了某种类型的二进制(或其他)搜索算法?
例如,如果我有一个有2,000个键的映射,它"平均"需要查看1,000才能找到匹配项,还是像二分法搜索那样只查看11(Log2n)?
我在《Go编程语言》(The Go Programming Language)中读到,"可以检索给定的密钥……平均使用恒定数量的密钥比较,无论哈希表有多大."不过,我不确定这对其内部实施意味着什么.这是否意味着它会搜索每个键,直到找到匹配项,还是内部使用了某种类型的二进制(或其他)搜索算法?
例如,如果我有一个有2,000个键的映射,它"平均"需要查看1,000才能找到匹配项,还是像二分法搜索那样只查看11(Log2n)?
本机映射类型使用hash table实现.它在键上使用散列函数生成数据数组的索引.因此,一般来说,大多数动作发生在O(1)时间内.这通常是正确的,因为一些键在散列时可能会产生相同的索引,称为冲突,然后必须进行特殊处理.
Hash tables个很酷!