Rehashing

noun

say it: “ree-HASH-ing” /riːˈhæʃɪŋ/

Moving every key of a hash table into a new, bigger array of buckets, working out each key's bucket again.

What is rehashing?

Rehashing is a hash table's moving day: it makes more buckets, usually twice as many, and hashes every key again, because a key's bucket depends on the number of buckets. It costs O(n), but doubling makes it rare, so a put stays O(1) on average.

In a sentence

  • “After rehashing into 8 buckets, Maya's coat moved from bucket 0 to bucket 4.”

Level: Journeyman · More Data Structures terms at this level

Updated