> An indexed array is a degenerate example in which the "hash" (pointer) is presumably a lot smaller than the key (index). No, it isn't. The "0" in arr[0] is

> An indexed array is a degenerate example in which the "hash" (pointer) is presumably a lot smaller than the key (index). No, it isn't. The "0" in arr[0] is (in most cases) a 32-bit signed integer. If you're using a signed 32-bit int to index your array, you're using a hash length of 32-bits. You won't be able to index more than 2.1 billion unique items without changing your data type. Even if you're not using all those bits, you're still using 32-bits to index them. The fact that you're storing something that may have more than 32 bits of information is irrelevant, because your array (a naive hash) doesn't consider them real values. If you want to store a set of N elements in an array or perfectly hash a set of N elements, then the set of all possible indexes or hashes must have at least N elements.