Can a hash table implement a relation which can't be viewed as a mapping?

Question

A (partial or total) mapping from set S to T is a special relation between S and T. The difference between a mapping and a relation is that: a relation between S and T in general doesn't require that for each s in S, there exists no more than one elements in T corresponding to s.

A hash table is a data structure which implements a (partial or total) mapping.

• Can a hash table implement a relation which can't be viewed as a (partial or total) mapping?

• Specifically, if a s in S corresponds to t1 and t2 in T in the relation, can a hash table store t1 and t2 for s in the same way as a hash table implements a mapping in the case of hash conflict?

Thanks.

Answer 1

First of all, what you are referring to as a Hash Table is actually a Map. That is the generic name for this kind of data structure; a hash map implies a specific implementation (one using a hash function). A minimal signature of the Map Abstract Data Type (ADT) is something like the following:

find: forall (k, v). k v map * k -> v opt
insert: forall (k, v). k v map * k * v -> k v map
empty: forall (k, v). k v map

The above is saying that map is a type-constructor (also called a higher-kinded type) that takes in a pair of types (k, v) and produces a new type denoted k v map. The three functions listed are polymorphic, which is evident by the type quantification forall (k, v). This means that find is parameterized by a pait of types.

The correspondence between the map type and a function is evident in the nomenclature - functions are often called mappings.

Clearly, as you've discerned, every map with keys of type k and values of type v induces a function from k to v. To prove this, we can simply demonstrate a polymorphic functions that converts from one to the other (this is called a natural transformation in category theory; the polymorphism of this function is what's significant):

map_to_func: forall (k, v): k v map -> (k -> v)
map_to_func m = \key -> case find(m, key) of Some v -> v | None -> loop forever

If m is total - in the sense that every key can be found in the map - then map_to_func m is also total. But if m does not have a value for every key, then the result is a partial function, whose result is undefined (non-halting computation) for some inputs.

Side note: your definition of function is slightly incorrect. You state a function requires that each element of the domain relates to no more than one element in the codomain; in fact, each element in the domain must relate to exactly one element in the codomain.

Answer 2

I would say, "no", precisely because the conditions under which hash collisions occur will arise from outside the hash table's implementation semantic re: its internal management of buckets, etc.

Indeed, these conditions are intrinsically contingent, only, to the hashing algorithm that is used for the hash table's key type.

The only way I see a hash table could implement such a relation faithfully is if the relation itself is defined as being exactly the hash algorithm's mapping into hashes from the input key type, but then I guess this becomes a moot point.

Answer 3

Sure, but you probably don't want to.

Just to get some terminology straight: As you say in the question, hash tables are commonly used to implement mappings. A thing that implements a mapping is commonly called a map. Depending on the programming language that you are writing that thing in, a map might be an abstract data type, a class, or something similar. (For example, in Java, java.util.Map is an interface.) Since I don't know what language you're in, I'll just say ADT/class. Since you're asking about using hash tables to implement things other than mappings, I assume we're defining "hash table" as the raw data structure with the buckets, not a higher-level abstraction that limits you to map operations.

Nothing prevents you from using hash tables to implement things other than mappings. It's just that mappings are what hash tables are good at.

You say you want to implement a relation, which is defined as a collection of ordered pairs. The obvious way to implement that would be to make an ADT/class to represent an ordered pair, then store instances of them in a set, assuming you already have an ADT/class to represent a set.

But you are right that there is overlap between that and a map implemented using a hash table. As you know, hash functions have collisions in the general case, so code that implements a map using a hash table has to store a set of (key, value) pairs for each hash code (or for each bucket, to be more precise). And if (let's say) "find me all the elements in T that are related to a given element in S" is going to be a common operation it might make sense to implement a relation using a hash table, as you describe. The trick is, the code for that findby(s) operation will have to return a subset of the (key, value) pairs in the bucket where key = s, in contrast to a map (which would return the first and only (key, value) pair where key = s) or the raw hash table itself (where the bucket is a collection of (key, value) pairs where truncate(hash(key)) = truncate(hash(s))).

The problem is, other operations like "find me all the elements in S that are related to a given element in T" are going to be more difficult. And getting the semantics of a relation right will be hard enough without dealing with the idiosyncrasies of hash tables.