> spread = 0
> while True:
> spread += 1
> hashbits = self._hashbits + spread
> expansion = 1 << spread
> #hashmask = capacity - 1
> hashbytes = (hashbits+7) >> 3
> hashshift = (hashbytes << 3) - hashbits
> idx = int.from_bytes(keyhash[:hashbytes], 'big')
> >> hashshift #& hashmask
> if idx != int.from_bytes(collision[:hashbytes],
> 'big') >> hashshift: #& hashmask:
> break
> capacity = self._capacity * expansion
> assert 1 << hashbits == capacity
> expansionmask = spread - 1
that bug was here, i think. should be expansionmask = expansion - 1 .
further bugs remain ;p
> def content_generator():
> for superidx, item in
> enumerate(tqdm.tqdm(self.array, desc='growing hashtable',
> leave=False)):
> if item == self._sentinel:
> yield from [self._sentinel] * expansion
> else:
> keyhash = self._key(item)
> wholeidx =
> int.from_bytes(keyhash[:hashbytes], 'big') #>> hashshift #& hashmask
> assert superidx == wholeidx >> (hashbytes
> * 8 - self._hashbits)
> subidx = (wholeidx >> hashshift) & expansionmask
> assert superidx * expansion + subidx ==
> wholeidx >> hashshift
> yield from [self._sentinel] * subidx
> yield item
> yield from [self._sentinel] * (expansion -
> subidx - 1)
> self.array[:] =
> IterableWithLength(content_generator(), self._capacity * expansion)
> yield from [self._sentinel] * subidx
> yield item
> yield from [self._sentinel] * (expansion -
> subidx - 1)
> self.array[:] =
> IterableWithLength(content_generator(), self._capacity * expansion)
>
> The arithmetic mistake is in this section:
> wholeidx =
> int.from_bytes(keyhash[:hashbytes], 'big') # misleading comment
> removed
> assert superidx == wholeidx >> (hashbytes
> * 8 - self._hashbits)
> subidx = (wholeidx >> hashshift) & expansionmask
> assert superidx * expansion + subidx ==
> wholeidx >> hashshift
> The second assertion is raising. One of my bitwise arithmetics is wrong.
>
> After reducing the exponential growth ratio I was going to implement
> .update() for fast bulk updates of many items.
>
> It's so useful to have basic data structures!
