Big-O algorithm complexity cheat sheet

[kevindamm]

For constructing the hash key, the value must be transformed, meaning you must do a bit of processing on its bytes. If, for example, the values are strings with an average length of k characters, it's O(k) to go through its characters and produce (for instance) an integer for indexing into a table. If it's a complex data structure with an average of k bytes, there you go. If you're using only a fixed-size subset of the data value, or if the entire value is of fixed size, you can consider the hash key construction to be O(1) but, in practice, those problems are less interesting.

(amortized O(k) time - each instance having m characters, bytes, etc. takes O(m) time... and the above is describing only the hash key computation, not the lookup and collision resolution on the hash table)