码农桃花源
  • README
  • channel
    • 06 - 从一个关闭的 channel 仍然能读出数据吗
    • 12 - channel 有哪些应用
    • 08 - 如何优雅地关闭 channel
    • 10 - channel 在什么情况下会引起资源泄漏
    • 00 - 什么是 CSP
    • channel 底层的数据结构是什么
    • 09 - channel 发送和接收元素的本质是什么
    • 11 - 关于 channel 的 happened-before 有哪些
    • 04 - 向 channel 发送数据的过程是怎样的
    • 03 - 从 channel 接收数据的过程是怎样的
    • 07 - 操作 channel 的情况总结
    • 05 - 关闭一个 channel 的过程是怎样的
  • map
    • map 的底层实现原理是什么
    • 可以边遍历边删除吗
    • map 的删除过程是怎样的
    • 可以对 map 的元素取地址吗
    • 如何比较两个 map 相等
    • 如何实现两种 get 操作
    • map 是线程安全的吗
    • map 的遍历过程是怎样的
    • map 中的 key 为什么是无序的
    • float 类型可以作为 map 的 key 吗
    • map 的赋值过程是怎样的
    • map 的扩容过程是怎样的
  • interface
    • iface 和 eface 的区别是什么
    • Go 接口与 C++ 接口有何异同
    • 如何用 interface 实现多态
    • 接口转换的原理
    • Go 语言与鸭子类型的关系
    • 值接收者和指针接收者的区别
    • 接口的构造过程是怎样的
    • 编译器自动检测类型是否实现接口
    • 类型转换和断言的区别
    • 接口的动态类型和动态值
  • 标准库
    • context
      • context.Value 的查找过程是怎样的
      • context 如何被取消
      • context 有什么作用
      • context 是什么
    • unsafe
      • 如何利用unsafe包修改私有成员
      • Go指针和unsafe.Pointer有什么区别
      • 如何实现字符串和byte切片的零拷贝转换
      • 如何利用unsafe获取slice&map的长度
  • goroutine 调度器
    • M 如何找工作
    • goroutine 调度时机有哪些
    • 什么是 go shceduler
    • goroutine 如何退出
    • 描述 scheduler 的初始化过程
    • 什么是workstealing
    • mian gorutine 如何创建
    • 什么是M:N模型
    • g0 栈何用户栈如何切换
    • schedule 循环如何运转
    • GPM 是什么
    • schedule 循环如何启动
    • sysmon 后台监控线程做了什么
    • goroutine和线程的区别
    • 一个调度相关的陷阱
  • 编译和链接
    • 逃逸分析是怎么进行的
    • GoRoot 和 GoPath 有什么用
    • Go 编译链接过程概述
    • Go 编译相关的命令详解
    • Go 程序启动过程是怎样的
  • 反射
    • Go 语言中反射有哪些应用
    • 什么情况下需要使用反射
    • 如何比较两个对象完全相同
    • Go 语言如何实现反射
    • 什么是反射
  • 数组和切片
    • 数组和切片有什么异同
    • 切片作为函数参数
    • 切片的容量是怎样增长的
  • GC
    • GC
Powered by GitBook
On this page

Was this helpful?

  1. map

float 类型可以作为 map 的 key 吗

从语法上看,是可以的。Go 语言中只要是可比较的类型都可以作为 key。除开 slice,map,functions 这几种类型,其他类型都是 OK 的。具体包括:布尔值、数字、字符串、指针、通道、接口类型、结构体、只包含上述类型的数组。这些类型的共同特征是支持 == 和 != 操作符,k1 == k2 时,可认为 k1 和 k2 是同一个 key。如果是结构体,只有 hash 后的值相等以及字面值相等,才被认为是相同的 key。很多字面值相等的,hash出来的值不一定相等,比如引用。

顺便说一句,任何类型都可以作为 value,包括 map 类型。

来看个例子:

func main() {
    m := make(map[float64]int)
    m[1.4] = 1
    m[2.4] = 2
    m[math.NaN()] = 3
    m[math.NaN()] = 3

    for k, v := range m {
        fmt.Printf("[%v, %d] ", k, v)
    }

    fmt.Printf("\nk: %v, v: %d\n", math.NaN(), m[math.NaN()])
    fmt.Printf("k: %v, v: %d\n", 2.400000000001, m[2.400000000001])
    fmt.Printf("k: %v, v: %d\n", 2.4000000000000000000000001, m[2.4000000000000000000000001])

    fmt.Println(math.NaN() == math.NaN())
}

程序的输出:

[2.4, 2] [NaN, 3] [NaN, 3] [1.4, 1] 
k: NaN, v: 0
k: 2.400000000001, v: 0
k: 2.4, v: 2
false

