Hash table

Is it ever possible to have a Hash table that can do get,put,remove @ O(1) for Strings?

calculating the hash for the String alone is O(n), is it not? [that's if you want to produce a good hash that won't collide all over the place]

>>134
The model would still break down in languages that don't support a real boolean type. I'm going to omit integral transformation and numbers outside of a set since we have a bunch of wanna be programmers/wikipedia educated folk on here.

Let's say that I have a set X such that X = {x | 2^n-1 - 1 <= x <= -2^n-1} and a set Y such that Y = {y | y !=0}. Now I define a relation F:X->Y as

F(x) = true when x != 0

If I pick two non zero points a and b in X, it's pretty easy that F(a) = true and F(b) is true. However, I don't think there would be a unique y in Y such that F(x) = y. This because in languages like C, you could possibly end up with f(a) != f(b).

This seems counter intuitive because logic would suggest f(a) == f(b) since they both a and b map to true.