A slow hash-function doesn't explain the increasing time-per-element as the hash table grows though. A poor fit between the keys and hash-function might though.