Perl stores the number of keys in the hash as an independent property. So accessing this data is always O(1).

Note that this is not true of code that does if (%hash){} or otherwise inspects the *fill* of a hash using scalar %hash (note the omission of the keys() function). Such code, depending on the version, will be inefficient. In later perls the if() case is special cased to not use "fill", and in 5.20 scalar %hash will likely be equivalent to scalar keys %hash.