1

I have a stupid question. Why in Swift Documentation is not say that Set and Dictionary is based on HashTable. If i am newbie and did not hear about algorithms and about hashtable is hard to understand how Set and Dic are working. Its important to mentions in first sentence that it is a based on Hashtable. For example if hash value are same how Set know about is this element equal. And if i know that under the hood it is hashtable i go and read about hash collision. What do you thing about?

2

Hey Bogdan, welcome to the forums!

The first line of the "Overview" for Dictionary is:

A dictionary is a type of hash table, providing fast access to the entries it contains.

Though honestly, I'm not sure it belongs there.

A common principle in programming is to emphasize interfaces (what things do) rather than implementations (what things are).

A dictionary is an unordered collection that provides fast access to some values by some unique key. This is all the documentation should commit to, because:

  1. This is what the library consumer wants to know: "What is this, and what can I do with it?"
  2. This is liberating to the library author, who now has the flexibility to use any data structure that fits the promises made by the documentation (namely, O(1) key access).

That sounds like an abstract concern, but it comes up in the real world. For example, for small enough sets/dictionaries, it's actually faster to do a linear scan through the elements in an array, than it is to compute hash values, chase pointers, etc.

So a really good implementation might be a hybrid of an array for small sizes, and a hash table for large sizes. This is a niche performance optimization detail, which doesn't belong in the documentation, IMO. And if that belongs there, then what other details should we mention? Side chaining vs double hashing?

Why in Swift Documentation is not say that Set and Dictionary is based on HashTable.

On the contrary, imagine a new programming coming to the documentation, and wondering "What the hell is a hash map?" It sounds like a geographic map of a certain plant.

3

If you‘re a newbie you probably should not care about hash collisions. If you want to implement a specific thing down the line you will find out about it during research.

Also I don’t think implementation details should be in the docs. The docs should mention things you need to know to use that component (Although some Swift Documentation is not very detailed in that regard either) and possibly some warnings if the implementation has some caveats you should be aware of.
If you are interested in how a thing works, you can always look up the sources and find detailed comments and the implementing itself there.

1 Like