Comment by xnorswap | Hacker News Reader

Comment by xnorswap | Hacker News Reader

I've been implementing data structures like hash tables for a project I've been working on so it's interesting to see alternative approaches for easy to implement hash tables.

One particular note of agreement is regarding deletion. An "Insert only hash table" is a very useful data structure which can have performance improvements given the extra overhead needed to support deletion.

This is very similar to the design that dotnet uses for HashSet[1]. For deletion they use the term "freelist" rather than "gravestones" which is definitely less emotive language. ( They also use linear probing because it's generally much faster than double-hashing because branch prediction and memory look ahead and other things I don't fully understand mean that it can just grab the next X items from memory all at once before starting to compare them rather than having to jump around the array. )

One choice from OP's design which I find odd is the choice of power-of-2 for the table size. I was under the impression that choosing a table size of a prime number has significant advantages such as being able to more easily expand the table.

On a related note, my favourite hash-table is a fixed-size zero-probing "probabilistic" hash table where hash collisions are dealt with by just overwriting the hash. That makes the choice of a good size for the hash table a fun problem in itself. It's extremely fast to both implement and run if you don't mind the occasional bit of data loss, although the probability of data loss can be well controlled by choice of table size.

[1] https://github.com/dotnet/runtime/blob/4017327955f1d8ddc4398...

> One choice from OP's design which I find odd is the choice of power-of-2 for the table size. I was under the impression that choosing a table size of a prime number has significant advantages such as being able to more easily expand the table.

One advantage of power-of-two sizes is that you do not need an expensive integer modulus.

If your hash is decently uniform and fills 32 bits, you can avoid the modulus with

  i = ((uint64_t)hash * (uint64_t)size) >> 32;

Good trick. I thought about the approach of storing or computing the magic numbers for division by the primes you've chosen for the hash table lengths, but this is better.

Testing this using a size of 101, it only appears to give results up to 50. In fact in general appears to only give numbers up to size / 2, should that have been >> 31?

edit: Nevermind, I was converting to Uint but should have been returning Int, this gives results in (-50,50).

Adding size / 2 will get you back to the range (0,size-1) that you would want for assigning buckets.

I was also going to ask you why it needed to be "decently uniform" but then implementing it saw that the first thousand numbers all hash to the same value.

In fact, the first 21,262,215 numbers all hash to the same value with size = 101.

Given that .net implements Int32.GetHashCode(value) as "return value"[1], I would avoid this trick in practice in .net.

Please correct me if I've stuffed up my implementation!

https://referencesource.microsoft.com/#mscorlib/system/int32...

might you have used a signed hash value instead of unsigned? (or just one that never sets the top bit)

(0xffffffff*101)>>32 is 100, which is the expected maximum.

Yes this was it thanks, I was trying to fit it around where I use GetHashCode in my workflow which is signed in .net.

As you say the algorithm was correct.

The algorithm above is a 64bit to 32bit reduction method. It performs a 64bit mult and then discards the lower 32bit. I'm not sure if Daniel Lemire invented it as a alternative to modulo, as I've seen the method used before, but he certainly made it popular[1]

There is a 64bit version as well (2x64bit -> 64bit), that when compiled using 128bit multiplication is quite fast too.

The method made it's way into .NET runtime[2]. It is used in HashSet, Dictionary and ConcurrentDictionary today.

[1] https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-...

[2] https://github.com/dotnet/runtime/blob/c22f7f8c73766830b3262...

It is in my 1990 edition of Cormen, Leiserson & Rivest, chapter 12 “hash tables” section 12.3.2 “the multiplication method”, though they don’t explain the non-power-of-2 case in detail.

In this section of CLR the hash function is multiplication by A where 0 < A < 1, and take the fractional part of the result. In practice, as they explain, you can multiply by A * 2^32 and keep only the lower 32 bits of the result. Anyway, that gives you a full 32 bit hash (if A is good).

Then multiply by m (the size of the hash table) and take the floor (or drop the lower 32 bits of a 64 bit integer result). In CLR they discuss the case where m is a power of 2 and you don’t have a double-width multiply, so they pull the modulus out of the lower word, but the basic idea is still there.

> They also use linear probing because it's generally much faster than double-hashing

Optimal is probably to use linear probing for a few indices at a time (depending on size of hash table entries, say, 4 or 8), and double hashing to move to a new region if no empty elements can be found in that run.

If you can choose to have a quality hash function, it's probably better to do that.

Sure, but if you have a sufficiently high quality hash function this approach is equivalent to simple linear probing, as you will never need to probe more than the initial batch. So why not have this behaviour as a fallback?

A similar idea is to think of the linear probe segments as large buckets that can store multiple items. The difference is that the hash identifies the bucket rather than an individual slot, so you always scan the whole bucket rather than maybe landing in the middle of a segment.

>probably

based on what?

The fact that this provides the benefits of both approaches, namely that it is (branch) predictable and amortises memory latency while obtaining the probabilistic benefits of double hashing.

How is a prime number better for expanding the hash table?

I imagine having a prime number size might reduce the chance of collision, probably as a result of some property of modular arithmetic.

But if you’re using a decent (i.e. actually pseudorandom) hash function I would think this is moot?

Reply on news.ycombinator.com