Day.14 Hash map II

今天要把上一篇讲的hash map写成code!

struct

type Node struct {
	key  string
	val  int
	next *Node
}

type HashMap struct {
	bucket [4]*Node
	len    int
}

hash function

func (h *HashMap) hashKey(key string) int {
	// 先把string转成 ASCII code再 % 桶子的大小
	return int(key[0]) % len(h.bucket)
}

get

func (h *HashMap) Get(key string) (val int, exist bool) {
	node := h.bucket[h.hashKey(key)]
	// 找不到
	if node == nil {
		return 0, false
	}

	// 找到同一样的key 再回传
	for node != nil {
		if node.key == key {
			return node.val, true
		}

		node = node.next
	}

	return 0, false
}

set

func (h *HashMap) Set(key string, val int) {
	hashkey := h.hashKey(key)
	if h.bucket[hashkey] == nil {
		h.bucket[hashkey] = &Node{
			key: key,
			val: val,
		}
		h.len++

		return
	}

	// 寻找是否有一样的key的节点，如果有就update
	node := h.bucket[hashkey]
	for node != nil {
		if node.key == key {
			node.val = val
			return
		}

		node = node.next
	}

	// 没找到一样key的
	// 把新的节点放在第一个位置
	h.bucket[hashkey] = &Node{
		key:  key,
		val:  val,
		next: h.bucket[hashkey],
	}
	h.len++
}

delete

func (h *HashMap) Delete(key string) {
	node := h.bucket[h.hashKey(key)]
	// 找不到
	if node == nil {
		return
	}

	// 删的是第一个节点
	if node.key == key {
		h.bucket[h.hashKey(key)] = nil
		h.len--
		return
	}

	// 寻找节点
	prev := node
	node = node.next
	for node != nil {
		if node.key == key {
			// 删除
			prev.next = node.next
			h.len--
			return
		}

		prev = node
		node = node.next
	}
}

明天来解leetcode!