2.2 hashmap

1. What It Is

• K-V pairs

2. Binary Search Tree Implementation

2.1. Data Structure

• Binary search tree

2.2. API

type IMap interface {
	// Print the map
	String() string
	// Number of elements in the map
	Length() int
	// Whether the map is empty
	IsEmpty() bool
	// Add an element to the map
	Add(key model.Comparable, value interface{})
	// Whether the map contains key
	Contains(key model.Comparable) bool
	// Get the value corresponding to key
	Get(key model.Comparable) (interface{}, bool)
	// Update the value corresponding to key
	Set(key model.Comparable, value interface{})
	// Delete the element corresponding to key
	Remove(key model.Comparable)
}

2.3. Implementation

package _map

import (
	"fmt"
	"my_algorithm/model"
	"strings"
)

type node struct {
	key   model.Comparable
	value interface{}
	left  *node
	right *node
}

func (n *node) String() string {
	return fmt.Sprintf("%v:%v", n.key, n.value)
}

func newNode(key model.Comparable, value interface{}) *node {
	return &node{key: key, value: value}
}

type BstMap struct {
	root   *node
	length int
}

func NewBstMap() *BstMap {
	return &BstMap{}
}

func (b *BstMap) String() string {
	s := fmt.Sprintf("length=%v, data={", b.Length())
	inOrderPrint(b.root, &s)
	s = strings.TrimRight(s, " ")
	s += "}"
	return s
}

func inOrderPrint(n *node, s *string) {
	if n == nil {
		return
	}
	inOrderPrint(n.left, s)
	*s += fmt.Sprintf("%v ", n)
	inOrderPrint(n.right, s)

}

func (b *BstMap) Length() int {
	return b.length
}

func (b *BstMap) IsEmpty() bool {
	return b.length == 0
}

func (b *BstMap) Add(key model.Comparable, value interface{}) {
	b.Set(key, value)
}

func (b *BstMap) Contains(key model.Comparable) bool {
	_, ok := b.Get(key)
	return ok
}

func (b *BstMap) Get(key model.Comparable) (interface{}, bool) {
	return get(b.root, key)
}

func get(n *node, key model.Comparable) (interface{}, bool) {
	if n == nil {
		return nil, false
	}
	if key.CompareTo(n.key) < 0 {
		return get(n.left, key)
	} else if key.CompareTo(n.key) > 0 {
		return get(n.right, key)
	} else {
		return n.value, true
	}
}

func (b *BstMap) Set(key model.Comparable, value interface{}) {
	b.root = b.set(b.root, key, value)

}

func (b *BstMap) set(n *node, key model.Comparable, value interface{}) *node {
	if n == nil {
		b.length++
		return newNode(key, value)
	}

	// Replace or add in the left subtree
	if key.CompareTo(n.key) < 0 {
		//if n.left == nil {
		//	n.left = newNode(key, value)
		//	b.length++
		//	return n
		//}
		n.left = b.set(n.left, key, value)
		return n
		// Replace or add in the right subtree
	} else if key.CompareTo(n.key) > 0 {
		//if n.right == nil {
		//	n.right = newNode(key, value)
		//	b.length++
		//	return n
		//}
		n.right = b.set(n.right, key, value)
		return n
	} else {
		n.value = value
		return n
	}
}

func (b *BstMap) Remove(key model.Comparable) {
	b.root = b.remove(b.root, key)
}

func (b *BstMap) remove(n *node, key model.Comparable) *node {
	if n == nil {
		return nil
	}
	// First find the node to delete
	if key.CompareTo(n.key) < 0 {
		n.left = b.remove(n.left, key)
		return n
	} else if key.CompareTo(n.key) > 0 {
		n.right = b.remove(n.right, key)
		return n
	} else {
		// Perform the deletion
		b.length--
		return doRemove(n)
	}
}

func doRemove(n *node) *node {
	if n.left == nil {
		rightNode := n.right
		n.right = nil
		return rightNode
	}
	if n.right == nil {
		leftNode := n.left
		n.left = nil
		return leftNode
	}
	// Both the left and right subtrees are non-empty
	// First find the successor of the current node, i.e. the minimum node in the right subtree, to replace this node
	successor := min(n.right)
	successor.right = removeMin(n.right)
	successor.left = n.left
	// Delete the current node
	n.left = nil
	n.right = nil
	return successor
}

func min(n *node) *node {
	if n.left == nil {
		return n
	}
	return min(n.left)
}

func removeMin(n *node) *node {
	// If the left subtree is empty, the current node is the minimum node
	// Delete the current node and move the right subtree up as the root
	if n.left == nil {
		rightNode := n.right
		n.right = nil
		return rightNode
	}
	n.left = removeMin(n.left)
	return n
}

2.3.1. Test

func TestBstMap(t *testing.T) {
	var bstMap IMap = NewBstMap()
	fmt.Println("Initial state: ", bstMap)

	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	e4 := model.NewElement(4)
	e5 := model.NewElement(5)

	bstMap.Add(e3, "e3")
	bstMap.Add(e1, "e1")
	bstMap.Add(e2, "e2")
	bstMap.Add(e4, "e4")
	bstMap.Add(e5, "e5")

	fmt.Println("After adding elements: ", bstMap)

	v, _ := bstMap.Get(e1)
	fmt.Println("Value corresponding to e1: ", v)

	bstMap.Remove(e3)
	fmt.Println("Delete e3: ", bstMap)
	fmt.Println("Does the value corresponding to e3 still exist? ", bstMap.Contains(e3))
	bstMap.Remove(e3)
	fmt.Println("Delete e3 again: ", bstMap)

	bstMap.Set(e3, "e3")
	fmt.Println("Update e3: ", bstMap)
	bstMap.Set(e3, "ee3")
	fmt.Println("Update e3 again: ", bstMap)

}

