Go的数据结构与实现【HashMap】

介绍

哈希表数据结构由哈希函数实现。数据结构不是使用自定义键将Key存储在映射中，而是对键执行散列函数以返回数组中Value的确切索引。

实现

实现思路

哈希表主要使用Go的map数据结构来实现，提供以下方法：

• Put()
• Remove()
• Get()
• Size()
  这里实现的哈希表并没有考虑哈希冲突，哈希函数采用著名的Horner’s method。

// the hash() private function uses the famous Horner's method
// to generate a hash of a string with O(n) complexity
func hash(k Key) int {
   h := 0
   for i := 0; i < len(k); i++ {
      h = 31*h + int(k[i])
   }
   return h
}

向哈希表中添加或删除元素即计算哈希映射然后刚刚map中k-v值，关于哈希冲突的解决后续有机会再去实现。

import "sync"

type Key string
type Value string

type HashMap struct {
   sync.RWMutex
   hashmap map[int]Value
}

func NewHashMap() *HashMap {
   ret := &HashMap{hashmap: make(map[int]Value)}

   return ret
}

// Put item with value v and key k into the hashmap
func (h *HashMap) Put(k Key, v Value) {
   h.Lock()
   defer h.Unlock()

   i := hash(k)
   if h.hashmap == nil {
      h.hashmap = make(map[int]Value)
   }

   h.hashmap[i] = v
}

// Remove item with key k from hashmap
func (h *HashMap) Remove(k Key) bool {
   h.Lock()
   defer h.Unlock()

   i := hash(k)
   if _, ok := h.hashmap[i]; ok {
      delete(h.hashmap, i)
      return true
   }

   return false
}

// Get item with key k from the hashmap
func (h *HashMap) Get(k Key) *Value {
   h.RLock()
   defer h.RUnlock()

   i := hash(k)
   if v, ok := h.hashmap[i]; ok {
      return &v
   }
   return nil
}

// Size returns the number of the hashmap elements
func (h *HashMap) Size() int {
   h.RLock()
   defer h.RUnlock()

   return len(h.hashmap)
}

单元测试

import "testing"

func TestHash(t *testing.T) {
   var key Key = "testKey"
   hashKey := hash(key)
   if hashKey != 105951707245 {
      t.Errorf("wrong hash, expect 105951707245 but got %d", hashKey)
   }
}

var (
   k1 Key   = "key1"
   k2 Key   = "key2"
   k3 Key   = "key3"
   v1 Value = "value1"
   v2 Value = "value2"
   v3 Value = "value3"
)

func InitHashMap() *HashMap {
   hashmap := NewHashMap()
   hashmap.hashmap[hash(k1)] = v1
   hashmap.hashmap[hash(k2)] = v2

   return hashmap
}

func TestHashMap_Put(t *testing.T) {
   hashmap := InitHashMap()
   if size := hashmap.Size(); size != 2 {
      t.Errorf("wrong count, expected 2 and got %d", size)
   }

   v := hashmap.Get(k3)
   if v != nil {
      t.Errorf("key k3 is not in hashmap")
   }

   hashmap.Put(k3, v3)
   if size := hashmap.Size(); size != 3 {
      t.Errorf("wrong count, expected 3 and got %d", size)
   }
   v = hashmap.Get(k3)
   if *v != v3 {
      t.Errorf("key k3 is in hashmap")
   }
}

func TestHashMap_Remove(t *testing.T) {
   hashmap := InitHashMap()

   ret := hashmap.Remove(k1)
   if !ret {
      t.Errorf("removing key k1 should return true")
   }

   ret = hashmap.Remove(k3)
   if ret {
      t.Errorf("removing key k1 should return false")
   }
}