Setting a <key,value> is in fact O(N) amortized runtime

[asafch]

hashlru claims that each operation's runtime is O(1) (amortized).
This assertion isn't held in this implementation: whenever a new <key,value> pair is inserted (and it does not exist in this.cache, in line 19 the comparison this.cache.size >= this.maxSize calls the getter size. This getter iterates over the cache in each call. Therefore, when inserting N new <key,value> pairs, the getter will create a total of 1+2+...+N=O(N^2) iterations. When amortized for N insertions, this is O(N) runtime (amortized) per single insert operation.

[sindresorhus]

Thanks for catching that. Could you take a look at #5?

[skeggse]

This getter iterates over the cache in each call.

Was this based on the ecmascript spec? I suspect that the exact phrasing (iterate over each item) isn't supposed to be normative - implementations should almost certainly just track the number of entries in the Map and return that value directly. Experimentally, I see no difference between reading the size of an empty Map and reading the size of a Map with 10⁷ items.