缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

哈希表

  1. 哈希表存储的是由键（key）和值（value）组成的数据。
  2. 在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。
  4. 如果发生哈希冲突(哈希函数对不同的键, 返回了相同的哈希值)，
  5. 就使用链表进行存储(因此, 哈希表一般至少是数组+链表的二维结构)。
  7. 如果数组的空间太小，
  8. 使用哈希表的时候就容易发生冲突，
  9. 线性查找的使用频率也会更高；
  10. 反过来，如果数组的空间太大，
  11. 就会出现很多空箱子，造成内存的浪费。
  13. 摘自 <<我的第一本算法书>>(【日】石田保辉；宫崎修一)

目标

  • 实现一个哈希表, 提供对键值对数据的增删改查, 且性能不能太差
  • 物理结构
    • 采用分区 + 数组 + 链表的三维结构
    • 分区是一个双向链表, 由小到大呈2次幂增长
    • 当前分区总是指向最新也是最大的那个分区
    • 查找某个键时, 需要遍历所有分区
  • 哈希函数
    • 合适的哈希函数对性能影响非常巨大
    • 对哈希函数的要求一般是足够快, 足够”散”, 对不同键值最好能随机均匀分布
    • 本示例采用hash/crc64, 多项式为ECMA
    • 如果哈希函数的计算比较耗时, 则应当尽可能重复利用计算结果
  • 扩容与缩容
    • 扩容
      • 填充因子为3/4, 即当前分区的元素数>容量的3/4时, 创建2倍大的新分区
      • 扩容不做任何拷贝和rehash.
      • 扩容后, 非当前分区变成只读和只删.
    • 缩容: 当某个分区未持有任何元素, 且不为当前分区时, 删除此分区

设计

  • IHasher: 哈希支持接口, 定义哈希计算函数, 和键值相等比较函数
  • IMap: 哈希表接口
  • IMapIterator: 哈希表迭代器接口
  • tCrc64Hasher:
    • 基于hash/crc64, 实现IHasher接口.
    • 支持多种键类型
    • 对于整型的键, 返回自身;
    • 其他类型的键, 转为%v字符串再计算crc64的哈希值.
  • tHashMap: 哈希表的实现, 使用分区(双链)+数组+链表(单链)三维结构
  • tPartition: 哈希表分区. 其大小呈2次幂
  • tBucket: 哈希桶, 每个桶内的任何元素, 哈希值是一致的
  • tHashMapIterator: 哈希表迭代器的实现

单元测试

