Хэширование: 2-независимость, k-независимость. Задача поиска числа различных элементов. Алгоритм Флажолета-Мартна (приближение $[d / 3, d \cdot 3]$). Алгоритм Бара-Йозева и др. $(\varepsilon, \delta)$-аппроксимация.
Источники:
- Probabilistic counting algorithms for data base applications, Flajolet, Philippe; Martin, G. Nigel, 1985
- On adaptive sampling, Flajolet, Philippe, 1990
- Counting Distinct Elements in a Data Stream, Ziv Bar-yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar , Luca Trevisan, 2002
- Tight Lower Bounds for the Distinct Elements Problem, Piotr Indyk, David Woodruff, 2003
- https://en.wikipedia.org/wiki/K-independent_hashing
- http://research.neustar.biz/2011/12/05/choosing-a-good-hash-function-part-1/ http://research.neustar.biz/2011/12/29/choosing-a-good-hash-function-part-2/ http://research.neustar.biz/2012/02/02/choosing-a-good-hash-function-part-3/
