I have a "standard" problem, but I can't remember its "official" name: I have to keep track of the presence of the absence of value in an array.
Currently I use an each bits of an other array to track it. Let's say I have a byte array of 8k elements if I want to know if a place is taken (without accessing to the array), I need a 1k byte array (8 bits per byte) to track it. So I have more or less these complexities:
- Check: $O(1)$
- Change: $O(1)$
- Memory: $O(n/8)$
I wanted to know if there's a more memory optimized data structure keep the constant check factor because I have the following properties:
- The targetted array has a fixed size known at compile-time
- Most of the actions performed are Check (maybe 10k-1k checks for one change)
- The array is mostly sparsed (5-25% used)
- There are only few space freeing
- Sometimes a value take more than one byte but I only need to keep track of the first one.
I'm looking for data-structures name or samples. Thanks.