hashmap_test.go, 除基本功能测试, 还测试了百万键值插入+遍历的性能

  1. package data_structure
  3. import (
  4.     "fmt"
  5.     "learning/gooop/data_structure/hashmap"
  6.     "strconv"
  7.     "testing"
  8.     "time"
  9. )
  11. func Test_HashMap(t *testing.T) {
  12.     fnAssertTrue := func(b bool, msg string) {
  13.         if !b {
  14.             t.Fatal(msg)
  15.         }
  16.     }
  18.     fnEquals := func(a interface{}, b interface{}) bool {
  19.         i1,b1 := a.(int)
  20.         if b1 {
  21.             i2,b2 := b.(int)
  22.             if b2 {
  23.                 return i1 == i2
  24.             }
  25.         }
  27.         s1,b1 := a.(string)
  28.         if b1 {
  29.             s2,b2 := b.(string)
  30.             if b2 {
  31.                 return s1 == s2
  32.             }
  33.         }
  35.         return a == b
  36.     }
  38.     hasher := hashmap.NewCrc64Hashful(fnEquals)
  39.     hm := hashmap.NewHashMap(hasher, 2)
  41.     hm.Put(1, "10")
  42.     t.Log(hm)
  43.     fnAssertTrue(hm.Size() == 1, "expecting size == 1")
  44.     fnAssertTrue(hm.IsNotEmpty(), "expecting not empty")
  46.     ok,v := hm.Get(1)
  47.     fnAssertTrue(ok, "expecting ok")
  48.     fnAssertTrue(v == "10", "expecting 10")
  50.     hm.Put(2, "20")
  51.     hm.Put(3, "30")
  52.     hm.Put(4, "40")
  53.     hm.Put(5, "50")
  54.     t.Log(hm)
  55.     fnAssertTrue(hm.Size() == 5, "expecting size == 5")
  56.     ok,v = hm.Get(2)
  57.     fnAssertTrue(ok == true && v == "20", "expecting true and 20")
  59.     hm.Clear()
  60.     t.Log(hm)
  61.     fnAssertTrue(hm.Size() == 0, "expecting size == 0")
  62.     fnAssertTrue(hm.IsEmpty(), "expecting empty")
  64.     iter := hm.Iterator()
  65.     fnAssertTrue(!iter.More(), "expecting no more")
  67.     hm.Put(1, "10")
  68.     hm.Put(2, "20")
  69.     hm.Put(3, "30")
  70.     t.Log(hm)
  71.     fnAssertTrue(hm.Has(1) && hm.Has(2) && hm.Has(3) && !hm.Has(4), "expecting has 1,2,3")
  73.     hm.Put(4, "40")
  74.     hm.Put(5, "50")
  75.     hm.Put(6, "60")
  76.     t.Log(hm)
  77.     iter = hm.Iterator()
  78.     fnAssertTrue(iter.More(), "expecting more")
  79.     e,k,v := iter.Next()
  80.     t.Logf("%v>%s", k, v)
  81.     fnAssertTrue(e == nil, "e == nil")
  82.     e,k,v = iter.Next()
  83.     t.Logf("%v>%s", k, v)
  84.     fnAssertTrue(e == nil, "e == nil")
  85.     e,k,v = iter.Next()
  86.     t.Logf("%v>%s", k, v)
  87.     fnAssertTrue(e == nil, "e == nil")
  88.     e,k,v = iter.Next()
  89.     t.Logf("%v>%s", k, v)
  90.     fnAssertTrue(e == nil, "e == nil")
  91.     e,k,v = iter.Next()
  92.     t.Logf("%v>%s", k, v)
  93.     fnAssertTrue(e == nil, "e == nil")
  94.     e,k,v = iter.Next()
  95.     t.Logf("%v>%s", k, v)
  96.     fnAssertTrue(e == nil, "e == nil")
  97.     e,k,v = iter.Next()
  98.     fnAssertTrue(e != nil, "expecting e != nil")
  100.     ok,v = hm.Remove(3)
  101.     t.Log(hm)
  102.     fnAssertTrue(ok && v == "30" && hm.Size() == 5, "expecting remove 30")
  104.     ok,v = hm.Remove(2)
  105.     t.Log(hm)
  106.     fnAssertTrue(ok && v == "20" && hm.Size() == 4, "expecting remove 20")
  108.     t0 := time.Now().UnixNano()
  109.     hm.Clear()
  110.     size := 1000 * 1000
  111.     for i := 0; i < size;i++ {
  112.         hm.Put(strconv.Itoa(i), i)
  113.     }
  114.     millis := (time.Now().UnixNano() - t0) / 1000000
  115.     t.Logf("putting %v string>int = %v ms", size, millis)
  116.     fnAssertTrue(hm.Size() == size, fmt.Sprintf("expecting %v", size))
  118.     for i := 0;i < size;i++ {
  119.         ok, v = hm.Get(strconv.Itoa(i))
  120.         fnAssertTrue(ok == true && v == i, "expecting i")
  121.     }
  122. }

测试输出

  1. $ go test -v hashmap_test.go 
  2. === RUN   Test_HashMap
  3.     hashmap_test.go:42: s=1,v=1 p[1:b[1 1]]
  4.     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]]
  5.     hashmap_test.go:60: s=0,v=6 p[]
  6.     hashmap_test.go:70: s=3,v=9 p[1:b[1 1],2:b[1 2],3:b[1 3]]
  7.     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]]
  8.     hashmap_test.go:80: 1>10
  9.     hashmap_test.go:83: 2>20
  10.     hashmap_test.go:86: 3>30
  11.     hashmap_test.go:89: 4>40
  12.     hashmap_test.go:92: 5>50
  13.     hashmap_test.go:95: 6>60
  14.     hashmap_test.go:101: s=5,v=13 p[1:b[1 1],2:b[1 2],4:b[1 4],5:b[1 5],6:b[1 6]]
  15.     hashmap_test.go:105: s=4,v=14 p[1:b[1 1],4:b[1 4],5:b[1 5],6:b[1 6]]
  16.     hashmap_test.go:115: putting 1000000 string>int = 1590 ms
  17. --- PASS: Test_HashMap (2.17s)
  18. PASS
  19. ok      command-line-arguments  2.181s

IHasher.go

