Skip to content

Instantly share code, notes, and snippets.

@SolidAlloy

SolidAlloy/HashMap.cs

Last active September 29, 2025 10:55
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save SolidAlloy/f430d7b6b715aef4ca7394d1ba208db0 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save SolidAlloy/f430d7b6b715aef4ca7394d1ba208db0 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. SolidAlloy revised this gist Sep 29, 2025. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion HashMap.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -55,7 +55,7 @@ public bool TryGetValue(TKey key, out TValue value)
    return false;
    }

    public ref TValue GetOrAddValueRef(TKey key, out bool exists)
    public ref TValue GetOrAddValue(TKey key, out bool exists)
    {
    if (NeedsResize(_count + 1)) Resize(Buckets.Length << 1);

  2. SolidAlloy revised this gist Sep 29, 2025. 1 changed file with 3 additions and 8 deletions.
    11 changes: 3 additions & 8 deletions HashMap.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,7 @@
    [StructLayout(LayoutKind.Auto)]
    public struct HashMap<TKey, TValue> where TKey : IEquatable<TKey>
    {
    [StructLayout(LayoutKind.Auto)]
    public struct Entry
    {
    public int Hash; // 0 == empty
    @@ -189,14 +191,7 @@ public bool Remove(TKey key)
    for (int hole = idxFound, next = (hole + 1) & _mask; ; hole = next, next = (next + 1) & _mask)
    {
    ref Entry e = ref Buckets[next];
    if (e.Hash == 0)
    {
    Buckets[hole] = default;
    --_count;
    return true;
    }

    if (e.Dib == 0)
    if (e.Hash == 0 || e.Dib == 0)
    {
    Buckets[hole] = default;
    --_count;
  3. SolidAlloy renamed this gist Sep 6, 2025. 1 changed file with 24 additions and 35 deletions.
    59 changes: 24 additions & 35 deletions BackshiftHashMap.cs → HashMap.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,4 @@
    public struct BackshiftHashMap<TKey, TValue> where TKey : IEquatable<TKey>
    public struct HashMap<TKey, TValue> where TKey : IEquatable<TKey>
    {
    public struct Entry
    {
    @@ -17,10 +17,10 @@ public struct Entry
    public int Count => _count;
    public int Capacity => Buckets.Length;

    public BackshiftHashMap(int initialCapacity = 8)
    public HashMap(int initialCapacity = 8)
    {
    if (initialCapacity < 1) initialCapacity = 1;
    int cap = NextPow2(initialCapacity);
    int cap = Mathf.NextPowerOfTwo(Mathf.CeilToInt(initialCapacity * MaxLoadFactor));
    Buckets = new Entry[cap];
    _mask = cap - 1;
    _count = 0;
    @@ -30,7 +30,7 @@ public BackshiftHashMap(int initialCapacity = 8)

    public bool TryGetValue(TKey key, out TValue value)
    {
    int hash = Fmix32NonZero(key.GetHashCode());
    int hash = MixNonZero(key.GetHashCode());
    int init = hash & _mask;

    for (int i = 0; i < Buckets.Length; ++i)
    @@ -59,22 +59,22 @@ public ref TValue GetOrAddValueRef(TKey key, out bool exists)

    var buckets = Buckets;
    int mask = _mask;
    int hash = Fmix32NonZero(key.GetHashCode());
    int hash = MixNonZero(key.GetHashCode());
    int init = hash & mask;

    // We'll insert this if missing; DIB will be set when placed.
    var entryToInsert = new Entry { Hash = hash, Dib = 0, Key = key, Value = default };
    int placedIndex = -1;

    for (int i = 0; ; ++i)
    for (int i = 0, currentDib = 0; ; ++i, ++currentDib)
    {
    int idx = (init + i) & mask;
    ref var e = ref buckets[idx];

    if (e.Hash == 0)
    {
    // place new
    entryToInsert.Dib = i;
    entryToInsert.Dib = currentDib;
    e = entryToInsert;
    ++_count;

    @@ -86,10 +86,8 @@ public ref TValue GetOrAddValueRef(TKey key, out bool exists)
    {
    return ref e.Value;
    }
    else
    {
    return ref Buckets[placedIndex].Value;
    }

    return ref Buckets[placedIndex].Value;

    }

    @@ -100,19 +98,19 @@ public ref TValue GetOrAddValueRef(TKey key, out bool exists)
    }

    // Robin-Hood: newcomer steals if its DIB (i) > resident's DIB
    if (i > e.Dib)
    if (currentDib > e.Dib)
    {
    // swap: newcomer takes slot with its current DIB (i)
    var tmpEntry = e;
    e = entryToInsert;
    e.Dib = i;
    e.Dib = currentDib;

    if (placedIndex < 0)
    placedIndex = idx;

    // displaced continues probing with its own DIB (tmp.Dib)
    entryToInsert = tmpEntry;
    i = entryToInsert.Dib; // continue from resident's DIB
    currentDib = entryToInsert.Dib; // continue from resident's DIB
    }
    }
    }
    @@ -124,19 +122,19 @@ public bool Add(TKey key, in TValue value)
    if (NeedsResize(_count + 1))
    Resize(Buckets.Length << 1);

    int hash = Fmix32NonZero(key.GetHashCode());
    int hash = MixNonZero(key.GetHashCode());
    int init = hash & _mask;

    Entry entryToInsert = new Entry { Hash = hash, Dib = 0, Key = key, Value = value };

    for (int i = 0; ; ++i)
    for (int i = 0, currentDib = 0; ; ++i, ++currentDib)
    {
    int idx = (init + i) & _mask;
    ref Entry e = ref Buckets[idx];

    if (e.Hash == 0)
    {
    entryToInsert.Dib = i;
    entryToInsert.Dib = currentDib;
    e = entryToInsert;
    ++_count;
    return true;
    @@ -148,15 +146,15 @@ public bool Add(TKey key, in TValue value)
    return false;
    }

    if (i > e.Dib)
    if (currentDib > e.Dib)
    {
    // swap with DIB maintenance
    var tmpEntry = e;
    e = entryToInsert;
    e.Dib = i;
    e.Dib = currentDib;

    entryToInsert = tmpEntry;
    i = entryToInsert.Dib;
    currentDib = entryToInsert.Dib;
    }
    }
    }
    @@ -165,7 +163,7 @@ public bool Remove(TKey key)
    {
    if (_count == 0) return false;

    int hash = Fmix32NonZero(key.GetHashCode());
    int hash = MixNonZero(key.GetHashCode());
    int init = hash & _mask;

    int idxFound = -1;
    @@ -209,7 +207,6 @@ public bool Remove(TKey key)
    Entry moved = e;
    moved.Dib -= 1;
    Buckets[hole] = moved;

    Buckets[next] = default;
    }
    }
    @@ -223,7 +220,7 @@ public void Clear()
    public void EnsureCapacity(int desired)
    {
    if (desired <= Capacity) return;
    Resize(NextPow2(desired));
    Resize(Mathf.NextPowerOfTwo(desired));
    }

    #endregion
    @@ -232,7 +229,7 @@ public void EnsureCapacity(int desired)

    private void Resize(int newCapacity)
    {
    newCapacity = NextPow2(Math.Max(newCapacity, 1));
    newCapacity = Mathf.NextPowerOfTwo(Math.Max(newCapacity, 1));

    Entry[] old = Buckets;
    Buckets = new Entry[newCapacity];
    @@ -280,22 +277,14 @@ private void Resize(int newCapacity)
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private bool NeedsResize(int futureCount) => futureCount > (int)(MaxLoadFactor * Buckets.Length);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int NextPow2(int v)
    {
    uint x = (uint)(v - 1);
    x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16;
    return (int)(x + 1);
    }

    #endregion

    // cheap mixer; maps 0 to non-zero for empty-sentinel
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int Fmix32NonZero(int h)
    private static int MixNonZero(int h)
    {
    uint x = (uint)h * 0x9E3779B1u; // golden ratio multiply
    if (x == 0) x = 1;
    return (int)x;
    }

    #endregion
    }
  4. SolidAlloy revised this gist Aug 12, 2025. No changes.
  5. SolidAlloy revised this gist Aug 12, 2025. 1 changed file with 0 additions and 4 deletions.
    4 changes: 0 additions & 4 deletions BackshiftHashMap.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -280,10 +280,6 @@ private void Resize(int newCapacity)
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private bool NeedsResize(int futureCount) => futureCount > (int)(MaxLoadFactor * Buckets.Length);

    // kept for reference; not used in hot path anymore since we store DIB.
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private int Dist(int init, int current) => (int)((uint)(current - init) & (uint)_mask);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int NextPow2(int v)
    {
  6. SolidAlloy created this gist Aug 12, 2025.
    305 changes: 305 additions & 0 deletions BackshiftHashMap.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,305 @@
    public struct BackshiftHashMap<TKey, TValue> where TKey : IEquatable<TKey>
    {
    public struct Entry
    {
    public int Hash; // 0 == empty
    public int Dib; // distance-to-initial-bucket for this slot (0 for home)
    public TKey Key;
    public TValue Value;
    }

    public Entry[] Buckets;
    private int _count;
    private int _mask;

    private const float MaxLoadFactor = 0.85f;

    public int Count => _count;
    public int Capacity => Buckets.Length;

    public BackshiftHashMap(int initialCapacity = 8)
    {
    if (initialCapacity < 1) initialCapacity = 1;
    int cap = NextPow2(initialCapacity);
    Buckets = new Entry[cap];
    _mask = cap - 1;
    _count = 0;
    }

    #region Public API

    public bool TryGetValue(TKey key, out TValue value)
    {
    int hash = Fmix32NonZero(key.GetHashCode());
    int init = hash & _mask;

    for (int i = 0; i < Buckets.Length; ++i)
    {
    int idx = (init + i) & _mask;
    ref Entry e = ref Buckets[idx];
    int eHash = e.Hash;

    if (eHash == 0) break; // empty bucket => not found
    if (i > e.Dib) break; // we passed where it could be

    if (eHash == hash && e.Key.Equals(key))
    {
    value = e.Value;
    return true;
    }
    }

    value = default!;
    return false;
    }

    public ref TValue GetOrAddValueRef(TKey key, out bool exists)
    {
    if (NeedsResize(_count + 1)) Resize(Buckets.Length << 1);

    var buckets = Buckets;
    int mask = _mask;
    int hash = Fmix32NonZero(key.GetHashCode());
    int init = hash & mask;

    // We'll insert this if missing; DIB will be set when placed.
    var entryToInsert = new Entry { Hash = hash, Dib = 0, Key = key, Value = default };
    int placedIndex = -1;

    for (int i = 0; ; ++i)
    {
    int idx = (init + i) & mask;
    ref var e = ref buckets[idx];

    if (e.Hash == 0)
    {
    // place new
    entryToInsert.Dib = i;
    e = entryToInsert;
    ++_count;

    // we displaced the original, remembered its placed index, so returning placedIndex
    // if placedIndex == -1, we didn't move anything
    exists = false;

    if (placedIndex == -1)
    {
    return ref e.Value;
    }
    else
    {
    return ref Buckets[placedIndex].Value;
    }

    }

    if (e.Hash == hash && e.Key.Equals(key))
    {
    exists = true;
    return ref e.Value;
    }

    // Robin-Hood: newcomer steals if its DIB (i) > resident's DIB
    if (i > e.Dib)
    {
    // swap: newcomer takes slot with its current DIB (i)
    var tmpEntry = e;
    e = entryToInsert;
    e.Dib = i;

    if (placedIndex < 0)
    placedIndex = idx;

    // displaced continues probing with its own DIB (tmp.Dib)
    entryToInsert = tmpEntry;
    i = entryToInsert.Dib; // continue from resident's DIB
    }
    }
    }

    public bool ContainsKey(TKey key) => TryGetValue(key, out _);

    public bool Add(TKey key, in TValue value)
    {
    if (NeedsResize(_count + 1))
    Resize(Buckets.Length << 1);

    int hash = Fmix32NonZero(key.GetHashCode());
    int init = hash & _mask;

    Entry entryToInsert = new Entry { Hash = hash, Dib = 0, Key = key, Value = value };

    for (int i = 0; ; ++i)
    {
    int idx = (init + i) & _mask;
    ref Entry e = ref Buckets[idx];

    if (e.Hash == 0)
    {
    entryToInsert.Dib = i;
    e = entryToInsert;
    ++_count;
    return true;
    }

    if (e.Hash == hash && e.Key.Equals(key))
    {
    e.Value = value; // overwrite existing
    return false;
    }

    if (i > e.Dib)
    {
    // swap with DIB maintenance
    var tmpEntry = e;
    e = entryToInsert;
    e.Dib = i;

    entryToInsert = tmpEntry;
    i = entryToInsert.Dib;
    }
    }
    }

    public bool Remove(TKey key)
    {
    if (_count == 0) return false;

    int hash = Fmix32NonZero(key.GetHashCode());
    int init = hash & _mask;

    int idxFound = -1;

    for (int i = 0; i < Buckets.Length; ++i)
    {
    int idx = (init + i) & _mask;
    ref Entry e = ref Buckets[idx];

    if (e.Hash == 0) break;
    if (i > e.Dib) break;

    if (e.Hash == hash && e.Key.Equals(key))
    {
    idxFound = idx;
    break;
    }
    }

    if (idxFound < 0) return false;

    // Backshift compaction: shift entries left until a home or empty
    for (int hole = idxFound, next = (hole + 1) & _mask; ; hole = next, next = (next + 1) & _mask)
    {
    ref Entry e = ref Buckets[next];
    if (e.Hash == 0)
    {
    Buckets[hole] = default;
    --_count;
    return true;
    }

    if (e.Dib == 0)
    {
    Buckets[hole] = default;
    --_count;
    return true;
    }

    // Move e back into the hole; DIB decreases by 1
    Entry moved = e;
    moved.Dib -= 1;
    Buckets[hole] = moved;

    Buckets[next] = default;
    }
    }

    public void Clear()
    {
    Array.Clear(Buckets, 0, Buckets.Length);
    _count = 0;
    }

    public void EnsureCapacity(int desired)
    {
    if (desired <= Capacity) return;
    Resize(NextPow2(desired));
    }

    #endregion

    #region Internals

    private void Resize(int newCapacity)
    {
    newCapacity = NextPow2(Math.Max(newCapacity, 1));

    Entry[] old = Buckets;
    Buckets = new Entry[newCapacity];
    _mask = newCapacity - 1;

    _count = 0;

    for (int i = 0; i < old.Length; i++)
    {
    Entry e = old[i];
    if (e.Hash == 0) continue;

    int hash = e.Hash;
    int init = hash & _mask;

    // reinsert with correct DIB tracking
    for (int dib = 0; ; ++dib)
    {
    int idx = (init + dib) & _mask;
    ref Entry target = ref Buckets[idx];

    if (target.Hash == 0)
    {
    e.Dib = dib;
    target = e;
    ++_count;
    break;
    }

    if (dib > target.Dib)
    {
    // swap; set DIBs appropriately
    Entry tmp = target;

    target = e;
    target.Dib = dib;

    e = tmp;
    dib = e.Dib; // continue with displaced entry's DIB
    }
    }
    }
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private bool NeedsResize(int futureCount) => futureCount > (int)(MaxLoadFactor * Buckets.Length);

    // kept for reference; not used in hot path anymore since we store DIB.
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private int Dist(int init, int current) => (int)((uint)(current - init) & (uint)_mask);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int NextPow2(int v)
    {
    uint x = (uint)(v - 1);
    x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16;
    return (int)(x + 1);
    }

    #endregion

    // cheap mixer; maps 0 to non-zero for empty-sentinel
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static int Fmix32NonZero(int h)
    {
    uint x = (uint)h * 0x9E3779B1u; // golden ratio multiply
    if (x == 0) x = 1;
    return (int)x;
    }
    }