org.apache.zookeeper.server.util

Class BitHashSet

java.lang.Object

org.apache.zookeeper.server.util.BitHashSet

All Implemented Interfaces:

Iterable<Integer>

public class BitHashSet
extends Object
implements Iterable<Integer>

Using BitSet to store all the elements, and use HashSet to cache limited number of elements to find a balance between memory and time complexity. Without HashSet, we need to use O(N) time to get the elements, N is the bit numbers in elementBits. But we need to keep the size small to make sure it doesn't cost too much in memory, there is a trade off between memory and time complexity. Previously, was deciding to dynamically switch between SparseBitSet and HashSet based on the memory consumption, but it will take time to copy data over and may have some herd effect of keep copying data from one data structure to anther. The current solution can do a very good job given most of the paths have limited number of elements.

Constructor Summary

Constructors

Constructor and Description
BitHashSet()
BitHashSet(int cacheSize)

Method Summary

Modifier and Type	Method and Description
boolean	add(Integer elementBit)
int	cachedSize()
boolean	contains(Integer elementBit)
boolean	isEmpty()
Iterator<Integer>	iterator() This function is not thread-safe, need to synchronized when iterate through this set.
boolean	remove(Integer elementBit)
int	remove(Set<Integer> bitSet, BitSet bits) Remove the watches, and return the number of watches being removed.
int	size()

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

BitHashSet

public BitHashSet()

BitHashSet

public BitHashSet(int cacheSize)

Method Detail

add

public boolean add(Integer elementBit)

remove

public int remove(Set<Integer> bitSet,
                  BitSet bits)

Remove the watches, and return the number of watches being removed.

remove

public boolean remove(Integer elementBit)

contains

public boolean contains(Integer elementBit)

size

public int size()

iterator

public Iterator<Integer> iterator()

This function is not thread-safe, need to synchronized when iterate through this set.

Specified by:

iterator in interface Iterable<Integer>

cachedSize

public int cachedSize()

isEmpty

public boolean isEmpty()