> 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.

It's the lemma I challenge, not the common case on certain of today's architectures. The use of the word "must" implies ∀, which is plainly not the case.

If it is not the case, can you present a counter-example? Can you code it up in say Python?

A really common pattern in many programs is to associate metadata with something using a unique key.

In cases where you can’t associate that metadata directly using a pointer (by using structures as keys embedding the pointer in the key) or a direct index into a metadata array, a perfect hash generated at build time is about as good as you’re going to get.

The other thing is that often this is easy to bolt on after the fact. As an example, in network devices it is common for a syslog mnemonic to be associated with an instance of a rate limiter. A good solution is to compile your log messages using an errmsg definition and compiler tool (which also allows you to build documentation) but this requires a lot of up-front planning and build orchestration and makes the code awkward in sone circumstances. An alternative is that you allow people to declare their mnemonic (and, for example, rate limit) in-place and then allow the logger library to use that to look up other properties that are joined from other sources (if there are any) and glean the structures that need to be created.

Since extracting the full set on mnemonics is necessary anyway (for tripwires, for documentation, ...) you can now build the hash function after-the-fact. This definitely simplified the build considerations (and avoids unnecessary rebuilds when, for example, only documentation changes).

The after-the-factness-but-with-low-overhead part is what’s nice about it. Yes, it’s better to structure things up front to make the system optimal but it’s nice to be able to get close.

OP just needs to change "key" to "key domain".

I mean, you can perfect hash the keys ["foo", "supercalifragilisticexpialidocious"] into a single bit, the string-lengths are irrelevant.

It's smaller than the key, but the size of the domain is the number of items you've put in the array.

Actually, I might have misunderstood you. In your example, the index in the array is treated like the hash of the item you've put in there, why are we suddenly considering pointers?

In this degenerate case the "hash function" is base_address+(index*sizeof(memory_address))

Not really, the function is still f(key) = <some number>, the rest is just taking the number and mapping it to the hardware that you're on.