# What Exactly Does the Term “Key” Mean with Regards to a Hash Table?

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.

• What now, hashtables or array? – Raphael May 22 '16 at 2:21
• (It has been my experience that mathematician $\ \ \not\!\!\!\!\!\iff$ rigor.) – Raphael May 22 '16 at 2:21
• 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) – Chill2Macht May 22 '16 at 2:23
• Depends. Do you want to talk abstract datatypes or implementation nitty-gritty? – Raphael May 22 '16 at 2:24
• I just want to know what the (mathematical) definition of key is? – Chill2Macht May 22 '16 at 2:25