5
$\begingroup$

Are there variants of hash tables that take advantage of the likely distribution of key values? For example, if I'm using utf-8 encoded unicode strings as identifiers in a compiler but expect the majority of them to fit into ASCII, can I optimize for that use case?

$\endgroup$
  • $\begingroup$ Hash functions are certainly designed for and tested with the data that they will likely be used on. For example, ElfHash (a variant on PJW) was designed with programming language identifiers in mind. Programmers tend to use sets of identifiers like "x1", "x2", "y1", "y2", etc, which caused collisions in some older hash functions. $\endgroup$ – Pseudonym Aug 5 '16 at 3:45
  • 3
    $\begingroup$ What exactly "optimize" means in your context? No collisions? Shorter hashes? The answer is "yes" and "yes", could you edit your question to give some objective? $\endgroup$ – Evil Aug 5 '16 at 4:15
2
$\begingroup$

Yes, it's sometimes possible to optimize hash tables based on expected key values (i.e. make certain classes of keys at the expense of other classes). But I don't see how there could be one in your case.

There are two ways to potentially make hash tables faster: use a hash function with fewer collisions, and use a hash functions that's faster to calculate. But they pull in opposite directions: you can either make the hash function faster or better, not both.

Hash functions are designed to spread out likely key values in the first place. So if you have “typical” input, there's nothing to be gained here.

For example, if you're making exact string comparisons, then the fact that the strings are encoded in UTF-8 doesn't affect the way the hashes are calculated. The hash function looks at all the bytes of the string anyway, and has a low probability of collisions except for specially-crafted data. A hash function specialized to pure-ASCII strings won't be faster to calculate (operations are on bytes anyway, even on words, not on individual bits) nor have more collisions (repeated bit patterns like “all upper bits are 0” is something typical hash functions are designed to cope with).

An example where you can gain performance for typical cases is when the key for the hash table is a large data structure, such that there's a gain to be made by hashing only part of the data structure. Say the key consists of both a name and some large extra data, and most keys have different names, but occasionally there are distinct keys with the same name. Then you might use a two-level table: first hash on the key, and then, only in buckets where there is more than one entry, calculate the hash of the extra data.

In the case of a string, the closest thing would be to hash only a prefix. But that typically gives bad results in practice; for example, in a compiler, it's very common to have large sets of identifiers with a common prefix.

Another case where a simpler, partial hash function can be useful is when equality between keys is hard to test. This may be the case with Unicode strings if you need to treat different representations of the same text as equal, e.g. treat combining characters as equivalent to non-canonical forms. In this case, you may want to avoid doing the work of normalizing each string. However that wouldn't help for the pure-ASCII case, since normalizing a pure-ASCII string is easy. It might help with typical “tame” uses of Unicode (sticking to characters that are common in one language).

A hash table is not necessarily the best structure to represent a mapping from keys to values. Search trees or tries have many advantages. Balanced search trees have guaranteed $O(\lg(n))$ behavior, whereas hash tables are harder to protect against deliberately-crafted key sets (not so much an issue in compilers, but it can be an issue when interpreting code from an untrusted source, e.g. a web browser running Javascript code from some random website). Hash tables are pretty much impossible to share intelligently — you have to copy the whole table. With trees, on the other hand, sharing comes naturally. Sharing is very often useful in compilers, between scopes that differ only on a few identifiers.

$\endgroup$
  • $\begingroup$ "You can either make the hash function faster or better, not both" - false, example is obvious. "Hash functions are designed to spread out likely key values in the first place." - false, look at the definition at least. Etc. Not wrong remainder - isn't an answer. $\endgroup$ – Les Aug 11 '16 at 7:41
  • $\begingroup$ @Les Obviously it's possible to design a hash function that is both slow and collision prone, but people don't use them. This statement is obviously not mathematically correct, but it's meaningful from an engineering point of view. Spreading out values is not a mathematical requirement for a hash function, but it's why one hash function would be picked over another, so yes, hash functions are designed to spread values out. $\endgroup$ – Gilles 'SO- stop being evil' Aug 11 '16 at 7:43
  • $\begingroup$ This is a science portal, so, the definitions are primarily scientific as well. However, your claims are all still invalid. To be specific about one of them... No, there're many engineering cases when hash should do collisions for optimization purposes. One case, when you squeeze known as rarely accessed entries in a few buckets of a static map while pumping data into your map for optimizing accessing to the hotspots later without other tradeoffs. Yes, there're other ways as nested maps or different storages, but this as is totally disproves your "they're designed for collision minimization." $\endgroup$ – Les Aug 11 '16 at 8:36
-1
$\begingroup$

Shortly, yes, - you can use this information for improvements. But you should define a current implementation and an optimization goal for a precise answer.

For example, you could optimize average search by key time. Let's assume that the "ASCII" set means that the last bit inside the utf-8 (8 bit) set is zero. Let's assume that you'd been used a naive hash Map and hash function as implementation. Always 8 buckets (static), the unsophisticated hash function is the last 3 bits. All ASCII symbols appear uniformly, and the utf-8's remainder chars are "very sparse."

Optimization: change the last 3 bits to the first three bits. You just get rid from "almost"(depending on the "very sparse") 1/3 adding hash collisions. Look at any article about hash Map's performance to figure out what performance boost you got via elimination of 1/3 hash collisions on average. Operations complexity for Java's HashMaps.

Avg. situation changed like. (hash function time + 1 or 2 operations with list for accessing)

000 - "NUL"(00000000)" -> "7" (11100000)

(a bucket with "000" hash label and two collided elements)

010 - "ESC(00111010)"

becomes (hash calculation + 1 operation)

000 - "NUL"

111 - "7"

001 - "ESC"

If there was no "very sparse" utf-8 remainder (and non-uniform access patterns) both hash functions act in the mentioned aspect equally. This is how, in principle, we can use size, keys, values, access patterns distribution and other use-cases info for optimizations.

$\endgroup$
  • $\begingroup$ Assuming a stupid hash function (very collision-prone in a way that doesn't make the function faster to calculate) isn't a useful consideration. $\endgroup$ – Gilles 'SO- stop being evil' Aug 11 '16 at 0:14
  • $\begingroup$ Just to be clear - I know this way, minus other who can't downvote yours, write your own. My answer isn't ideal as a question, but your answer is incorrect in many points, and I don't care about karma, for the record. Showing a naive hash as a clear concept demonstration... nothing wrong with it. Principle that you can gain fewer collisions or other improvements with a more precise distribution info still stands and very useful. Thanks for the feedback, however. $\endgroup$ – Les Aug 11 '16 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.