New answers tagged hash-tables
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....
0
The assumption is: You have an "equality" operator. The equality operator follows the usual rules, and it is also stable over time: If x = y or x ≠ y today, then x = y or x ≠ y tomorrow as well. You need a hash function which is guaranteed to hash equal values to equal hashes. Since equality is stable over time, if hash (x) is calculated and stored today, ...
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.)
...
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 ...
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 ...
Top 50 recent answers are included
