Rehash only when a new key is added. Fixes #5886

Cc: @JeffBezanson