0
$\begingroup$

I know it is supposed to be some arbitrary term that is a stand-in for a large class of possible objects.

But I still don't understand what part of the array the term "key" is meant to represent or denote.

Does it mean an element of the array? The index of the element of the array? Some arbitrary function from the elements of the array to some subset of the natural numbers?

EDIT: Since many people seem not to understand the question, here is a quote from Introduction to Algorithms by Cormen et al.

"With direct addressing, an element with key $k$ is stored in slot $k$. With hashing, this element is stored in slot $h(k)$; that is, we use a hash function to compute the slot from key $k$. Here $h$ maps the universe $U$ of keys into the slots of a hash table $T$... We also say that $h(k)$ is the hash value of key $k$."

It seems to me that the key, element index, and hash value are all different based on this.

Here is where the term is introduced in the chapter for the first time in a formal manner:

"Suppose that an application needs a dynamic set in which each element has a key drawn from the universe $U=\{0,1,\dots,m-1\}$, where $m$ is not too large. We shall assume that no two elements have the same key."

From this I would draw the conclusion that a universe of keys cannot exist for a multiset of integers which allows duplicate values, since the former is a finite set which is in bijection with all possible elements of the array (implying that the set of all possible elements of the array is finite), whereas the latter has no bound on its cardinality (since it can increase in size with every operation, hence the "dynamic", and there is no bound to the number of elements which can be added because (1) duplicate elements are allowed and (2) the number of possible integers is infinite).

Context:

For instance, when discussing the "pth-smallest key" algorithm, you want to find the "key" with the pth-smallest "rank" -- so the "rank" is different from the "key", and you want to sort the "ranks" of the "keys", but usually the "keys" are numbers too, so why not sort them? And why would there be a "rank", a "key", a "hash value", an array element, and an array element index?

As another example of where seemingly imprecise terminology is confusing me, consider a dynamic multiset $S$ of integers which allows duplicate values. Would this object allow a hash function? If it would, what would be the "keys", and what would be the "hash values"? Both the universe of keys and the target space for the hash function are supposed to be finite, whereas $|S|$, the cardinality of $S$, is clearly potentially unbounded, and in fact any integer can appear arbitrarily many times -- so how could anything associated with this problem be a "key"?

It is seemingly similar to other problems that admit hash functions.

$\endgroup$
  • 1
    $\begingroup$ What now, hashtables or array? $\endgroup$ – Raphael May 22 '16 at 2:21
  • $\begingroup$ (It has been my experience that mathematician $\ \ \not\!\!\!\!\!\iff$ rigor.) $\endgroup$ – Raphael May 22 '16 at 2:21
  • $\begingroup$ I don't understand the question? Do you mean about the tags? Isn't a hash table just an array with a hash function defined for its keys (whatever the keys of an array are, that's what I don't understand/what my question is about) $\endgroup$ – Chill2Macht May 22 '16 at 2:23
  • $\begingroup$ Depends. Do you want to talk abstract datatypes or implementation nitty-gritty? $\endgroup$ – Raphael May 22 '16 at 2:24
  • $\begingroup$ I just want to know what the (mathematical) definition of key is? $\endgroup$ – Chill2Macht May 22 '16 at 2:25
1
$\begingroup$

Their difference is the role that they have in the ordering and addressing of the table. The key is used to address a specific object (it's usually calculated using some algorithm or hashing function), while the rank is used to order objects and their respective keys using a specific ranking rule.

$\endgroup$
  • 1
    $\begingroup$ Theoretically the key is defined as that. The index can be a key depending on the implementation of the hash table. Imagine, for example, mapping the 26 standard latin letters: you need only a single array of 26 items (let's not go into the specific of how to deal with eventual duplicated keys...), so the index can be the alphabetic order index of the letter. $\endgroup$ – Matteo Manfredi May 22 '16 at 0:37
  • 1
    $\begingroup$ Well no, the index and the key would be the same, but the rank not necessarily. You could use an additional variable (or column in the table) to define it. The rank it's used also in case of duplicated keys to select the one that is the first in each of the keys (think of it like a FIFO or LIFO stack index). $\endgroup$ – Matteo Manfredi May 22 '16 at 0:47
  • 1
    $\begingroup$ It depends what the index of the array is for the hash table: if it is the rank yes, if it is the key no (the hashing function should always return the same key for the same object). You can use the hash function, the hard part I optimize the key space (how many single keys you have, ideally as low as possible) vs. the possible collisions (how many times the same key is generated (you have to deal with it and not always is possible or fast). $\endgroup$ – Matteo Manfredi May 22 '16 at 8:59
  • 1
    $\begingroup$ The key is the result of the hash function. That is the point. Then you can use the index or a variable in the object structure to indicate it (if it is the index you save the object to the index corresponding to the key, if it is a variable you save the object where you want putting the key in the variable). $\endgroup$ – Matteo Manfredi May 22 '16 at 14:28
  • 1
    $\begingroup$ You're completely right, based off of Cormen they define the key as the object, so following that substitute slot to key in my explanation. $\endgroup$ – Matteo Manfredi May 22 '16 at 15:24
1
$\begingroup$

You can say that a KEY is always unique or one to one mapping, corresponding to a certain element, while HASH function is not always one to one. HASH takes KEY as its input and different KEY may have same HASH value

$\endgroup$
  • $\begingroup$ So if two functions are assigned the same value by a function, the function couldn't be a key, but it could be a hash? $\endgroup$ – Chill2Macht May 22 '16 at 20:01
  • 1
    $\begingroup$ Yeah. We can always regard KEY as a function with input of element and it should be one to one. $\endgroup$ – user51561 May 22 '16 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.