Flexible and efficient partitioning of a table is accomplished by hashing the key for an entry, and determining a partition for the entry by generating a sequence of pseudo-random numbers using the hashed key as the seed. As many pseudo-random numbers are generated as there are partitions available. The partition in which the entry belongs corresponds to the largest number in the sequence generated with the hashed key and the pseudo-random number generator. In this way, repartitioning of a partitioned table with a first number of partitions to a second number of partitions can be done with minimal movement and upon repartitioning, the new partition is the same partition that that would have resulted had a new partitioning been performed with the second number of partitions.