哈希支持接口, 定义哈希计算函数, 和键值相等比较函数

  1. package hashmap
  3. type IHasher interface {
  4.     Hash(key interface{}) uint64
  5.     Equals(a interface{}, b interface{}) bool
  6. }

IMap.go

哈希表接口

  1. package hashmap
  3. type IMap interface {
  4.     Size() int
  5.     IsEmpty() bool
  6.     IsNotEmpty() bool
  8.     Put(key interface{}, value interface{})
  9.     Get(key interface{}) (bool,interface{})
  10.     Has(key interface{}) bool
  11.     Remove(key interface{}) (bool, interface{})
  12.     Clear()
  14.     Iterator() IMapIterator
  15.     String() string
  16. }

IMapIterator.go

哈希表迭代器接口

  1. package hashmap
  3. type IMapIterator interface {
  4.     More() bool
  5.     Next() (err error, key interface{}, value interface{})
  6. }

tCrc64Hasher.go

  • 基于hash/crc64, 实现IHasher接口.
  • 支持多种键类型
  • 对于整型的键, 返回自身;
  • 其他类型的键, 转为%v字符串再计算crc64的哈希值. ```go package hashmap

import ( “fmt” “hash/crc64” )

var gCrc64Table = crc64.MakeTable(crc64.ECMA)

type FnEquals func(a interface{}, b interface{}) bool

type tCrc64Hasher struct { fnEquals FnEquals }

const INT_MAX = int(^uint(0) >> 1) const INT_MIN = ^INT_MAX const INT32_MAX = int32(^uint32(0) >> 1) const INT32_MIN = ^INT32_MAX const INT64_MAX = int64(^uint64(0) >> 1) const INT64_MIN = ^INT64_MAX

func (me *tCrc64Hasher) Hash(it interface{}) uint64 { if it == nil { return 0 }

  1. if v,ok := it.(int);ok {
  2.     return uint64(v - INT_MIN)
  4. } else if v,ok := it.(int64);ok {
  5.     return uint64(v - INT64_MIN)
  7. } else if v,ok := it.(int32);ok {
  8.     return uint64(v - INT32_MIN)
  10. } else if v,ok := it.(uint32);ok {
  11.     return uint64(v)
  13. }  else if v,ok := it.(uint64);ok {
  14.     return v
  16. } else if v,ok := it.(string);ok {
  17.     return crc64.Checksum([]byte(v), gCrc64Table)
  19. } else {
  20.     data := []byte(fmt.Sprintf("%v", it))
  21.     return crc64.Checksum(data, gCrc64Table)
  22. }

}

func (me *tCrc64Hasher) Equals(a interface{}, b interface{}) bool { if a == nil && b == nil { return true } if a == nil || b == nil { return false }

  1. fn := me.fnEquals
  2. if fn == nil {
  3.     return a == b
  4. } else {
  5.     return fn(a, b)
  6. }

}

func NewCrc64Hashful(fn FnEquals) IHasher { return &tCrc64Hasher{ fnEquals: fn, } }

  1. <a name="4cl6J"></a>
  2. # tHashMap.go
  3. 哈希表的实现, 使用分区(双链)+数组+链表(单链)三维结构
  4. ```go
  5. package hashmap
  7. import (
  8.     "fmt"
  9.     "strings"
  10. )
  12. type tHashMap struct {
  13.     hasher     IHasher
  14.     partitions *tPartition
  15.     size int
  16.     version int
  17. }
  20. func NewHashMap(hasher IHasher, capacity int) IMap {
  21.     if capacity < 4 {
  22.         capacity = 4
  23.     }
  25.     part := newPartition(hasher, capacity)
  26.     return &tHashMap{
  27.         hasher: hasher,
  28.         partitions: part,
  29.         size: 0,
  30.         version: 0,
  31.     }
  32. }
  34. func (me *tHashMap) Size() int {
  35.     return me.size
  36. }
  38. func (me *tHashMap) IsEmpty() bool {
  39.     return me.Size() <= 0
  40. }
  42. func (me *tHashMap) IsNotEmpty() bool {
  43.     return !me.IsEmpty()
  44. }
  46. func (me *tHashMap) Put(key interface{}, value interface{}) {
  47.     hash := me.hasher.Hash(key)
  48.     ok, _, bucket, node, _ := me.findByKeyAndHash(key, hash)
  49.     if ok {
  50.         bucket.putAt(node, key, value)
  52.     } else {
  53.         if me.partitions.nearlyFull() {
  54.             // create new partition
  55.             part := newPartition(me.hasher, int(me.partitions.bucketCount * 2))
  56.             part.next = me.partitions
  57.             me.partitions.prev = part
  58.             me.partitions = part
  59.             part.appendByKeyAndHash(key, value, hash)
  60.         } else {
  61.             me.partitions.appendByKeyAndHash(key, value, hash)
  62.         }
  64.         me.size++
  65.     }
  67.     me.version++
  68. }
  71. func (me *tHashMap) findByKey(key interface{}) (ok bool, part *tPartition, bucket *tBucket, node *tLinkedNode, prev *tLinkedNode) {
  72.     hash := me.hasher.Hash(key)
  73.     return me.findByKeyAndHash(key, hash)
  74. }
  76. func (me *tHashMap) findByKeyAndHash(key interface{}, hash uint64) (ok bool, part *tPartition, bucket *tBucket, node *tLinkedNode, prev *tLinkedNode) {
  77.     for part = me.partitions; part != nil; part = part.next {
  78.         ok, bucket, node, prev = part.findByKeyAndHash(key, hash)
  79.         if ok {
  80.             return ok, part, bucket, node, prev
  81.         }
  82.     }
  84.     return false, nil, nil, nil, nil
  85. }
  87. func (me *tHashMap) Get(key interface{}) (bool,interface{}) {
  88.     ok, _, _, node, _ := me.findByKey(key)
  89.     if ok {
  90.         return true, node.value
  91.     } else {
  92.         return false, nil
  93.     }
  94. }
  96. func (me *tHashMap) Has(key interface{}) bool {
  97.     ok, _, _, _, _ := me.findByKey(key)
  98.     return ok
  99. }
  101. func (me *tHashMap) Remove(key interface{}) (ok bool, value interface{}) {
  102.     ok, part, bucket, node, prev := me.findByKey(key)
  103.     if ok {
  104.         value = node.value
  105.         bucket.removeAt(node, prev)
  107.         // 缩容
  108.         if part.size <= 0 && part != me.partitions {
  109.             me.removePartition(part)
  110.         }
  112.         me.size--
  113.         me.version++
  114.         return ok, value
  116.     } else {
  117.         return false, nil
  118.     }
  119. }
  121. func (me *tHashMap) removePartition(part *tPartition) {
  122.     prev := part.prev
  123.     next := part.next
  125.     if prev != nil {
  126.         prev.next = next
  127.     }
  129.     if next != nil {
  130.         next.prev = prev
  131.     }
  133.     if me.partitions == part {
  134.         me.partitions = next
  135.     }
  136. }
  138. func (me *tHashMap) Clear() {
  139.     if me.IsEmpty() {
  140.         return
  141.     }
  143.     part := newPartition(me.hasher, len(me.partitions.buckets))
  144.     me.partitions = part
  145.     me.size = 0
  147.     me.version++
  148. }
  151. func (me *tHashMap) Iterator() IMapIterator {
  152.     return newHashMapIterator(me)
  153. }
  155. func (me *tHashMap) String() string {
  156.     itemStrings := make([]string, 0)
  157.     for p := me.partitions;p != nil;p = p.next {
  158.         itemStrings = append(itemStrings, p.String())
  159.     }
  160.     return fmt.Sprintf("s=%v,v=%v %s", me.size, me.version, strings.Join(itemStrings, " "))
  161. }

