net.i2p.router.util

Class DecayingHashSet

java.lang.Object

net.i2p.router.util.DecayingBloomFilter

net.i2p.router.util.DecayingHashSet

public class DecayingHashSet
extends DecayingBloomFilter

Double-buffered hash set with time-based decay for efficient data management.

Extends DecayingBloomFilter to provide dual-buffered hash sets with automatic decay switching between active and previous buffers. Optimized for high-throughput scenarios with frequent insertions and periodic cleanup operations.

Memory usage analysis shows significant optimization potential:

• 32 bytes, peak 10 entries in 1m (320 on fast routers)
• 4 bytes, peak 150 entries in 10s (1600 on fast routers)
• 8 bytes, peak 1K entries in 2m (36K on fast routers)
• 16 bytes, peak 15K entries in 10m (15K on fast routers)

Performance characteristics:

• Zero false positive rate for ≤8 byte keys
• 5.4E-20 false positive rate for larger keys
• Twice as fast as DBF in benchmarks
• Space-proportional traffic handling

Uses read/write locks with SimpleTimer2 for thread safety and efficient buffer switching without synchronization overhead.

Field Summary

Fields inherited from class net.i2p.router.util.DecayingBloomFilter

_context, _currentDuplicates, _decayEvent, _durationMs, _entryBytes, _keepDecaying, _log, _name, _reorganizeLock

Constructor Summary

Constructors

Constructor and Description
DecayingHashSet(I2PAppContext context, int durationMs, int entryBytes) Create a double-buffered hash set that will decay its entries over time.
DecayingHashSet(I2PAppContext context, int durationMs, int entryBytes, String name)

Method Summary

Modifier and Type	Method and Description
boolean	add(byte[] entry, int off, int len)
boolean	add(long entry)
void	clear()
protected void	decay()
double	getFalsePositiveRate() pointless, only used for logging elsewhere
int	getInsertedCount() unsynchronized but only used for logging elsewhere
boolean	isKnown(long entry)
void	stopDecaying() super doesn't call clear, but neither do the users, so it seems like we should here

Methods inherited from class net.i2p.router.util.DecayingBloomFilter

add, getCurrentDuplicateCount, getReadLock, getWriteLock, releaseReadLock, releaseWriteLock

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DecayingHashSet

public DecayingHashSet(I2PAppContext context,
                       int durationMs,
                       int entryBytes)

Create a double-buffered hash set that will decay its entries over time.

Parameters:

durationMs - entries last for at least this long, but no more than twice this long

entryBytes - how large are the entries to be added? 1 to 32 bytes

DecayingHashSet

public DecayingHashSet(I2PAppContext context,
                       int durationMs,
                       int entryBytes,
                       String name)

Parameters:

name - just for logging / debugging / stats

Method Detail

add

public boolean add(byte[] entry,
                   int off,
                   int len)

Overrides:

add in class DecayingBloomFilter

Returns:

true if the entry added is a duplicate

add

public boolean add(long entry)

Overrides:

add in class DecayingBloomFilter

Returns:

true if the entry added is a duplicate. the number of low order bits used is determined by the entryBytes parameter used on creation of the filter.

clear

public void clear()

Overrides:

clear in class DecayingBloomFilter

decay

protected void decay()

Overrides:

decay in class DecayingBloomFilter

getFalsePositiveRate

public double getFalsePositiveRate()

pointless, only used for logging elsewhere

Overrides:

getFalsePositiveRate in class DecayingBloomFilter

getInsertedCount

public int getInsertedCount()

unsynchronized but only used for logging elsewhere

Overrides:

getInsertedCount in class DecayingBloomFilter

isKnown

public boolean isKnown(long entry)

Overrides:

isKnown in class DecayingBloomFilter

Returns:

true if the entry is already known. this does NOT add the entry however.

stopDecaying

public void stopDecaying()

super doesn't call clear, but neither do the users, so it seems like we should here

Overrides:

stopDecaying in class DecayingBloomFilter