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]

>>79
You'd end up with a different function, it doesn't change that it always either returns true or false.

>>81
In some cases, true would return false and vice versa.

>>82
And hence, this wouldn't be a function.

>>82
Yes what is your point? It's still a function.

Listen Kodak, all a function has to do is to return a single value. If you change the definition of a function it's a different function, so for instance if you first let f(x) = 1 and then let f(x) = 2, nothing has been violated, both are still functions. In this case the function is the return value of another function which takes a set to filter against. Consider the FIOC example.

def d(filter_set):
  return lambda x : x in filter_set

Now let f = d([2, 3]), given some input f will either return True or False, so it fits the definition of a mathematical function. If you later change f = d([1, 2]), f will return different values for some input compared to the old f, but they're both still functions.

Rightfully you may mutate filter_set after the creation of f so that the same (in the Python sense) function returns different values, but that's not relevant since it's not allowed in the mathematical sense.

>>82
Logical negation is a function which has the desired properties, it's even one-to-one.

>>84
To sum it up, >>18 has zero clue as to what it's talking about.

>>85
There is no logical negation going on though.

>>87
Well it would seem that >>83 seems to conclude that the property means that it can't be a function, which isn't true.

>>84
What about something like

X = {1, 2, 3,....,2^n -1} and Y = ("true", "false"}

I can think some C code that would produce the following sequence...

1 -> "true"
2 -> "false"
1 -> "false"
2 -> "true'
3 -> value not in the set
value not in the set -> "true"

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

>>89
Or even

1 -> "true"
2 -> "false"
value not in the set X -> "true"

In such a case, how can this be a function when a value which isn't in a set X, maps to Y ?

>>91
In such a case, how can this be a function when a value which isn't in a set X, maps to Y ?
Okay I get you now, yeah you definitely have to expand the domain to something larger than the set you're filtering against, if you don't it just always returns "true" or is undefined.

What >>18 did was to specify that the domain was a superset of the "filter set", which is valid but can probably lead to weird paradoxes with infinite sets and the likes, just saying that the domain is fixed and that the filter set is a subset of that avoids any such problems.

>>89
Can we stop keep saying "I can think of some [code] ..." and actually prototype our thoughts correctly?

>>93
If you had written any real life code you would've understood what I meant, you no talent bitch.

>>94
I'm sorry.  I'm only watching this thread because it's marginally interesting - marginally so - but your side of the argument is inserting ambiguity.  If it was a matter of "it goes without saying," you wouldn't even be having the argument in the first place.  Moreover, I can see what your opposition is saying because they are producing fuller examples, whether or not they are watertight; saying "this is where I start" and "this is what I got from it" is cheating the validity of your argument.

>>95
Cripes, look at this idiot, I bet you haven't written a piece of non trivial code in your whole life.

Kodak-san, you shouldn't expect math to perfectly fit c. You should instead learn math in its own context, and then apply it as appropriate to c.

>>90
Not everyone here understands the mathematical notation. I did my best to make it unambiguous using plain english, although that is always difficult.

Some of the posts here are making me cringe. I stopped when someone claimed functions had to have a one-to-one correspondence.

I stopped reading*, that is

>>98
That would be Kodak, he's not very bright. He regularly misapplies mathematical concepts because he simply doesn't understand them. He doesn't really know what a subset is but frequently uses the word.

>>98
ey is probably just using the wrong terms when trying to say that a function needs to be well defined. That is, that f(x) will take on only one value, for each x. An example of a function that is not well defined is the square root function with no convention for sign:

sqrt(x) = y where y^2 = x

both y and -y could be satisfactory outputs for x. So this definition does not uniquely define what values sqrt must take on for all x, and leaves the function not well defined.

Man this has been entertaining as hell. And also depressing

>>101
Right, but >>20 seems to think surjective functions aren't functions either.

>>103
Kodak is very unintelligent, this is why he mixes up code with purely mathematical concepts, he somehow thinks that his broken understanding of some programming language can affect mathematics.

He's also unable to admit that he's ever wrong, I've never seen him be right beyond purely basic stuff that everybody knows. There is another thread on /prog/ where he denies that every subset of a countable set is also countable despite mathematical proof being posted in the thread, he attempted to undermine the proof (there were two given actually, both one liners) by showcasing his broken idea of what a subset is and started ranting about credit card numbers or something like that, when confronted about it he angrily responded that nobody had a programming job but him.

So he's not only unintelligent and overly aggressive but he's also unwilling to learn, so I think it's safe to say that he'll never reach the intellectual level of say, you and me. I think it's sad that someone will be stuck at such a low mental level forever, but whatever, it's his fault not mine.

>>104
to be fair, it takes more than just an internet argument to learn these things. It takes time and practice, and you need to have access to some good dependable resources. If we linked him to a  a good online book on proofs and set theory, ey'd probably learn it pretty quick.

>>105
I doubt it, you're welcome to try though.

>>104
Stop projecting you no talent bitch.

>>103
No he doesn't you idiot.

>>105
And I'm still not convinced that you understand, that at least in C, it's possible for a value which is defined outside of a set, to be mapped to a "true" or "false". So perhaps it is you that needs to get a book on set theory. Now tell us all again what you do for a living.

>>104
You still don't seem to understand that in language like C, it is possible to have a value, which is defined outside of a set, map to either "true" or "false".

So again, you are stupid. And again, you have no possible future as a computer programmer. Now get rest bitch. You have a long day of doing general labor jobs in the morning.

>>108
>it's possible for a value which is defined outside of a set, to be mapped to a "true" or "false"

Are you talking about undefined behavior? Or maybe there is state that affects the output of the function that is not accounted for in the parameters, and depending on what the state is, the function application may evaluate to true or false?

>>110
I'm not talking about undefined behavior.

>>110
Try reading that sentence again, ``faggot''

>>110
No he's just being retarded, he still thinks that C has something to do with the mathematical definition of a function.

He just doesn't get it, he never will, he's not smart enough to grasp simple things like mathematics.

>>113
This is /prog. Hence, one can (reasonably) assume that the lame attempt at the math would apply to programming.

>>114
It does if you apply it correctly, several posts in this thread have, only you are too fucking dumb to understand mathematics.

Watching Kodak talk about mathematics is like watching someone commit suicide by slowly suffocating in their own feces.

>>116
As opposed the winner response >>18 gave?

>>115
Eh? Give us another lame math description you no talent bitch.

>>108
>>18 is describing a surjective function (domain is some set X, and the value of the function is true if the parameter is a member of X, and false otherwise) yet >>20 is claiming it's not a function. To be fair, it was horribly worded by >>18, but you're still a fucking retard.

>>119
Sorry I meant the value of the function is true if the parameter is a member of some set Y which is a subset of X.