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]

>>119
If this model is applied to languages that don't have a 'boolean' type, it won't always be a function, since there will be cases when a value not that in the set will map to "true"/"false".

>>121
That's kind of irrelevant.

When you say not in the set, you mean not in the domain of the function? That can't happen. By definition, any valid input is a member of the domain. If you mean not in the subset (Y, as I defined earlier), the value of the function will be "false". I don't see what not having a boolean type has to do with it. As long as you can represent "true" and "false", it's fine.

>>122
When you say not in the set, you mean not in the domain of the function? That can't happen.

Yes it can. Consider a set of unsigned integers {1...2^n-1} that maps to {true, false} . Now let's say this set undergoes an integral promotion. The end result is a number a outside of {1...2^n-1} would map to 'false'.

>>122
I don't see what not having a boolean type has to do with it. As long as you can represent "true" and "false", it's fine.

Having a boolean type gets around having a number outside of a set map to either 'true' or false'.

Hmm...ya know, I think I just lost all the minimum wage taco pushers who like to say "learn basic mathematics".

>>122
Kodak is simply too unintelligent to understand mathematics, I suggest you stop trying to teach him, he doesn't know how to listen to his betters.

>>122
Listen you mental midget, go work the cash register at target. I bet they appreciate your lame math skills . Also you still haven't posted any code, also you're still a minimum wage worker.

>>125
Minimum wage bitch, you still haven't posted any code, you still don't work as aprogrammer.

>>125
I'm still not convinced you understand what is being discussed in this thread. Now hush up and go help another customer you no talent bitch.

>>127
fuck off and die you cock sucking code monkey piece of shit

>>123
>>124
>>126
>>127
>>128
Same guy?

You're bringing in details that have no relevance to the mathematical definition you fuckwit. Just because it's possible in an implementation to give an input or return an output that is outside the range doesn't mean the function isn't well-defined. In practice, you would throw an error some way or another if something like that happened (or in this case, just return "false" indicating it isn't a member of the subset). In maths, we don't really consider things like that... but you wouldn't know that, would you?

>>130
>>123,124,126-128
ZOMG OPTIMIZED!

>>127
Instead of asking for code every ten replies, why don't you open up a fucking calc book.

>You're bringing in details that have no relevance to the mathematical definition you fuckwit. Just because it's possible in an implementation to give an input or return an output that is outside the range doesn't mean the function isn't well-defined.

Homegirl, if a number outside of a defined set maps to true/false, then is it a well defined function?

>In practice, you would throw an error some way or another if something like that happened (or in this case, just return "false" indicating it isn't a member of the subset). In maths, we don't really consider things like that... but you wouldn't know that, would you?

You're confused. If the set undergoes an integral transformation, no error will be thrown, because like, ya know, it's a legal conversion.

>>133
A function defined from a domain X to a range Y, is well defined if and only if for each x in X, there is a unique y in Y such that f(x) = y.

>>133
homegirl
fuck off and die feminist faggot

>>135
lol

>>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.

>>131
I Like Being Explicit

>>133
It doesn't map to anything because it's an invalid input. It would be undefined, but that doesn't mean the function isn't well-defined.

What language does an implicit conversion from a higher precision type to a lower one? If the programmer does an explicit conversion, it's their fault, and yeah, no error would be thrown.

>>137
Like I said before, that's beyond the scope of the maths. The function you defined, f(x), returns "true" if x != 0 and "false" otherwise. A conforming implementation shouldn't return any other value.

>>134
You can have a well defined function that doesn't fulfill those requirements, your definition is too strong.

>>139
What requirements? That a function shall return the values it is defined to return, or...?