4 ms·

Is that always true? It depends whether or not you think of the hash as a property of the hashtable, or a property of the key itself. e.g. you may have string o

Is that always true? It depends whether or not you think of the hash as a property of the hashtable, or a property of the key itself. e.g. you may have string objects that store their hash values internally - a useful optimisation if you are dealing with lots of long read-only strings, given that the hash function will have a cost of at least O(n) for the string length. Inserting a string into a hashtable wouldn't change its hash (what if the string is inserted into two tables of different sizes?)

ModernMech 6y ago
Right, it does depend on this perspective, which is why I say the distinction is often lost in practice. But from the perspective of hash table designers (at least historically), the hash can in fact change and is dependent on the size of the table. The distinction is important because the two operations are separable. I guess people didn't want to call one thing a "hash" and the other "hash mod k" because there are ways to do this other than mod. They could have called one "hash" and the other "post hash" but it is what it is. All I'm trying to say is if you want to know more about hash tables, and you bother to venture into the literature or some textbooks, you're going to run into this distinction sooner rather than later, so I wanted to point that out here.