[Question] Reason for no key collisions
Closed this issue · 5 comments
For this assignment, it seems we are avoiding key collisions by hashing the entire binary value rather than using some modulus to truncate the value. For instance, we create a new level in the tree to accommodate fox 111011, rather than modulus N (size of our current array) -> store at 011.
I don't understand the motivation behind this growable array. Considering our segment length is 2^i, to insert 2^i keys with size 2^i< k <= 2^(2i) keys we may have to create 2^i new levels. Which is 2^(2i) operations.
I might have missed it in the reading but is there a specific reason that we don't want any key collisions (and adding keys to buckets for this growable array).
We don't care about hashing in this homework for simplicity. You could implement it if you want to.
So does that mean we do not need to implement the recursive split ordering because our bucket sizes will always be one, since our growable array will grow each time we add a key > current size of the list. Therefore, buckets won't have to be broken up and relocated.
No, you should implement full functionality of recursive split ordered list (except for hashing) as presented in the reading materials. I'm not sure how you deduced that bucket sizes should be always 1 from your original question, but that's generally not true. As written in the comment, the size of buckets should grow. Please implement the recursive split ordered list as illustrated in the reading materials.
Hmm, I was able to pass all the tests without split ordering. I assumed this because of the growable array implementation. We don't have a resize function for the growable array, meaning when we insert key > loading factor it automatically grows, and without manual hashing, we will never take key mod load size. So the bucket size will always be 1, since we have no key collisions.
You might have just made a degenerate table, and since it is still a valid table impl, you pass the test. The test should test whether you properly inserted the algorithm, but it's not doing that currently :(.