Talk:Hash table

may I ask what is O(1)? Robert Tito | Talk 14:39, 21 February 2007 (CST)

The O(n)-notation gives a hint on the complexity of a task, i.e. on the computational time needed to perform the task. n is the number of elements in consideration. This means if a task is in O(n) class, the time to perform the task increases linearly with the number of elements. O(1) (what you asked for) means that the time does not increase with the number of elements. O(n^2) would mean that time grows quadratically with the number of elements. Typical classe are O(1), O(log n), O(n), O(n log n), O(n2) and O(2^n). -- Alexander Wiebel 15:08, 21 February 2007 (CST)

By the way, this belongs to the field of theoretical computer science. Hope that helps. -- Alexander Wiebel 15:10, 21 February 2007 (CST)

I was hoping to come in later and write the article 'Big O Notation,' which would have cleared this up. As a general style rule, should I explain that in the article text instead of just linking to Big O Notation? --Nick Johnson 15:57, 21 February 2007 (CST)

understanding

See my remark as Alexander Wiebel's page:

order

To indicate an order, not the O is used but a curly O, ϑ though that is the theta. In a definition it seems inappropriate to state the order of what is meant. I guessed Order was meant but then it leaves me wondering: order of what in what. I hope you can understand this argument. Robert Tito | Talk 15:15, 21 February 2007 (CST) May I suggest to remove the Order from the definition and explain it in the article?Robert Tito | Talk 16:10, 21 February 2007 (CST)

I've seen the notation ${\mathcal {O}}(n)$, but only rarely. It may be a bit strong to say that $O(n)$ is incorrect. Greg Woodhouse 13:00, 30 April 2007 (CDT)

I do not see its contribution to hash tables at all, I would suggest removing the O(n) and replacing it by complexity ≈ n, or n^2. stating that the time needed to sort is proportional to the number of elements, or to its square or root or whatever is appropriate. To me that seems to make more sense than using some obscure order function that has no definition. Of course an explanation about the proportionality is appropriate. Robert Tito |  Talk  13:26, 30 April 2007 (CDT)

You'll get no argument from me there. The confusion is that if fixed size keys are used, it is reasonable to say that the hash algorithm should run in constant time (which is all that O(1) means), but the algorithms won't really run in constant time, it's just that a fixed key size makes it effectively constant. Greg Woodhouse 13:40, 30 April 2007 (CDT)

well why not just say that, and use terms people can relate to, some fuzzy order function needs to be looked up before people can understand it where we know it takes a few words to explain it without using nerdy language. my €0.01, the $ is slipping way too much :) Robert Tito |  Talk  13:45, 30 April 2007 (CDT)

Hash functions

The following is either misleading or incorrect:

The only requirement is the existence of a hash function which maps a unique object of the key type to a unique integer which is an offset within the array of values.

Suppose we're hashing integers, and we use the hash function n -> 2^100 n. This satisfies the above condition, but, since people usually use hash table sizes that are powers of 2, every object will be hashed to the first bucket. The correct condition is that the hash function should appear to be a random mapping from the space of keys to the space of hashes (usually 32-bit integers). I'll try to fix the article. Warren Schudy 10:46, 12 January 2008 (CST)

Great, thanks.Pat Palmer 21:32, 16 January 2008 (CST)