Design hash table with putAll function, time complexity limited O(1)

【 title 】

The three common operations on a hash table are PUT, GET, and containsKey, and the time complexity of these operations is O(1). Now we want to add a putAll function, which is to set all the key values to the same value. Use Golang to design and implement putAll enabled hash tables with O(1) time complexity for put, get, and putAll operations.

【 Basic ideas 】

Add the Version number field Version

1. Add + 1 to the version number of each record to mark the establishment sequence of each record;

2. Set a putAll record on top of the previous put operation and the version number +1 to mark when the putAll record is established.

3. If the version number of a record is smaller than that of the putAll record, putAll is the latest data and the value of the putAll record is returned. If the version number of a record is greater than that of the putAll record, the value of the record is the latest.

** Code implementation **

package main

import "fmt"

type PutAllValue struct {
	Value   string
	Version int
}

func (p *PutAllValue) GetValue(a) string {
	return p.Value
}

func (p *PutAllValue) GetVersion(a) int {
	return p.Version
}

type MyMap struct {
	Version int
	Mp map[string]*PutAllValue
}


func (m *MyMap) Put(key, value string) {
	p := &PutAllValue{}
	p.Value = value
	m.Version += 1
	m.Mp[key] = p
}
var  pForPutAll = &PutAllValue{}

func (m *MyMap) PutAll(value string) {

	pForPutAll.Value = value
	m.Version += 1
  // Critical operation to share the value of the version number
	pForPutAll.Version = m.Version

}

func (m *MyMap) Get(key string) string {
	if v, ok := m.Mp[key]; ok {
		if v.GetVersion() < pForPutAll.GetVersion() {
			return pForPutAll.GetValue()
		}else {
			return v.GetValue()
		}
	}else {
		return ""}}func main(a)  {
	tmpM := make(map[string]*PutAllValue)
	mm := &MyMap{0,tmpM}

	mm.Put("1"."a")
	mm.Put("2"."b")
	mm.Put("3"."c")
	res := mm.Get("2")
	fmt.Println(res)

	// Put all the key as 'd'
	mm.PutAll("d")

	afterRes := mm.Get("1")
	fmt.Println(afterRes)
	res2 := mm.Get("2")
	fmt.Println(res2)
	fmt.Println("All the key's value set as 'd' ")}Copy the code

You can see that the operation of putAll can be done in O(1) time complexity.

The above.