iT邦幫忙

2021 iThome 鐵人賽

DAY 14
0
Software Development

算法30天系列 第 14

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!


上一篇
Day.13 Hash map
下一篇
Day. 15 Bulls and Cows
系列文
算法30天30

尚未有邦友留言

立即登入留言