search

usethesource / capsule

The Capsule Hash Trie Collections Library
BSD 2-Clause "Simplified" License
404 stars 27 forks source link

Question on nodes array #17

Closed FrankC01 closed 7 years ago

FrankC01 commented 7 years ago

For Map tries...

I'm trying to wrap my head around the implementation (great work and kudos to all). No, I'm not a masochist!

Re: BitmapIndexedMapNode 'nodes' array

  1. Does it grow and/or shrink?
  2. Won't grow beyond 64 in size?

TIA

msteindorfer commented 7 years ago

Hi Frank, the answer to both questions is 'yes'.

ad 1) for growing and shrinking, have a look all methods prefixed with copyAnd.... ad 2) Leaf nodes might end up with 64 elements (32 times key and value) when you have a full trie with 2^32 elements, but typically the array sizes are way smaller.

FrankC01 commented 7 years ago

Thanks for that quick response and, by inference as I continue reading:

Hypothetical node:

nodeMap = 0x01; dataMap = 0x10;

then:

nodes.length = 4; nodes[0] ; == lower level node nodes[1] ; == null nodes[2] ; == key nodes[3] ; == value

FrankC01 commented 7 years ago

I'm good, thanks to the copyAnd... reference you gave me, I see now.