Golang Map efficiently vs other language

原文链接

主要是介绍没有泛型的情况下，hashmap实现上的一些高效考虑

Go’s map is a hashmap

hash function

• The first is stability. The hash function must be stable. Given the same key, your hash function must return the same answer
• The second property is good distribution. Given two near identical keys, the result should be wildly different

In this case our hashmap has eight buckets (as this is the value that the Go implementation uses) and each bucket can hold up to eight entries each (again drawn from the Go implementation)

a hash map four properties

1. You need a hash function for the key.
2. You need an equality function to compare keys.
3. You need to know the size of the key and,
4. You need to know the size of the value because these affect the size of the bucket structure, which the compiler needs to know, as you walk or insert into that structure, how far to advance in memory.

java

boxing: boolean, int, short, long, byte, char, float, and double to java.lang.Object

c++同java实现hashmap的优缺点

c++

• key和value的大小，在compile阶段就知道
• 可以进行inlineing
• 速度快
• 编译和代码上慢，要有不同的types

java

• 天然有泛型的含义，一切都是object
• 同样也是缺点，boxing等方式，会增大gc的概率
• Buckets are stored as linked lists, not sequential arrays

golang的实现

While we have the container/{list,heap} packages which do use the empty interface, the runtime’s map implementation does not use interface{}.

v := m["key"]     → runtime.mapaccess1(m, ”key", &v)
v, ok := m["key"] → runtime.mapaccess2(m, ”key”, &v, &ok)
m["key"] = 9001   → runtime.mapinsert(m, ”key", 9001)
delete(m, "key")  → runtime.mapdelete(m, “key”)

实际上针对channel的操作？

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

在mapaccess中，指明maptype，不同于c++部分针对所有的map有不同的实现，golang部分，在compile阶段生成maptype字段

type maptype struct {
        typ           _type
        key         *_type
        elem        *_type
        bucket        *_type // internal type representing a hash bucket

        hmap          *_type // internal type representing a hmap
        keysize       uint8  // size of key slot
        indirectkey   bool   // store ptr to key instead of key itself
        valuesize     uint8  // size of value slot
        indirectvalue bool   // store ptr to value instead of value itself
        bucketsize    uint16 // size of bucket
        reflexivekey  bool   // true if k==k for all keys
        needkeyupdate bool   // true if we need to update key on overwrite

}

mapaccess的功能如下：

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead

// it will return a reference to the zero object for the value type if

// the key is not in the map.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {

        if h == nil || h.count == 0 {
                return unsafe.Pointer(&zeroVal[0])

        }
        alg := t.key.alg
        hash := alg.hash(key, uintptr(h.hash0))
        m := bucketMask(h.B)
        b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))