GHashTable: Robin Hood hashing

Submitted by Hans Petter Jansson @hansp

Link to original bug (#770616)

Description

Created attachment 334488 0001-GHashTable-Change-from-quadratic-probing-to-Robin-Ho.patch

Alex' prodding in bug 526456 motivated me to patch GHashTable to use Robin Hood hashing. The patch passes the tests and works when linked with Evolution, but I'm still skeptical of its performance benefits.

One nice thing about it is that I was able to eliminate the use of tombstones entirely.

It still needs proper benchmarking of insertions, removals and lookups in an appropriate mix alongside the current implementation.

There may also be some microoptimization/cleanup left to do.

Patch 334488, "0001-GHashTable-Change-from-quadratic-probing-to-Robin-Ho.patch":
0001-GHashTable-Change-from-quadratic-probing-to-Robin-Ho.patch

Version: 2.49.x