tPartition.go

哈希表分区. 其大小呈2次幂

  1. package hashmap
  3. import (
  4.     "fmt"
  5.     "strings"
  6. )
  8. type tPartition struct {
  9.     hasher IHasher
  10.     buckets []*tBucket
  11.     bucketCount uint64
  12.     prev *tPartition
  13.     next *tPartition
  14.     size int
  15.     threshhold int
  16. }
  18. func newPartition(hasher IHasher, bucketCount int) *tPartition {
  19.     it := &tPartition{
  20.         hasher: hasher,
  21.         buckets: make([]*tBucket, bucketCount),
  22.         bucketCount: uint64(bucketCount),
  23.         prev: nil,
  24.         next: nil,
  25.         size: 0,
  26.         threshhold: bucketCount * 3 / 4,
  27.     }
  28.     for i,_ := range it.buckets {
  29.         it.buckets[i] = newBucket(hasher)
  30.     }
  31.     return it
  32. }
  34. func (me *tPartition) putByKey(key interface{}, value interface{}) bool {
  35.     hash := me.hasher.Hash(key)
  36.     return me.putByKeyAndHash(key, value, hash)
  37. }
  39. func (me *tPartition) putByKeyAndHash(key interface{}, value interface{}, hash uint64) bool {
  40.     if me.getBucketByHash(hash).put(key, value) {
  41.         me.size++
  42.         return true
  43.     }
  44.     return false
  45. }
  47. func (me *tPartition) appendByKeyAndHash(key interface{}, value interface{}, hash uint64) {
  48.     me.getBucketByHash(hash).append(key, value)
  49.     me.size++
  50. }
  52. func (me *tPartition) getBucketByKey(key interface{}) *tBucket {
  53.     hash := me.hasher.Hash(key)
  54.     return me.getBucketByHash(hash)
  55. }
  57. func (me *tPartition) getBucketByHash(hash uint64) *tBucket {
  58.     return me.buckets[int(hash % me.bucketCount)]
  59. }
  61. func (me *tPartition) get(key interface{}) (bool,interface{}) {
  62.     return me.getBucketByKey(key).get(key)
  63. }
  65. func (me *tPartition) findByKey(key interface{}) (ok bool,bucket *tBucket,node *tLinkedNode, prev *tLinkedNode) {
  66.     bucket = me.getBucketByKey(key)
  67.     ok,node,prev = bucket.find(key)
  68.     return ok,bucket,node, prev
  69. }
  71. func (me *tPartition) findByKeyAndHash(key interface{}, hash uint64) (ok bool,bucket *tBucket,node *tLinkedNode, prev *tLinkedNode) {
  72.     bucket = me.getBucketByHash(hash)
  73.     ok,node,prev = bucket.find(key)
  74.     return ok,bucket,node, prev
  75. }
  77. func (me *tPartition) remove(key interface{}) (bool, value interface{}) {
  78.     ok,node := me.getBucketByKey(key).remove(key)
  79.     if ok {
  80.         me.size--
  81.         return true, node.value
  83.     } else {
  84.         return false, nil
  85.     }
  86. }
  88. func (me *tPartition) nearlyFull() bool {
  89.     return me.size >= me.threshhold
  90. }
  92. func (me *tPartition) String() string {
  93.     itemStrings := make([]string, 0)
  94.     for i,b := range me.buckets {
  95.         if b.size > 0 {
  96.             itemStrings = append(itemStrings, fmt.Sprintf("%v:%s", i, b.String()))
  97.         }
  98.     }
  99.     return fmt.Sprintf("p[%s]", strings.Join(itemStrings, ","))
  100. }

