Shulou(Shulou.com)06/03 Report--

This article mainly explains "golang basic data structure and algorithm how to use hash table", the content of the article is simple and clear, easy to learn and understand, now please follow the editor's train of thought slowly in depth, together to study and learn "golang basic data structure and algorithm how to use hash table" bar!

Hash tables store data consisting of keys (key) and values (value). In the hash table, we can use the hash function to quickly access the target data in the array. If a hash conflict occurs (the hash function returns the same hash value for different keys), it is stored using a linked list (therefore, the hash table is generally at least a two-dimensional structure of an array + linked list). If the space of the array is too small, conflicts will occur easily when using hash tables, and linear lookups will be used more frequently; conversely, if the space of the array is too large, there will be a lot of empty boxes, resulting in a waste of memory. Excerpt from ([Japan] Ishida Baohui; Miyazaki Shoichi) goal

Implement a hash table that provides the addition, deletion, modification and query of key value pairs of data, and the performance can not be too poor

Physical structure

Adopt the three-dimensional structure of partition + array + linked list

Partition is a two-way linked list, which grows to the second power from small to large.

The current partition always points to the newest and largest partition

When looking for a key, you need to traverse all partitions

Hash function

The appropriate hash function has a great impact on performance.

The requirements for hash functions are generally fast enough and scattered enough, and it is best to distribute different key values randomly and evenly.

This example uses hash/crc64, and the polynomial is ECMA.

If the calculation of the hash function is time-consuming, the calculated results should be reused as much as possible

Capacity expansion and reduction

Create a new partition twice the size of the current partition when the filling factor is 3max 4, that is, when the number of elements in the current partition is greater than the number of elements in the capacity.

Expansion does not make any copies and rehash.

After expansion, non-current partitions become read-only and delete-only.

Expand capacity

Scale down: delete a partition when it does not hold any elements and is not the current partition

Design

IHasher: hash support interface, define hash calculation function, and key value equality comparison function

IMap: hash table interface

IMapIterator: hash table iterator interface

TCrc64Hasher:

Based on hash/crc64, IHasher interface is realized.

Multiple key types are supported

For integer keys, return themselves

Other types of keys are converted to the% v string and then the hash value of crc64 is calculated.

THashMap: the implementation of hash table, using partition (double chain) + array + linked list (single chain) three-dimensional structure

TPartition: hash table partition. Its size is of the second power.

TBucket: hash bucket. The hash value of any element in each bucket is the same.

THashMapIterator: implementation of hash table iterator

Unit testing

Hashmap_test.go, in addition to basic functional testing, also tested the performance of million key insertion + traversal

