We’re rewarding the question askers & reputations are being recalculated! Read more.

# Tag Info

5

The way I can think of to do this is by some sort of normalization: that is, you need to find a function $f$ such that, if $\equiv$ is your custom equality and $==$ is the normal C++ (or whatever language you use) equality, for all $x,y$, we have $x \equiv y$ if and only if $f(x)==f(y)$. We call $f(x)$ the normal form of $x$. Then, the trick is, instead of ...

3

If you don’t know the equality function then you let hash(x) = 0. Seriously. All your algorithms will work, but slowly because of collisions. All the other suggestions will make your hashing slow instead so you lose nothing. Actually, if you have multiple dictionaries containing these keys, operations are quadratic in the size of each dictionary, instead of ...

1

Your question is a bit vague, but it seems that you're missing one mechanism: dynamic memory allocation. Some data structures such as linked lists are heavily based on dynamic memory allocation, and so although linked lists are very similar to arrays in function, they are implemented very differently. Dynamic memory allocation is treated as a primitive in C....

1

Suppose the objects you want to compare are strings containing terminating programs that output either 1 or 0 (and written in Visual Basic, because why not), and the equality function returns true if and only if the output of the two programs given as operands is the same. (The termination assumption is there to ensure that this equality is well-defined.) ...

Only top voted, non community-wiki answers of a minimum length are eligible