tBucket.go

哈希桶, 每个桶内的任何元素, 哈希值是一致的

  1. package hashmap
  3. import (
  4.     "fmt"
  5.     "strings"
  6. )
  8. type tBucket struct {
  9.     hasher IHasher
  10.     nodes  *tLinkedNode
  11.     size int
  12. }
  14. type tLinkedNode struct {
  15.     key interface{}
  16.     value interface{}
  17.     next *tLinkedNode
  18. }
  20. func newBucket(hasher IHasher) *tBucket {
  21.     return &tBucket{
  22.         hasher: hasher,
  23.         nodes: nil,
  24.         size: 0,
  25.     }
  26. }
  28. func newLinkedNode(key interface{}, value interface{}) *tLinkedNode {
  29.     return &tLinkedNode{
  30.         key: key,
  31.         value: value,
  32.         next: nil,
  33.     }
  34. }
  36. func (me *tBucket) put(key interface{}, value interface{}) bool {
  37.     existed, node, _ := me.find(key)
  38.     me.putAt(node, key, value)
  39.     return !existed
  40. }
  42. func (me *tBucket) append(key interface{}, value interface{}) {
  43.     me.putAt(nil, key, value)
  44. }
  46. func (me *tBucket) putAt(node *tLinkedNode, key interface{}, value interface{}) {
  47.     if node != nil {
  48.         node.value = value
  49.         return
  50.     }
  52.     it := newLinkedNode(key, value)
  53.     if me.nodes == nil {
  54.         me.nodes = it
  56.     } else {
  57.         it.next = me.nodes
  58.         me.nodes = it
  59.     }
  61.     me.size++
  62. }
  64. func (me *tBucket) get(key interface{}) (bool, interface{}) {
  65.     ok, node, _ := me.find(key)
  66.     if ok {
  67.         return true, node.value
  68.     }
  69.     return false, nil
  70. }
  72. func (me *tBucket) find(key interface{}) (ok bool, node *tLinkedNode, prev *tLinkedNode) {
  73.     prev = nil
  74.     for it:=me.nodes;it != nil;it = it.next {
  75.         if me.hasher.Equals(it.key, key) {
  76.             return true, it, prev
  77.         }
  78.         prev = it
  79.     }
  80.     return false, nil, nil
  81. }
  84. func (me *tBucket) remove(key interface{}) (bool, *tLinkedNode) {
  85.     ok,node, prev := me.find(key)
  86.     if !ok {
  87.         return false, nil
  88.     }
  90.     me.removeAt(node, prev)
  91.     return true, node
  92. }
  95. func (me *tBucket) removeAt(node *tLinkedNode, prev *tLinkedNode) {
  96.     if prev == nil {
  97.         me.nodes = node.next
  98.     } else {
  99.         prev.next = node.next
  100.     }
  101.     me.size--
  102. }
  104. func (me *tBucket) String() string {
  105.     itemStrings := make([]string, me.size)
  106.     i := 0
  107.     for it := me.nodes;it != nil;it = it.next {
  108.         itemStrings[i] = fmt.Sprintf("%v", it.key)
  109.         i++
  110.     }
  111.     return fmt.Sprintf("b[%v %s]", me.size, strings.Join(itemStrings, ","))
  112. }