3. Hash Table Implementation

3.1. Hash Function Design

• Principles
  • Consistency: if a == b, then hash(a) == hash(b)
  • Efficiency: calculation should be efficient and simple
  • Uniformity: hash values should be distributed uniformly

3.1.1. Approach 1: Convert to Integer

• Integer
  • Use small-range positive integers directly
  • Offset small-range negative integers
  • For large integers, take modulo by a prime number
• Floating point
  • Essentially represented using 32-bit or 64-bit binary values, so parse them as integers
• String
  • 
  • 
• Composite type
  • Same as strings
  • 

3.2. Data Structure

• Array + linked list

3.3. API

• Same as above

3.4. Implementation

// Prime numbers
const DefaultM = 7

type hashNode struct {
	key   model.Comparable
	value interface{}
}

func (h *hashNode) String() string {
	return fmt.Sprintf("%v:%v", h.key, h.value)
}

func newHashNode(key model.Comparable, value interface{}) *hashNode {
	return &hashNode{key: key, value: value}
}

func hashKey(key model.Comparable) *hashNode {
	return &hashNode{key: key, value: nil}
}

func (h *hashNode) CompareTo(other model.Comparable) int {
	otherHashNode, ok := other.(*hashNode)
	if !ok {
		panic("other is not hashNode")
	}
	return h.key.CompareTo(otherHashNode.key)
}

type HashMap struct {
	// Array in which each element is a linked list
	table []list.IList
	// Table length
	M int
	// Number of elements
	length int
}

func NewHashMap() *HashMap {
	table := make([]list.IList, DefaultM)
	for i := 0; i < len(table); i++ {
		table[i] = list.NewDoubleLinkedList()
	}
	return &HashMap{
		table:  table,
		length: 0,
		M:      DefaultM,
	}
}

func (h *HashMap) String() string {
	s := fmt.Sprintf("length=%v, M=%v, data={", h.length, h.M)

	for i := 0; i < len(h.table); i++ {
		slot := h.table[i]
		if slot.Length() > 0 {
			s += fmt.Sprintf("[slot-%v]: ", i)
			for i := 0; i < slot.Length(); i++ {
				n, _ := slot.Get(i)
				hNode := n.(*hashNode)
				s += fmt.Sprintf("%v ", hNode)
			}
			s = strings.TrimRight(s, " ")
			s += "\n"
		}
	}

	s += "}"
	return s
}

func (h *HashMap) Length() int {
	return h.length
}

func (h *HashMap) IsEmpty() bool {
	return h.length == 0
}

// Compute the hashCode of key
func hashCode(key interface{}) int {
	str := fmt.Sprintf("%v", key)
	v := int(crc32.ChecksumIEEE([]byte(str)))
	if v >= 0 {
		return v
	}
	return -v
}

// Compute which slot key maps to
func (h *HashMap) hash(key model.Comparable) int {
	return (hashCode(key) & 0x7fffffff) % h.M
}

func (h *HashMap) Add(key model.Comparable, value interface{}) {
	h.Set(key, value)
}

func (h *HashMap) Contains(key model.Comparable) bool {
	slot := h.table[h.hash(key)]
	return slot.Contains(hashKey(key))
}

func (h *HashMap) Get(key model.Comparable) (interface{}, bool) {
	slot := h.table[h.hash(key)]
	n, err := slot.Get(slot.Find(hashKey(key)))
	if err != nil {
		return nil, false
	}

	n2, ok := n.(*hashNode)
	if ok {
		return n2.value, true
	}
	return nil, false
}

func (h *HashMap) Set(key model.Comparable, value interface{}) {
	slot := h.table[h.hash(key)]
	index := slot.Find(hashKey(key))
	if index != -1 {
		slot.Set(index, newHashNode(key, value))
		return
	}
	slot.AddLast(newHashNode(key, value))
	h.length++
}

func (h *HashMap) Remove(key model.Comparable) {
	slot := h.table[h.hash(key)]
	if slot.RemoveElement(hashKey(key)) {
		h.length--
	}
}

3.4.1. Test

func TestHashMap(t *testing.T) {
	var hashMap IMap = NewHashMap()
	fmt.Println("Initial state: ", hashMap)

	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	e4 := model.NewElement(4)
	e5 := model.NewElement(5)

	hashMap.Add(e3, "e3")
	hashMap.Add(e1, "e1")
	hashMap.Add(e2, "e2")
	hashMap.Add(e4, "e4")
	hashMap.Add(e5, "e5")

	fmt.Println("After adding elements: ", hashMap)

	v, _ := hashMap.Get(e1)
	fmt.Println("Value corresponding to e1: ", v)

	hashMap.Remove(e3)
	fmt.Println("Delete e3: ", hashMap)
	fmt.Println("Does the value corresponding to e3 still exist? ", hashMap.Contains(e3))
	hashMap.Remove(e3)
	fmt.Println("Delete e3 again: ", hashMap)

	hashMap.Set(e3, "e3")
	fmt.Println("Update e3: ", hashMap)
	hashMap.Set(e3, "ee3")
	fmt.Println("Update e3 again: ", hashMap)
}