cs3110 / textbook

The CS 3110 Textbook, "OCaml Programming: Correct + Efficient + Beautiful"
Other
720 stars 132 forks source link

Inconsistency when to resize (Sections 8.1 and 8.2) #137

Closed cionx closed 8 months ago

cionx commented 1 year ago

There is a slight inconsistency for the resizing of hash tables between Sections 8.1 and 8.2. In Section 8.1, we resize a hash table once its load factor is strictly larger than 2. But then in Section 8.2, we suddenly resize it once the load factor is equal to 2.

I can see that both conventions make sense in the given context (in 8.1 we use the same behaviour as Hashtbl, whereas in 8.2 we want the calculations to be simple). But it is not clear if this inconsistency is an oversight, or actually intended. If it is intended, then there should maybe be a note in the text that acknowledges this inconsistency and assures the reader that it is not a mistake.

clarksmr commented 8 months ago

To be fair, 8.1 only makes that assumption in the limited context of 8.1.6. Elsewhere it is left deliberately more vague, because it's an implementation/analysis detail.

But 8.2 does need to clarify the exact assumption it makes, so I've now done that.