例子中定义了一个 key 类型是 float 型的 map,并向其中插入了 4 个 key:1.4, 2.4, NAN,NAN。

打印的时候也打印出了 4 个 key,如果你知道 NAN != NAN,也就不奇怪了。因为他们比较的结果不相等,自然,在 map 看来就是两个不同的 key 了。

接着,我们查询了几个 key,发现 NAN 不存在,2.400000000001 也不存在,而 2.4000000000000000000000001 却存在。

有点诡异,不是吗?

接着,我通过汇编发现了如下的事实:

当用 float64 作为 key 的时候,先要将其转成 unit64 类型,再插入 key 中。

具体是通过 Float64frombits 函数完成:

// Float64frombits returns the floating point number corresponding
// the IEEE 754 binary representation b.
func Float64frombits(b uint64) float64 { return *(*float64)(unsafe.Pointer(&b)) }

也就是将浮点数表示成 IEEE 754 规定的格式。如赋值语句:

0x00bd 00189 (test18.go:9)      LEAQ    "".statictmp_0(SB), DX
0x00c4 00196 (test18.go:9)      MOVQ    DX, 16(SP)
0x00c9 00201 (test18.go:9)      PCDATA  $0, $2
0x00c9 00201 (test18.go:9)      CALL    runtime.mapassign(SB)

"".statictmp_0(SB) 变量是这样的:

"".statictmp_0 SRODATA size=8
        0x0000 33 33 33 33 33 33 03 40
"".statictmp_1 SRODATA size=8
        0x0000 ff 3b 33 33 33 33 03 40
"".statictmp_2 SRODATA size=8
        0x0000 33 33 33 33 33 33 03 40

我们再来输出点东西:

package main

import (
    "fmt"
    "math"
)

func main() {
    m := make(map[float64]int)
    m[2.4] = 2

    fmt.Println(math.Float64bits(2.4))
    fmt.Println(math.Float64bits(2.400000000001))
    fmt.Println(math.Float64bits(2.4000000000000000000000001))
}
4612586738352862003
4612586738352864255
4612586738352862003

转成十六进制为:

0x4003333333333333
0x4003333333333BFF
0x4003333333333333

和前面的 "".statictmp_0 比较一下,很清晰了吧。2.4 和 2.4000000000000000000000001 经过 math.Float64bits() 函数转换后的结果是一样的。自然,二者在 map 看来,就是同一个 key 了。

再来看一下 NAN(not a number):

// NaN returns an IEEE 754 ``not-a-number'' value.
func NaN() float64 { return Float64frombits(uvnan) }

uvan 的定义为:

uvnan    = 0x7FF8000000000001

NAN() 直接调用 Float64frombits,传入写死的 const 型变量 0x7FF8000000000001,得到 NAN 型值。既然,NAN 是从一个常量解析得来的,为什么插入 map 时,会被认为是不同的 key?

这是由类型的哈希函数决定的,例如,对于 64 位的浮点数,它的哈希函数如下:

func f64hash(p unsafe.Pointer, h uintptr) uintptr {
    f := *(*float64)(p)
    switch {
    case f == 0:
        return c1 * (c0 ^ h) // +0, -0
    case f != f:
        return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN
    default:
        return memhash(p, h, 8)
    }
}

第二个 case,f != f 就是针对 NAN,这里会再加一个随机数。

这样,所有的谜题都解开了。

由于 NAN 的特性:

NAN != NAN
hash(NAN) != hash(NAN)

因此向 map 中查找的 key 为 NAN 时,什么也查不到;如果向其中增加了 4 次 NAN,遍历会得到 4 个 NAN。

最后说结论:float 型可以作为 key,但是由于精度的问题,会导致一些诡异的问题,慎用之。

关于当 key 是引用类型时,判断两个 key 是否相等,需要 hash 后的值相等并且 key 的字面量相等。由 @WuMingyu 补充的例子:

func TestT(t *testing.T) {
    type S struct {
        ID    int
    }
    s1 := S{ID: 1}
    s2 := S{ID: 1}

    var h = map[*S]int {}
    h[&s1] = 1
    t.Log(h[&s1])
    t.Log(h[&s2])
    t.Log(s1 == s2)
}

test output:

=== RUN   TestT
--- PASS: TestT (0.00s)
    endpoint_test.go:74: 1
    endpoint_test.go:75: 0
    endpoint_test.go:76: true
PASS

Process finished with exit code 0
Previousmap 中的 key 为什么是无序的Nextmap 的赋值过程是怎样的

Last updated 5 years ago

Was this helpful?