1
$\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.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ What now, hashtables or array? $\endgroup$
    – Raphael
    Commented May 22, 2016 at 2:21
  • $\begingroup$ (It has been my experience that mathematician $\ \ \not\!\!\!\!\!\iff$ rigor.) $\endgroup$
    – Raphael
    Commented May 22, 2016 at 2:21
  • 1
    $\begingroup$ @Chill2Macht, I have exactly the same concern now when reading CLRS. I don't understand: Is key just some identifier of the object (may not be unique) that helps with search? E.g. it may be the hash-slot, so instead of going one-by-one through all elements in a dynamic set we instead only go through the linked-list specified by the hash-slot? Or we sort objects by the key value, and then can search for objects faster (like in binary search)? But then if the key is a unique identifier of an object, how is it then different from a pointer? Hope you've got some clarity after 6 years have past $\endgroup$
    – Bananeen
    Commented Dec 16, 2020 at 18:44
  • 1
    $\begingroup$ The set of keys is most likely NOT finite. Even if it is finite, it is most likely HUGE. Say you have a UUID as the key with 2^128 values. Finite or infinite makes little difference. $\endgroup$
    – gnasher729
    Commented Jan 19, 2023 at 15:46
  • 1
    $\begingroup$ A hash table cannot sort. Rank and hashing are unrelated concepts. $\endgroup$
    – user16034
    Commented Jan 19, 2023 at 16:41

4 Answers 4

Reset to default
0
$\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.

Improve this answer
$\endgroup$
12
  • 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
    Commented May 22, 2016 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
    Commented May 22, 2016 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
    Commented May 22, 2016 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
    Commented May 22, 2016 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
    Commented May 22, 2016 at 15:24
4
$\begingroup$

A hash table is an implementation of a more general principle: A key/value table. In a key/value table you can insert values according to a key, you cannot add two values under the same key. You can lookup a value based on the key, or delete it based on the key.

Very often the key can be anything that is "equatable" (that is you can take two keys and say if they are equal, with the properties that a = a, a = b implies b = a, and a = b plus b = c implies a = c), and preferable is "hashable" (that is you can calculate an integer hash value for each key with the property that hash(a) doesn't change during one run of your program, and a = b implies hash(a) = hash(b)).

Improve this answer
$\endgroup$
3
$\begingroup$

A set is an abstract data type that stores "elements" such as integers, strings, points, or whatever. The elements must be unique and are stored in an unspecified order. Those elements are called the "keys".

A dictionary is like a set, but a value is associated to each key.

A set or a dictionary can be implemented by means of an array and a hashing function. The array slots are accessed by means of the hash, which is an integer computed from the key by some suitable rule. You lookup a key (to check its presence in the set or retrieve the associated value) by computing the hash and indexing the array with that number*.

As sets are unordered, the rank plays no role.

*This is a slightly simplified description: it turns out that two different keys may hash to the same index, and this needs to be somehow arbitrated.

Improve this answer
$\endgroup$
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

Improve this answer
$\endgroup$
2
  • $\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
    Commented May 22, 2016 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
    Commented May 22, 2016 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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