tHashMapIterator.go

哈希表迭代器的实现

  1. package hashmap
  3. import "errors"
  5. type tHashMapIterator struct {
  6.     hashMap *tHashMap
  7.     pindex *tPartition
  8.     bindex int
  9.     nindex *tLinkedNode
  10.     version int
  11.     visited int
  12. }
  15. func newHashMapIterator(hashMap *tHashMap) IMapIterator {
  16.     return &tHashMapIterator{
  17.         hashMap: hashMap,
  18.         pindex: hashMap.partitions,
  19.         bindex: -1,
  20.         nindex: nil,
  21.         version: hashMap.version,
  22.         visited: 0,
  23.     }
  24. }
  27. func (me *tHashMapIterator) nextNode() *tLinkedNode {
  28.     node := me.nindex
  29.     for {
  30.         if node == nil {
  31.             bkt := me.nextBucket()
  32.             if bkt == nil {
  33.                 return nil
  34.             } else {
  35.                 me.nindex = bkt.nodes
  36.                 return me.nindex
  37.             }
  39.         } else {
  40.             node = node.next
  41.             if node != nil {
  42.                 me.nindex = node
  43.                 return node
  44.             }
  45.         }
  46.     }
  47. }
  49. func (me *tHashMapIterator) nextBucket() *tBucket {
  50.     part := me.pindex
  51.     bi := me.bindex + 1
  53.     for {
  54.         if bi >= len(part.buckets) {
  55.             part = me.nextPartition()
  56.             if part == nil {
  57.                 return nil
  58.             }
  60.             bi = 0
  61.         }
  63.         bkt := part.buckets[bi]
  64.         if bkt.nodes != nil {
  65.             me.bindex = bi
  66.             return bkt
  67.         }
  69.         bi++
  70.     }
  71. }
  74. func (me *tHashMapIterator) nextPartition() *tPartition {
  75.     if me.pindex == nil {
  76.         return nil
  77.     }
  78.     me.pindex = me.pindex.next
  79.     return me.pindex
  80. }
  82. func (me *tHashMapIterator) More() bool {
  83.     if me.version != me.hashMap.version {
  84.         return false
  85.     }
  86.     return me.visited < me.hashMap.size
  87. }
  89. func (me *tHashMapIterator) Next() (err error, key interface{}, value interface{}) {
  90.     if me.version != me.hashMap.version {
  91.         return gConcurrentModificationError, nil, nil
  92.     }
  94.     if !me.More() {
  95.         return gNoMoreElementsError, nil, nil
  96.     }
  98.     node := me.nextNode()
  99.     if node == nil {
  100.         return gNoMoreElementsError, nil, nil
  102.     } else {
  103.         me.visited++
  104.         return nil, node.key, node.value
  105.     }
  106. }
  108. var gConcurrentModificationError = errors.New("concurrent modification error")
  109. var gNoMoreElementsError = errors.New("no more elements")

(end)