wouldn't it be more realistic to compare the benchmark to std::unordered_map[^]?
I ask, because std::map is an ordered container with focussing on slower insertation (write) but fast ordered iteration. The unordered_map does not focus on any output order, thus it does not spend time on complicated insertation...
Maybe, but this implementation is about preserving the order. That one reason, the other one is because there is almost nothing to gain from it. However, I just updated my GitHub repo to include std::unordered_map, and after you see the result, you will know what I mean by nothing.
For the function delete_(), You are right. it like that not because of a bug but by design; if size_ decremented, resize or accessing items will break. That is why you see if (item.hash_ != 0) almost everywhere. and I will get to that later.
For your point about anchor_, You are also right; it should be set to null, and that what (*before)->next_ = (*item)->next_; does. If next is null, then it is null, and if not, the next_ element is placed in that spot. If it set to null, the hash table breaks, because it not related to the item with it.
I understand why it may be confusing, and so, I have started working on a new design where anchor is placed in its block, and not having to initialize all of the variable just to have access to anchor. Also, the performance of the new design is better then this, and I might add std::allocator if there is something to gain. Overall, this is just an implementation, but does not mean it has to be that simple.
The reason why I have zero hash code is because of JSON, and JSON allows for empty key names. I have my hashing function that returns a number if the string is not null, and if it is empty or its length is zero, then it returns a positive number. However, I need to update the helper in this project to do just that.
Update: I think there is a bug in (*before)->next_ = (*item)->next_; and it should be something like (*before) = (*item)->next_; with more changes to the function. Thank you for reporting that.
Today I read the new implementation.
Moving the anchors to an external storage is a brilliant idea. Good to read this!
Its data structure and implementation is really interesting.
However there are still two problems in the previous implementation left unaddressed in the current one:
Hash code could not be 0 yet. If the code happened to be zero, the corresponding item will get lost after resizing HArray.
No API is exposed to return the number of available items in an HArray, since size_ is not decremented after a deletion. It is very common to query whether the container is empty or how many items are there within the container. Lacking such a function could significantly limit its usage.
You are right, I was being lazy and did not implement an API for getting the number of items that are not deleted. I said lazy because I really do not need it in my library that I use this for, and I should have done better. Sorry.
For the hash function, I have moved all calls to a single function, where I could replace std::hash with my hashing function - because I do not use the slandered library in my library, and mine never returns 0 unless the char *str is null.
To fix the hashing function returning zero, a single if statement should be added to replace any zero with one, I'm not sure yet about the impact on the performance, but I think It will be alright. But for the API, it might take a bit of work to ensure everything is working correctly.
Check back in a few days or keep an eye on the repo: HArray[^].