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]

>>86
Well, >>18 is largely mathematically imprecise so I didn't bother to read the whole post, but if we let Y be a subset of X, and let f:X -> {true, false}, f(x) = true if x is in Y and false otherwise then that defines a valid mathematical function. The definition changes with Y though, so if you change Y the function becomes something different.

It becomes clearer if the definition is changed to something like this, let Y be a subset of X, and let
f_Y:X -> {true, false}, f_Y(x) = true if x is in Y and false otherwise.
Now it's easier to see that f_Y is a different function if you change Y, every f_Y either returns true or false and never both, so they are all functions.