golang map键key值valueMapGolangMapMap使用平衡二叉查找树结构实现的哈希表，不会占用多余空间，因为平衡树的缘故，查找元素效率也不是那么地糟糕，所以有时候选择它来做哈希表是特别好的。
如何使用
很简单，执行：
go get -v github.com/hunterhug/gomap
gomap有以下几种用法:
Red-Black Treegomap.New()gomap.NewMap()gomap.NewRBMap()AVL Treegomap.NewAVLMap()核心 API:
// Map 实现
// 被设计为并发安全的
type Map interface {
Put(key string, value interface{}) // 放入键值对
Delete(key string) // 删除键
Get(key string) (interface{}, bool) // 获取键，返回的值value是interface{}类型的，想返回具体类型的值参考下面的方法
GetInt(key string) (int, bool, error) // get value auto change to Int
GetInt64(key string) (int64, bool, error) // get value auto change to Int64
GetString(key string) (string, bool, error) // get value auto change to string
GetFloat64(key string) (float64, bool, error) // get value auto change to string
GetBytes(key string) ([]byte, bool, error) // get value auto change to []byte
Contain(key string) bool // 查看键是否存在
Len() int64 // 查看键值对数量
KeyList() []string // 根据树的层次遍历，获取键列表
KeySortedList() []string // 根据树的中序遍历，获取字母序排序的键列表
Iterator() MapIterator // 迭代器，实现迭代
SetComparator(comparator) // 可自定义键比较器，默认按照字母序
}
// Iterator 迭代器，不是并发安全，迭代的时候确保不会修改Map，否则可能panic或产生副作用
type MapIterator interface {
HasNext() bool // 是否有下一对键值对
Next() (key string, value interface{}) // 获取下一对键值对，迭代器向前一步
}Golangkeyvalue算法比较
Red-Black Tree2log(N+1)AVL Tree1.44log(N+2)-1.328AVL TreeJava/C#/C++Red-Black TreeWindowsAVL Tree例子
下面是一个基本的例子：
package main
import (
"fmt"
"github.com/hunterhug/gomap"
"math/rand"
"time"
)
// 循环的次数，用于随机添加和删除键值对
// 可以修改成1000
var num = 10
func init() {
// 随机数种子初始化
rand.Seed(time.Now().Unix())
}
func main() {
// 1. 新建一个 Map，默认为标准红黑树实现
m := gomap.New()
for i := 0; i < num; i++ {
key := fmt.Sprintf("%d", rand.Int63n(int64(num)))
fmt.Println("add key:", key)
// 2. 放键值对
m.Put(key, key)
}
fmt.Println("map len is ", m.Len())
// 3. 迭代器使用
iterator := m.Iterator()
for iterator.HasNext() {
k, v := iterator.Next()
fmt.Printf("Iterator key:%s,value %v\n", k, v)
}
// 4. 获取键中的值
key := "9"
value, exist := m.Get(key)
if exist {
fmt.Printf("%s exist, value is:%s\n", key, value)
} else {
fmt.Printf("%s not exist\n", key)
}
// 5. 获取键中的值，并且指定类型，因为类型是字符串，所以转成整形会报错
_, _, err := m.GetInt(key)
if err != nil {
fmt.Println(err.Error())
}
// 6. 内部辅助，检查是不是一颗正常的红黑树
if m.Check() {
fmt.Println("is a rb tree,len:", m.Len())
}
// 7. 删除键 ‘9‘ 然后再找 ‘9‘
m.Delete(key)
value, exist = m.Get(key)
if exist {
fmt.Printf("%s exist, value is:%s\n", key, value)
} else {
fmt.Printf("%s not exist\n", key)
}
// 8. 删除很多键值对
for i := 0; i < num; i++ {
key := fmt.Sprintf("%d", rand.Int63n(int64(num)))
fmt.Println("delete key:", key)
m.Delete(key)
}
// 9. 获取键列表
fmt.Printf("keyList:%#v,len:%d\n", m.KeyList(), m.Len())
fmt.Printf("keySortList:%#v,len:%d\n", m.KeySortedList(), m.Len())
// 10. 再次检查是否是一颗正常的红黑树
if m.Check() {
fmt.Println("is a rb tree,len:", m.Len())
}
}性能测试
我进行了压测：
go test -run="bench_test.go" -test.bench=".*" -test.benchmem=1 -count=1 BenchmarkGolangMapPut-4 1000000 1385 ns/op 145 B/op 6 allocs/op BenchmarkRBTMapPut-4 528231 3498 ns/op 113 B/op 6 allocs/op BenchmarkAVLMapPut-4 1000000 3317 ns/op 104 B/op 6 allocs/op BenchmarkAVLRecursionMapPut-4 389806 4563 ns/op 116 B/op 6 allocs/op BenchmarkGolangMapDelete-4 2630281 582 ns/op 15 B/op 1 allocs/op BenchmarkRBTMapDelete-4 2127256 624 ns/op 15 B/op 1 allocs/op BenchmarkAVLMapDelete-4 638918 2256 ns/op 15 B/op 1 allocs/op BenchmarkAVLRecursionMapDelete-4 376202 2813 ns/op 15 B/op 1 allocs/op BenchmarkGolangMapGet-4 9768266 172 ns/op 2 B/op 1 allocs/op BenchmarkRBTMapGet-4 3276406 352 ns/op 2 B/op 1 allocs/op BenchmarkAVLMapGet-4 3724939 315 ns/op 2 B/op 1 allocs/op BenchmarkAVLRecursionMapGet-4 2550055 462 ns/op 2 B/op 1 allocs/op BenchmarkGolangMapRandom-4 1000000 2292 ns/op 163 B/op 8 allocs/op BenchmarkRBTMapRandom-4 244311 4635 ns/op 136 B/op 8 allocs/op BenchmarkAVLMapRandom-4 488001 5879 ns/op 132 B/op 8 allocs/op BenchmarkAVLRecursionMapRandom-4 211246 5411 ns/op 138 B/op 8 allocs/op
Mapgolang mapMap空间换时间，还是时间换空间，这是一个问题。