Here's an idea. First define the shift map $f$ by
$f(n) = 2n\,({\rm mod}\,N)$
for some large prime $N$. The hash function works as follows:
- Convert every character to its ASCII value
- Map the string $s$ to an integer by summing the ASCII values: $g(s) = \sum_{i=0}^{n-1} s_i$
- Apply the shift map $M$ times
Does this satisfy the common properties of being a hash function?
- The shift map is ergodic, so it distributes values uniformly throughout the range $\{1\dots N\}$
- The shift map exhibits sensitive dependence on initial conditions, so small changes in the input can result in large changes in the output (although, see my note later).
However, it is relatively easy to invert the shift map. We exploit the fact that $\mathbb{Z}/N\mathbb{Z}$ is a field for $N$ prime, which means that division is possible. Therefore given a hash value $h$, we compute $g=h/2^M$ in the field $\mathbb{Z}/N\mathbb{Z}$. We now know that any string whose ASCII values sum to a member of the set
$\{g, g+N, g+2N, \dots \}$
will be hashed to $h$. The problem is then to enumerate all strings whose ASCII values sum to members of this set, which is a much easier task.
Note: This answer isn't complete. One obvious deficiency is that two strings whose ASCII values sum to the same number will always hash to the same value - therefore we can make small changes to a string that will guarantee a hash collision. In particular, any permutation of a string will result in a hash collision, so "star", "rats" and "tars" will all hash to the same value. However, these are structured edits. A generic edit, such as randomly inserting, deleting or modifying a single character, will in general result in a different hash value.
Edit: One trivial modification that overcomes the above difficulty is to take a different map from String -> Int. Rather than simply summing values, we could consider
$g(s) = \sum_{i=0}^{n-1}2^ia_i$
where $n$ is the length of the string. Now, permuting the string will result in a different value of $g(s)$, so permutations will hash to different values. There may still be other problems with the approach, however.