The structures you are talking about are defined by Perl itself.
in reply to Re^4: RFC on Inline::C hack: Hash_Iterator
in thread RFC on Inline::C hack: Hash_Iterator
I didn't know that, and I find it interesting. The cost involved to point back to the previous record is effectively negligable; however, I agree that the benefits are also minimal.
The linked lists used for buckets in perls hashes are intended to be extremely small, ie, generally they should hold only one element, and except for degenerate cases should not really exceed two elements. With this in mind a binary tree approach makes less sense as in most cases you will derive no benefit from it at all.
Agreed, from a Perl perspective. I should point out that I was aiming to talk in a more general way with that comment - though I accept that I didn't make that clear. My experience is largely with Other Languages that perhaps don't have such clever internals as Perl and where the underlying data structures can make the difference between terrible and acceptable performance speeds for extremely heavily loaded hash tables.