Answers · Making it fast enough
How can you check whether something is in a set without storing every item?
In shortRecord a few hashed marks per item in a bitmap; all marks set means probably present, any mark clear means certainly absent.
You keep a bitmap and set a few bits for every item you record. To ask whether an item has been seen, compute the same few positions and inspect those bits: if any one is clear, the item is definitely absent; if all are set, it is probably present, with a small chance that other items set those bits.
Here b is the number of bits of memory allowed per recorded item, k is the number of marks made for each item, and p is the chance that an item never recorded is reported present. The inner term is the chance that one chosen bit has been set by somebody; raising it to k demands that all k marks of the absent item be set at once. The number of recorded items is hidden inside b, which is why the same formula works at any size once the bitmap has been sized for the count.
At ten bits per item and seven marks, the false present rate is therefore about 0.008, or eight in a thousand, just under one per cent. That is the usual working point: ten bits is 1.25 bytes per item. For a hundred thousand items the bitmap is 100,000 times 10 = 1,000,000 bits, which is 125,000 bytes. Storing the same hundred thousand keys at forty bytes each would take 4,000,000 bytes, thirty-two times as much. At ten million items the bitmap is 12,500,000 bytes, about 12.5 megabytes, against 400 megabytes for the keys. The arithmetic scales because ten bits per item is a rate, not a fixed allowance.
The mark count trades both ways. At one mark per item p falls slowly as bits are added. At too many marks the bitmap fills faster than the extra evidence helps, and p rises again. For a fixed bit budget the best k is about 0.7b; at b=10 that is k=7, and at b=20 it is about 14. Ten bits with seven marks gives p=0.008; five bits with three marks gives e^{-3/5}=0.5488, 1-0.5488=0.4512, and 0.4512^3=0.0918, about 9 per cent. Halving the memory has multiplied the error by roughly eleven.
The mistaken picture
The natural guess is that membership needs the items themselves, or at least a compressed copy of each one. It does not. A list answers by comparing a query with stored keys; the bitmap answers by checking an overlap of marks. The overlap is evidence, not proof. Any recorded item has all its bits set, so it is never reported absent, because recording only sets bits and nothing clears them. An unrecorded item is reported absent as soon as one of its bits is clear. The failure is the other direction: an unrecorded item can have all its bits set by coincidence and be reported present. That error is one-sided by construction, not by luck.
A small example makes the failure visible. With sixteen bits and three marks, record apple at positions 2, 7 and 11; pear at 4, 7 and 13; plum at 1, 11 and 14. The set bits are then 1, 2, 4, 7, 11, 13 and 14. Ask about damson at 2, 11 and 13. All three are set, so the answer is present, although damson was never recorded. Sixteen bits for three items is 5.33 bits each, well below ten, so a false alarm at this rate is expected rather than mysterious.
Where the guarantee ends
The guarantee lasts only while bits are only set, never cleared. Deleting an item by clearing its marks is unsafe: another item may share a mark, and clearing it would make that other item report absent. Deletion needs counters per position or a rebuild from the surviving keys. The size has to be chosen for the maximum number of items, because recording more than planned lowers b and raises p. If the answer must be exact, or the items must be listed or counted, this structure cannot supply it. A false present is tolerable only when it triggers one extra exact check; if a wrong yes is itself costly, the saving disappears.
The marks must be spread by a hash function that behaves uniformly over the bitmap. If positions cluster, the same b and k give a worse p than the formula, because the effective number of usable positions is smaller. Uniformity is an assumption of the arithmetic, not a property of the bitmap.
Worth keeping
- With ten bits per item and seven marks, the false present rate is about 0.8 per cent, and the formula depends on bits per item and marks, not on item count.
- A bitmap never reports a recorded item absent as long as no bits are cleared, so its error is only false present.
- Deleting by clearing bits breaks that guarantee, because another item may share the bit.
Where this goes next
This question is one step of Finding It Instantly, a course that works through its subject from the beginning. The page that teaches this part of it is Asking Only Whether It Is There, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- How does a hash function turn a word into an array index?A hash function reads the word as bytes, mixes them into one large number, then takes the remainder after dividing by the table size to get an index from zero to size minus one.
- Why can a hash table find something without scanning everything else?A hash table does not search its contents faster. It computes where the item must sit from the key itself, so the number of stored items never enters the calculation.
- Why can't a hash table give me the next key in order?Because a good hash deliberately scatters neighbouring keys, so the table keeps no record of which key comes after which; finding the next key means reading every entry.
- Why does a hash table need to grow before it is completely full?Because what makes lookup fast is how full the table is, not how big it is: near full, a lookup turns into a scan well before the last slot is taken.
- Why doesn't breadth-first search give the cheapest path once the links have different costs?Breadth-first search counts links rather than costs, so it can return a route with fewer links that is more expensive than a longer route.
- Why is O(2n) treated the same as O(n)?Because it describes how cost grows rather than exact cost, doubling every cost does not change the growth class.