4 ms·
I read TFA discussion of performance issues for hashmaps, and I see that deletes are something of a serious hindrance. As I often use hashmaps for a single-pas
by lucas_membrane 8y ago
I read TFA discussion of performance issues for hashmaps, and I see that deletes are something of a serious hindrance. As I often use hashmaps for a single-pass accumulation or transformation of data, I suspect that a hashmap without a delete operator might be designed to give superior performance in many such cases. Is this so, and are there any such implementations of hashmaps, mutable but with no delete method?
- samcheng 8y agoBloom filters are an example of a hashing data structure that does not support delete. So yes, such a tradeoff can be made. Maybe some DHT implementations also make deletion hard? (In general, I'd much rather mark something as invalid than delete it.)
- kccqzy 8y agoI think GP is talking about improving performance just by omitting deletion support in hash maps. For example the tombstone marking in the original article won't be necessary. Experience tells me that for a host of data structures (vectors, BSTs, hash maps and many others), omitting deletion support can simplify the code a lot as well.
- adamnemecek 8y agoThere’s cuckoo filters.
- rurban 8y agoWithout the delete tombstone it can be made much faster, yes. I wrote one recently: https://github.com/LibreDWG/libredwg/blob/master/src/hash.c https://github.com/LibreDWG/libredwg/blob/master/src/hash.c
- easytiger 8y agowasn't the original folly hashmap exactly that?
- bogomipz 8y agoWhats the TFA discussion? Can you say why are deletes such a serious hindrance?