[BlitzMap] Shorten chain after remove?

[artelk]

I wonder if it is possible to shorten the chain after removing the entry by changing the code somewhere here:

Faster.Map/src/BlitzMap.cs

Lines 656 to 657 in 594d2e4

	// Set the erased bucket to inactive
	_buckets[index].Signature = INACTIVE;

(btw, I believe that can be just bucket.Signature = INACTIVE).
I tried to change that to

if (bucket.Next != INACTIVE)
{
    ref var nextBucket = ref Unsafe.Add(ref bucketBase, bucket.Next);
    bucket = nextBucket; // shorten the chain
    nextBucket.Signature = INACTIVE; // the next Bucket is free to use
    // keep nextBucket.Next unchanged so both will have the same tail
}
else
{
    // Set the erased bucket to inactive
    bucket.Signature = INACTIVE;
    //bucket.Next is INACTIVE here
}

But after the change the FindLastBucket started crashing sometimes because it couldn't find the bucket in the chain...

Did I miss something?
Does it make sence to try to shorten the chains after removing entries? 😄
Did you consider to add uint ownerBucketIndex; to Entry to avoid going though the chain?

[Wsm2110]

When designing a hashmap, there’s no such thing as a free lunch, it’s all about trade-offs. Shortening chains might improve lookup performance, but it can severely degrade insert and remove speeds. Ultimately, it all depends on your specific requirements. This hashmap offers the most well-rounded performance overal Op ma 21 jul 2025, 17:04 schreef Artem Elkin ***@***.***>:

…

I wonder if it is possible to shorten the chain after removing the entry by changing the code somewhere here: https://github.com/Wsm2110/Faster.Map/blob/594d2e4cf9d7d8556cd1de0ac6797d597defc933/src/BlitzMap.cs#L656-L657 (btw, I believe that can be just bucket.Signature = INACTIVE). I tried to change that to if (bucket.Next != INACTIVE){ ref var nextBucket = ref Unsafe.Add(ref bucketBase, bucket.Next); bucket = nextBucket; // shorten the chain nextBucket.Signature = INACTIVE; // the next Bucket is free to use // keep nextBucket.Next unchanged so both will have the same tail}else{ // Set the erased bucket to inactive bucket.Signature = INACTIVE; //bucket.Next is INACTIVE here} But after the change the FindLastBucket started crashing sometimes because it couldn't find the bucket in the chain... Did I miss something? Does it make sence to try to shorten the chains after removing entries? 😄 Did you consider to add uint ownerBucketIndex; to Entry to avoid going though the chain? — Reply to this email directly, view it on GitHub <#48>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AD4KISNOFGWDCN7OZTT3UGT3JT6ORAVCNFSM6AAAAACCAD7DN6VHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZYGYYTMMZQGM> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>