查看原文

本文介绍了 Go 语言如何实现 Map 的泛型，并对比了 C++ STL 和 Java 的实现。

• HashMap: 一种查询时间复杂度近乎 O(1), 最差为 O(N) 的数据结构，需提供 hash function。O(N) 估计也真是运气背到家了，所有 Key 都哈希碰撞。
  • hash function 一定是一个产出固定长度数据的函数
• C++ STL std::unordered_map 在编译时就把类型模板编好了，所以编译时就知道每个 map 的 key 类型。
• Java java.util.Hashmap 要对原子类型做 boxing。由于所有 java.lang.Object 的子类都有 hashCode 所以它们都可以被塞入 Entry。HashMap 是 Entry 的链表.
• Go 运行时不用 interface{} 的信息，编译时也不做code generation。它的方案是：将诸如 v := m["key"] 这样的代码写成 runtime.mapaccess1(m, "key", &v), 而 mapaccess1 有如下签名

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

Trick在于 *maptype 这种数据结构，它存储了 key, value 的类型。不像 C++ 完整地生成了多型 map 的实现，Go 只生成了多型的 maptype，这样我们就只需要一份 map 的实现，在运行时读取 maptype 的大小完成 hash 运算。