我在《Go编程语言》(The Go Programming Language)中读到,"可以检索给定的密钥……平均使用恒定数量的密钥比较,无论哈希表有多大."不过,我不确定这对其内部实施意味着什么.这是否意味着它会搜索每个键,直到找到匹配项,还是内部使用了某种类型的二进制(或其他)搜索算法?

例如,如果我有一个有2,000个键的映射,它"平均"需要查看1,000才能找到匹配项,还是像二分法搜索那样只查看11(Log2n)?

推荐答案

本机映射类型使用hash table实现.它在键上使用散列函数生成数据数组的索引.因此,一般来说,大多数动作发生在O(1)时间内.这通常是正确的,因为一些键在散列时可能会产生相同的索引,称为冲突,然后必须进行特殊处理.

Hash tables个很酷!

Go相关问答推荐

Go 1.22 net/http群组路由

如何在AWS SDK Go v2 STS上正确使用重试

Golang Gorm Fiber - 如何将定义为别名的名称发送到索引模板?

在 Go 中将元数据从一个 JPEG 复制到另一个

Go:如何在不加载正文的情况下创建 http 代理通行证

Golang Docker Selenium Chrome

在 Windows 11 上运行 go mod tidy 时的 gitlab 权限问题

AWS Lambda 中的 Websocket URL 超时达到错误

更改多对多连接表的名称

在 Cloud Run 中找不到默认凭据

Golang crypto/rand 线程安全吗?

在反向 GORM 中创建查询有一个关系

将 big.Int 转换为 [2]int64,反之亦然和二进制补码

当函数返回一个函数时,为什么 Go 泛型会失败?

不能在 *gorm.db 而不是 gorm.db 上使用 WithContext(ctx) 方法

在 Go GRPC 服务器流式拦截器上修改元数据

使用 `didip/tollbooth` 限制每小时最大请求数

有没有办法判断值是否满足接口中定义的类型约束?

Go AST:获取所有 struct

Golang 使用 docker 将敏感数据作为参数传递