0
  1. Is it correct that hashtables assume no key is shared between more than one records?

    In other words, can hashtables be used for implementing multimaps?

  2. When using a hashtable, can't multiple records with the same key value be dealt with in the same way as dealing with hash collision?

    Specifically, can the following operations work in the same way as resolving hash collision:

    • inserting two different records with the same key value, and
    • searching for possibly more than one records with the same key value
    • deleting possibly more than one records with the same key value.

Thanks.

3

Hashtables always deal with the possibility of hash collisions, as there is a good chance they occur even for different keys, the size of the hashes used being much smaller than those used for cryptography for example.

One way they deal with collisions is by using a linked list of pairs that share a key hash.

Thus, I see no impediment in implementing a multimap the same way.

  • Thanks. If hashtables are suitable implementing both maps and multimaps, then why the standard libraries of popular languages, such as C++, provide different data structures for maps and multimaps? Are hashtables only suitable for maps but not multimaps? – Tim Oct 19 '16 at 14:10
  • 1
    @Tim You're confusing interface and implementation. A Map and a MultiMap are different data types. That is why both are provided by C++. What D. Jurcau is saying is that underneath the hood, they could both be implemented by a hash table. – gardenhead Oct 19 '16 at 14:52
  • 1
    @Tim For once - because the contract is different. The contract for a 'Map' is that if you put a value with the same key twice, it replaces the old value. It's different for a 'MultiMap', hence the data structures have to be different, even if they use the same concept and might reuse many components underneath the interface. The other reason is that 'HashMap' assumes little to no collisions. It does deal with them, but not in the most efficient way. Thus it may be beneficial to also change some mechanics when transitioning to multiple keys as well. – Ordous Oct 19 '16 at 15:12
2

Yes, the contract of table/map-like interfaces like Java's Map<K,V>oder .NET's IDictionary<K,V> usually specify that one key has exactly one value of type V.

Why not multi-maps? Because that is a corner case that is very rarely used while single-valued maps are used much more frequently. It is easier to use a multi map by using a Map<K,Set<V>> wherever needed instead of having multi-maps the standard and extracting the single element of the image all over the place.

In fact that's what I would do if I wanted to implement a multi-map class: I would make a Map<K,Set<V>> the underlying data structure and delegate most of the work to that object. Whether that's a hash-map or some other map is not all that important.

  • 1
    Why a Set? Every multimap I've heard of (and used) is conceptually a Map<K, List<V>>. – Mason Wheeler Oct 19 '16 at 15:45
  • Really? Every multimap I've seen is Map<K,Set<V>>. This to me seems more like an artifact of their rare use than any real misunderstanding. Mathematically speaking multimaps model "multi-valued functions" which nowadays are understood to mean $f. K\to P(V)$ where $P$ denotes the powerset. – Johannes Hahn Oct 20 '16 at 7:00

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.