# Hashing to Estimate the Size of a Stream

DevFeed: [Hashing to Estimate the Size of a Stream](<https://devfeed.tech/articles/hashing-to-estimate-the-size-of-a-stream-40394.md>)

Original publisher: [Read original article](<https://www.jeremykun.com/2016/01/04/hashing-to-estimate-the-size-of-a-stream/>)

Published: 2016-01-04T09:00:37Z

Content type: tutorial

Language: en

Sources: [Jeremy Kun](<https://devfeed.tech/sources/jeremy-kun.md>)

Topics: [hashing](<https://devfeed.tech/topics/hashing.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>), [data](<https://devfeed.tech/topics/data.md>), [Python](<https://devfeed.tech/topics/python.md>), [parallel](<https://devfeed.tech/topics/parallel.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [approximation-algorithms](<https://devfeed.tech/tags/approximation-algorithms.md>), [data](<https://devfeed.tech/tags/data.md>), [hashing](<https://devfeed.tech/tags/hashing.md>), [mathematics](<https://devfeed.tech/tags/mathematics.md>), [parallel](<https://devfeed.tech/tags/parallel.md>), [programming](<https://devfeed.tech/tags/programming.md>), [python](<https://devfeed.tech/tags/python.md>), [sublinear-algorithms](<https://devfeed.tech/tags/sublinear-algorithms.md>)

## AI overview

This article explains how random hash functions can estimate the number of distinct items in a data stream that is too large to fit in memory. It presents a Python implementation using minimum hash values and parallel hashes to reduce variance, and states approximation guarantees for the estimate.

## Source excerpt

Problem: Estimate the number of distinct items in a data stream that is too large to fit in memory. Solution: (in python) import random def randomHash(modulus): a, b = random.randint(0,modulus-1), random.randint(0,modulus-1) def f(x): return (a*x + b) % modulus return f def average(L): return sum(L) / len(L) def numDistinctElements(stream, numParallelHashes=10): modulus = 2**20 hashes = [randomHash(modulus) for _ in range(numParallelHashes)] minima = [modulus] * numParallelHashes currentEstimate = 0 for i in stream: hashValues = [h(i) for h in hashes] for i, newValue in enumerate(hashValues): if newValue < minima[i]: minima[i] = newValue currentEstimate = modulus / average(minima) yield currentEstimate Discussion: The technique used here is to use random hash functions.