hashmap的golang实现

HashMap=数组+链表

这是一个简单的HashMap的结构图：

当我们存储一个键值对时，HashMap会首先通过一个哈希函数将key转换为数组下标，真正的key-value是存储在该数组对应的链表里。

HashMap的数组往往是有限的，那当要存储的键值对很多数组不够或者两个键值对哈希运算后的值相同时，不就会有不同的键值对存储在同一个数组下吗？是的，这个就叫做哈希碰撞。当发生哈希碰撞时，键值对就会存储在该数组对应链表的下一个节点上。

尽管这样，HashMap的操作效率也是很高的。当不存在哈希碰撞时查找复杂度为O(1)，存在哈希碰撞时复杂度为O(N)。所以，但从性能上讲HashMap中的链表出现越少，性能越好；当然，当存储的键值对非常多时，从存储的角度链表又能分担一定的压力。

下面看下hashMap的golang简单实现：

/**
*
* hashMap的golang实现
*
**/

package main

//桶的格子数
const BucketsCount = 20

//node节点
type Node struct {
	Next *Node
	Data Value
}

//node节点存放的实际对象
type Value struct {
	Key   string
	Value interface{}
}

//hashMap 桶
type HashMap struct {
	Buckets [BucketsCount]*Node //存在node节点的数组
}

//新建一个hashMap桶
func NewHashMap() HashMap {
	hashMap := HashMap{}
	for i := 0; i < BucketsCount; i++ {
		hashMap.Buckets[i] = NewEmptyNode()
	}

	return hashMap
}

//自定义hash算法获取key
func getBucketKey(key string) int {
	length := len(key)
	sum := 0
	for i := 0; i < length; i++ {
		sum = sum + int(key[i])
	}
	return sum % BucketsCount
}

//在hashMap桶中新加一个节点
func (h *HashMap) put(data Value) {
	//获取index
	index := getBucketKey(data.Key)
	node := h.Buckets[index]
	//判断数组节点是否是空节点
	if node.Data.Value == nil {
		node.Data = data
	} else {
		//发生了hash碰撞,往该槽的链表尾巴处添加存放该数据对象的新节点
		last := node
		for last.Next != nil {
			last = last.Next
		}
		newNode := &Node{Data: data, Next: nil}
		last.Next = newNode
	}
}

//从hashMap中获取某个key的值
func (h *HashMap) get(key string) interface{} {
	//获取index
	index := getBucketKey(key)
	if h.Buckets[index].Data.Key == key {
		return h.Buckets[index].Data.Value
	}
	if h.Buckets[index].Next == nil {
		return nil
	}
	next := h.Buckets[index].Next
	for {
		if next.Data.Key == key {
			return next.Data.Value
		}
		if next.Next == nil {
			return nil
		}
		next = next.Next
	}
	return nil
}

//创建一个空node
func NewEmptyNode() *Node {
	node := &Node{}
	node.Data.Key = ""
	node.Data.Value = nil
	node.Next = nil
	return node
}

func main() {
	myMap := NewHashMap()
	data1 := Value{"001", 1}
	myMap.put(data1)
	data2 := Value{"002", "this is string"}
	myMap.put(data2)
	fmt.Println(myMap.get("002"))
}