Sent from my iPad
>
> However I'm unable to make it at least comparable to chaining. The trick
> is that the hash table performs reasonably only until it's ~ 65-70% full,
> it gets really slow after that. So to maintain performance comparable to
> chaining, I'd have to keep the table below this threshold, effectively
> wasting ~30% of memory.
I expected that. AFAIK, open addressing gets slow when the load factor approaches 1. I feel this is what is happening
here.
>
> And the topic of this thread was about decreasing the memory consumptions,
> so it seems to me open-addressing is not a good match here. I'll try a few
> more things but I don't think it's going to fly.
>
Yeah, I also feel that open addressing isn't the way to go for the problem here.
> I've made some significant improvements in the chaining version (in the
> master branch), now getting about the memory consumption I've estimated.
>
I agree, we can hope to reduce the memory consumption by making changes in the current chaining implementation. I would
liketo look into changing the data structure used for chaining from singly linked list to maybe skip list or something
else.
Regards,
Atri