Package data_structureimport ("fmt"learning/gooop/data_structure/hashmap"strconv"testing"time") func Test_HashMap (t * testing.T) {fnAssertTrue: = func (b bool) Msg string) {if! b {t.Fatal (msg)} fnEquals: = func (an interface {}, b interface {}) bool {i1 if b1: = a. (int) if b1 {i2 B2: = b. (int) if b2 {return i1 = = i2} s 1 direction b1: = a. (string) if b1 {S2 B2: = b. (string) if b2 {return S1 = = S2} return a = b} hasher: = hashmap.NewCrc64Hashful (fnEquals) hm: = hashmap.NewHashMap (hasher, 2) hm.Put (1 "10") t.Log (hm) fnAssertTrue (hm.Size () = 1, "expecting size = = 1") fnAssertTrue (hm.IsNotEmpty (), "expecting not empty") ok,v: = hm.Get (1) fnAssertTrue (ok, "expecting ok") fnAssertTrue (v = = "10", "expecting 10") hm.Put (2, "20") hm.Put (3 "30") hm.Put (4, "40") hm.Put (5, "50") t.Log (hm) fnAssertTrue (hm.Size () = = 5, "expecting size = = 5") ok,v = hm.Get (2) fnAssertTrue (ok = = true & & v = = "20" "expecting true and 20") hm.Clear () t.Log (hm) fnAssertTrue (hm.Size () = 0, "expecting size = = 0") fnAssertTrue (hm.IsEmpty (), "expecting empty") iter: = hm.Iterator () fnAssertTrue (! iter.More (), "expecting no more") hm.Put (1, "10") hm.Put (2 "20") hm.Put (3, "30") t.Log (hm) fnAssertTrue (hm.Has (1) & & hm.Has (2) & & hm.Has (3) & &! hm.Has (4), "expecting has 1, hm.Put (4," 40 ") hm.Put (5," 50 ") hm.Put (6) "60") t.Log (hm) iter = hm.Iterator () fnAssertTrue (iter.More (), "expecting more") e fnAssertTrue v: = iter.Next () t.Logf ("% v >% s", k) fnAssertTrue (e = = nil, "e = = nil") V) fnAssertTrue (e = = nil, "e = = nil") ePersonnce v = iter.Next () t.Logf ("% v >% s", kpene v) fnAssertTrue (e = = nil, "e = = nil") ePert v = iter.Next () t.Logf ("% v >% s", kpene v) fnAssertTrue (e = = nil, "e = nil") V = iter.Next () t.Logf ("% v >% s", kPoweragv) fnAssertTrue (e = = nil, "e = = nil") ePersonality v = iter.Next () t.Logf ("% v >% s", kpencev) fnAssertTrue (e = = nil, "e = = nil") eMagnekPersonv = iter.Next () fnAssertTrue (e! = nil) "expecting e! = nil") ok,v = hm.Remove (3) t.Log (hm) fnAssertTrue (ok & v = = "30" & & hm.Size () = = 5, "expecting remove 30") ok,v = hm.Remove (2) t.Log (hm) fnAssertTrue (ok & & v = = "20" & & hm.Size () = = 4 "expecting remove 20") t0: = time.Now () .UnixNano () hm.Clear () size: = 1000 * 1000 for I: = 0 I

< size;i++ { hm.Put(strconv.Itoa(i), i) } millis := (time.Now().UnixNano() - t0) / 1000000 t.Logf("putting %v string>

Int =% v ms ", size, millis) fnAssertTrue (hm.Size () = = size, fmt.Sprintf (" expecting% v ", size)) for I: = 0

< size;i++ { ok, v = hm.Get(strconv.Itoa(i)) fnAssertTrue(ok == true && v == i, "expecting i") }}测试输出$ go test -v hashmap_test.go === RUN Test_HashMap hashmap_test.go:42: s=1,v=1 p[1:b[1 1]] hashmap_test.go:54: s=5,v=5 p[4:b[1 4],5:b[1 5]] p[1:b[1 1],2:b[1 2],3:b[1 3]] hashmap_test.go:60: s=0,v=6 p[] hashmap_test.go:70: s=3,v=9 p[1:b[1 1],2:b[1 2],3:b[1 3]] hashmap_test.go:76: s=6,v=12 p[1:b[1 1],2:b[1 2],3:b[1 3],4:b[1 4],5:b[1 5],6:b[1 6]] hashmap_test.go:80: 1>

10 hashmap_test.go:83: 2 > 20 hashmap_test.go:86: 3 > 30 hashmap_test.go:89: 4 > 40 hashmap_test.go:92: 5 > 50 hashmap_test.go:95: 6 > 60 hashmap_test.go:101: 5 > 50 hashmap_test.go:95: 6 > 60 hashmap_test.go:101: 5 > 50 hashmap_test.go:95: 6 > 60 hashmap_test.go:101: 5 > 50 hashmap_test.go:95: 6 > 60 hashmap_test.go:101: 5 > 50 hashmap_test.go:95: 6 > 60 hashmap_test.go:101: 5 > 50 hashmap_test.go:95: 6 > 60 hashmap_test.go:101 4 string [1 4], 5 string [15], 6] hashmap_test.go:115: putting 1000000 string > int = 1590 ms--- PASS: Test_HashMap (2.17s) PASSok command-line-arguments 2.181sIHasher.go

Hash support interface, define hash calculation function, and key value equality comparison function

Package hashmaptype IHasher interface {Hash (key interface {}) uint64 Equals (an interface {}, b interface {}) bool} IMap.go

Hash table interface

Package hashmaptype IMap interface {Size () int IsEmpty () bool IsNotEmpty () bool Put (key interface {}, value interface {}) Get (key interface {}) (bool,interface {}) Has (key interface {}) bool Remove (key interface {}) (bool,interface {}) Clear () IMapIterator String () string} IMapIterator.go

Hash table iterator interface

Package hashmaptype IMapIterator interface {More () bool Next () (err error, key interface {}, value interface {})} tCrc64Hasher.go

Based on hash/crc64, IHasher interface is realized.

Multiple key types are supported

For integer keys, return themselves

Other types of keys are converted to the% v string and then the hash value of crc64 is calculated.

Package hashmapimport ("fmt"hash/crc64") var gCrc64Table = crc64.MakeTable (crc64.ECMA) type FnEquals func (an interface {} B interface {}) booltype tCrc64Hasher struct {fnEquals FnEquals} const INT_MAX = int (^ uint (0) > > 1) const INT_MIN = ^ INT_MAXconst INT32_MAX = int32 (^ uint32 (0) > > 1) const INT32_MIN = ^ INT32_MAXconst INT64_MAX = int64 (^ uint64 (0) > > 1) const INT64_MIN = ^ INT64_MAXfunc (me * tCrc64Hasher) Hash (it interface {}) uint64 {if it = = nil {return 0} if v Ok: = it. Int) Ok {return uint64 (v-INT_MIN)} else if v INT64_MIN ok: = it. (int64); ok {return uint64 (v-INT64_MIN)} else if v Magi ok: = it. (int32); ok {return uint64 (v-INT32_MIN)} else if v Magi ok: = it. (uint32) Ok {return uint64 (v)} else if v Die ok: = it. (uint64); ok {return v} else if v Magi ok: = it. (string) Ok {return crc64.Checksum ([] byte (v), gCrc64Table)} else {data: = [] byte (fmt.Sprintf ("% v", it)) return crc64.Checksum (data, gCrc64Table)}} func (me * tCrc64Hasher) Equals (an interface {} B interface {}) bool {if a = = nil & & b = = nil {return true} if a = = nil | b = nil {return false} fn: = me.fnEquals if fn = = nil {return a = = b} else {return fn (a) B)}} func NewCrc64Hashful (fn FnEquals) IHasher {return & tCrc64Hasher {fnEquals: fn,}} tHashMap.go

The implementation of hash table, using partition (double chain) + array + linked list (single chain) three-dimensional structure

Package hashmapimport ("fmt"strings") type tHashMap struct {hasher IHasher partitions * tPartition size int version int} func NewHashMap (hasher IHasher, capacity int) IMap {if capacity

< 4 { capacity = 4 } part := newPartition(hasher, capacity) return &tHashMap{ hasher: hasher, partitions: part, size: 0, version: 0, }}func (me *tHashMap) Size() int { return me.size}func (me *tHashMap) IsEmpty() bool { return me.Size() 0 { itemStrings = append(itemStrings, fmt.Sprintf("%v:%s", i, b.String())) } } return fmt.Sprintf("p[%s]", strings.Join(itemStrings, ","))}tBucket.go 哈希桶, 每个桶内的任何元素, 哈希值是一致的 package hashmapimport ( "fmt" "strings")type tBucket struct { hasher IHasher nodes *tLinkedNode size int}type tLinkedNode struct { key interface{} value interface{} next *tLinkedNode}func newBucket(hasher IHasher) *tBucket { return &tBucket{ hasher: hasher, nodes: nil, size: 0, }}func newLinkedNode(key interface{}, value interface{}) *tLinkedNode { return &tLinkedNode{ key: key, value: value, next: nil, }}func (me *tBucket) put(key interface{}, value interface{}) bool { existed, node, _ := me.find(key) me.putAt(node, key, value) return !existed}func (me *tBucket) append(key interface{}, value interface{}) { me.putAt(nil, key, value)}func (me *tBucket) putAt(node *tLinkedNode, key interface{}, value interface{}) { if node != nil { node.value = value return } it := newLinkedNode(key, value) if me.nodes == nil { me.nodes = it } else { it.next = me.nodes me.nodes = it } me.size++}func (me *tBucket) get(key interface{}) (bool, interface{}) { ok, node, _ := me.find(key) if ok { return true, node.value } return false, nil}func (me *tBucket) find(key interface{}) (ok bool, node *tLinkedNode, prev *tLinkedNode) { prev = nil for it:=me.nodes;it != nil;it = it.next { if me.hasher.Equals(it.key, key) { return true, it, prev } prev = it } return false, nil, nil}func (me *tBucket) remove(key interface{}) (bool, *tLinkedNode) { ok,node, prev := me.find(key) if !ok { return false, nil } me.removeAt(node, prev) return true, node}func (me *tBucket) removeAt(node *tLinkedNode, prev *tLinkedNode) { if prev == nil { me.nodes = node.next } else { prev.next = node.next } me.size--}func (me *tBucket) String() string { itemStrings := make([]string, me.size) i := 0 for it := me.nodes;it != nil;it = it.next { itemStrings[i] = fmt.Sprintf("%v", it.key) i++ } return fmt.Sprintf("b[%v %s]", me.size, strings.Join(itemStrings, ","))}tHashMapIterator.go 哈希表迭代器的实现 package hashmapimport "errors"type tHashMapIterator struct { hashMap *tHashMap pindex *tPartition bindex int nindex *tLinkedNode version int visited int}func newHashMapIterator(hashMap *tHashMap) IMapIterator { return &tHashMapIterator{ hashMap: hashMap, pindex: hashMap.partitions, bindex: -1, nindex: nil, version: hashMap.version, visited: 0, }}func (me *tHashMapIterator) nextNode() *tLinkedNode { node := me.nindex for { if node == nil { bkt := me.nextBucket() if bkt == nil { return nil } else { me.nindex = bkt.nodes return me.nindex } } else { node = node.next if node != nil { me.nindex = node return node } } }}func (me *tHashMapIterator) nextBucket() *tBucket { part := me.pindex bi := me.bindex + 1 for { if bi >

= len (part.buckets) {part = me.nextPartition () if part = = nil {return nil} bi = 0} bkt: = part.buckets [bi] If bkt.nodes! = nil {me.bindex = bi return bkt} bi++}} func (me * tHashMapIterator) nextPartition () * tPartition {if me.pindex = = nil {return nil} me.pindex = me.pindex.next Return me.pindex} func (me * tHashMapIterator) More () bool {if me.version! = me.hashMap.version {return false} return me.visited < me.hashMap.size} func (me * tHashMapIterator) Next () (err error Key interface {}, value interface {}) {if me.version! = me.hashMap.version {return gConcurrentModificationError, nil, nil} if! me.More () {return gNoMoreElementsError, nil, nil} node: = me.nextNode () if node = = nil {return gNoMoreElementsError, nil Nil} else {me.visited++ return nil, node.key, node.value}} var gConcurrentModificationError = errors.New ("concurrent modification error") var gNoMoreElementsError = errors.New ("no more elements") Thank you for your reading The above is the content of "how to use hash table in golang basic data structure and algorithm". After the study of this article, I believe you have a deeper understanding of how to use hash table in golang basic data structure and algorithm, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.