3 ms·
Small nit: in table 2 with the columns labeled "Key, Hash, Hash modulo 16", the thing called "hash" is actually known as a "prehash", while the "hash modulo 16"
by ModernMech 6y ago
Small nit: in table 2 with the columns labeled "Key, Hash, Hash modulo 16", the thing called "hash" is actually known as a "prehash", while the "hash modulo 16" is the hash. In the context of hash tables, pre-hashing is when you take something like a string or a data structure and turn it into a number. Hashing is the mapping from that number to one of the hash table bins. The distinction is often lost in practice, but if we're talking about hash table design and implementation it's important to make this clear at least once.
- joosters 6y agoIs 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 agoRight, 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.