5 ms·
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 impleme
by xnorswap 4y ago
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/4017327955f1d8ddc43980eb1848c52fbb131dfc/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/HashSet.cs https://github.com/dotnet/runtime/blob/4017327955f1d8ddc4398...
- _benedict 4y ago> 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.
- anonymoushn 4y agoIf you can choose to have a quality hash function, it's probably better to do that.
- _benedict 4y agoSure, 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?
- fanf2 4y agoA 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.
- bruce343434 4y ago>probably based on what?
- _benedict 4y agoThe 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.
- anonymoushn 4y ago> 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.
- fanf2 4y agoIf your hash is decently uniform and fills 32 bits, you can avoid the modulus with i = ((uint64_t)hash * (uint64_t)size) >> 32;
- anonymoushn 4y agoGood 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.
- xnorswap 4y agoTesting 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.cs,86 https://referencesource.microsoft.com/#mscorlib/system/int32...
- dzaima 4y agomight 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.
- heavenlyblue 4y agoHow is a prime number better for expanding the hash table?
- bigyikes 4y agoI 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?