3 ms·

This is neat, and remarkably small. I personally need more comments in order to follow, say, the growth logic. I see it rehashes but I don't see how it doesn't

This is neat, and remarkably small. I personally need more comments in order to follow, say, the growth logic. I see it rehashes but I don't see how it doesn't potentially overwrite entries on the way. Algorithm for hash collisions is just to find the next empty slot (linear probing)? What happens when the original entry is removed, are the ones in subsequent slots cycled backwards? I don't see that... Also the name is new to me! TIL 'salmagundi' is an English word (not even a loan-word) for a type of salad made of many ingredients: an excellent name for a hash map that can contain many effectively random items.

e-dant 2y ago
I like the exercise of trying to find the simplest reasonable solution to some problem. Many of my toy and hobby projects are exactly that. Some make allowances for the sake of performance and generality. The hash map, though, is up there with sorting algorithms in the breadth of wild implementations. Salmagundi is unlikely to be the fastest, or the smartest. But it’s cute and portable.
- vintagedave 2y ago
  It's neat. I like it! I edited my comment with some more questions, btw, likely as you were answering - apologies if that ended up confusing.
  - e-dant 2y ago
    There’s no slot cycling logic. When a k,v pair at some index is deleted, and a different k,v pair has a matching hash, there’s a (small?) penalty in the hm_get logic that will eventually the right k,v pair. I need a bit more clarification on your first question. There should be no mutation of the underlying map when it grows — we’re just allocating more room for entries and adjusting the old map’s item “ownership” — moving pointers->items around.
    - e-dant 2y ago
      Nevermind — there are ways for deleting colliding items to cause other colliding items to be “forgotten”, and one solution would be to implement slot cycling on deletion
      - skitter 2y ago
        Another solution could be tombstones: When a slot gets cleared and the next slot has an item, insert a placeholder value. During linear probing, treat the placeholder as a normal item (that doesn't match); during insertion & deletion treat the placeholder as an empty slot.
andrelaszlo 2y ago
The etymology of 'salmagundi' seems pretty obscure. It might be a loan word? https://www.nytimes.com/1978/01/16/archives/the-salmagundi-debate-continues-a-cold-salad-another-source.html?unlocked_article_code=1.gE4.2AwC.1o6oO8yRk9aG https://www.nytimes.com/1978/01/16/archives/the-salmagundi-d... https://en.m.wiktionary.org/wiki/salmagundi https://en.m.wiktionary.org/wiki/salmagundi

e-dant 2y ago

I like the exercise of trying to find the simplest reasonable solution to some problem. Many of my toy and hobby projects are exactly that. Some make allowances for the sake of performance and generality. The hash map, though, is up there with sorting algorithms in the breadth of wild implementations. Salmagundi is unlikely to be the fastest, or the smartest. But it’s cute and portable.

vintagedave 2y ago
It's neat. I like it! I edited my comment with some more questions, btw, likely as you were answering - apologies if that ended up confusing.
- e-dant 2y ago
  There’s no slot cycling logic. When a k,v pair at some index is deleted, and a different k,v pair has a matching hash, there’s a (small?) penalty in the hm_get logic that will eventually the right k,v pair. I need a bit more clarification on your first question. There should be no mutation of the underlying map when it grows — we’re just allocating more room for entries and adjusting the old map’s item “ownership” — moving pointers->items around.
  - e-dant 2y ago
    Nevermind — there are ways for deleting colliding items to cause other colliding items to be “forgotten”, and one solution would be to implement slot cycling on deletion
    - skitter 2y ago
      Another solution could be tombstones: When a slot gets cleared and the next slot has an item, insert a placeholder value. During linear probing, treat the placeholder as a normal item (that doesn't match); during insertion & deletion treat the placeholder as an empty slot.

andrelaszlo 2y ago

The etymology of 'salmagundi' seems pretty obscure. It might be a loan word? https://www.nytimes.com/1978/01/16/archives/the-salmagundi-debate-continues-a-cold-salad-another-source.html?unlocked_article_code=1.gE4.2AwC.1o6oO8yRk9aG https://www.nytimes.com/1978/01/16/archives/the-salmagundi-d... https://en.m.wiktionary.org/wiki/salmagundi https://en.m.wiktionary.org/wiki/salmagundi