On 2014-05-17 22:30, bearophile wrote:
Sorry, I didn't know the linked list is sorted. It's scanned sequentially,
because you can't use a binary search on a regular linked list. Perhaps a
skiplist is better to avoid O(n^2) behavour in presence of attacks or
degenerate cases (in past the AA used a tree there).
if (nodes > buckets_length * 4) rehash();
Skiplist doesn't seem necessary. As seen above, there shouldn't be much of a
problem with long lists accumulating in some selected buckets, as long as the
hash function is a proper hash (i.e. for any set of x (especially consecutive
ones like 0, 1, ... n) hash(x) values cover the range of size_t evenly).
