1package hashtable 2 3import ( 4 "github.com/timtadh/data-structures/tree/avl" 5 . "github.com/timtadh/data-structures/types" 6) 7 8const ( 9 UTILIZATION = .75 10 RECORDS_PER_BLOCK = 16 11) 12 13type bst struct { 14 hash int 15 key Hashable 16 value interface{} 17 left *bst 18 right *bst 19} 20 21type LinearHash struct { 22 table []*avl.AvlNode 23 n uint 24 r uint 25 i uint 26} 27 28func NewLinearHash() *LinearHash { 29 N := uint(32) 30 I := uint(5) 31 return &LinearHash{ 32 table: make([]*avl.AvlNode, N), 33 n: N, 34 r: 0, 35 i: I, 36 } 37} 38 39func (self *LinearHash) bucket(key Hashable) uint { 40 m := uint(key.Hash() & ((1 << self.i) - 1)) 41 if m < self.n { 42 return m 43 } else { 44 return m ^ (1 << (self.i - 1)) 45 } 46} 47 48func (self *LinearHash) Size() int { 49 return int(self.r) 50} 51 52func (self *LinearHash) Put(key Hashable, value interface{}) (err error) { 53 var updated bool 54 bkt_idx := self.bucket(key) 55 self.table[bkt_idx], updated = self.table[bkt_idx].Put(key, value) 56 if !updated { 57 self.r += 1 58 } 59 if float64(self.r) > UTILIZATION*float64(self.n)*float64(RECORDS_PER_BLOCK) { 60 return self.split() 61 } 62 return nil 63} 64 65func (self *LinearHash) Get(key Hashable) (value interface{}, err error) { 66 bkt_idx := self.bucket(key) 67 return self.table[bkt_idx].Get(key) 68} 69 70func (self *LinearHash) Has(key Hashable) bool { 71 bkt_idx := self.bucket(key) 72 return self.table[bkt_idx].Has(key) 73} 74 75func (self *LinearHash) Remove(key Hashable) (value interface{}, err error) { 76 bkt_idx := self.bucket(key) 77 self.table[bkt_idx], value, err = self.table[bkt_idx].Remove(key) 78 if err == nil { 79 self.r -= 1 80 } 81 return 82} 83 84func (self *LinearHash) split() (err error) { 85 bkt_idx := self.n % (1 << (self.i - 1)) 86 old_bkt := self.table[bkt_idx] 87 var bkt_a, bkt_b *avl.AvlNode 88 self.n += 1 89 if self.n > (1 << self.i) { 90 self.i += 1 91 } 92 for key, value, next := old_bkt.Iterate()(); next != nil; key, value, next = next() { 93 if self.bucket(key.(Hashable)) == bkt_idx { 94 bkt_a, _ = bkt_a.Put(key.(Hashable), value) 95 } else { 96 bkt_b, _ = bkt_b.Put(key.(Hashable), value) 97 } 98 } 99 self.table[bkt_idx] = bkt_a 100 self.table = append(self.table, bkt_b) 101 return nil 102} 103 104func (self *LinearHash) Iterate() KVIterator { 105 table := self.table 106 i := 0 107 iter := table[i].Iterate() 108 var kv_iterator KVIterator 109 kv_iterator = func() (key Hashable, val interface{}, next KVIterator) { 110 key, val, iter = iter() 111 for iter == nil { 112 i++ 113 if i >= len(table) { 114 return nil, nil, nil 115 } 116 key, val, iter = table[i].Iterate()() 117 } 118 return key, val, kv_iterator 119 } 120 return kv_iterator 121} 122 123func (self *LinearHash) Items() (vi KIterator) { 124 return MakeItemsIterator(self) 125} 126 127func (self *LinearHash) Keys() KIterator { 128 return MakeKeysIterator(self) 129} 130 131func (self *LinearHash) Values() Iterator { 132 return MakeValuesIterator(self) 133} 134