Package com.biglybt.core.util
Class LightHashSet
- java.lang.Object
-
- java.util.AbstractCollection<E>
-
- java.util.AbstractSet
-
- com.biglybt.core.util.LightHashSet
-
- All Implemented Interfaces:
java.lang.Cloneable
,java.lang.Iterable
,java.util.Collection
,java.util.Set
public class LightHashSet extends java.util.AbstractSet implements java.lang.Cloneable
A lighter (on memory) hash set
Advantages over HashSet:- Lower memory footprint
- Everything is stored in a single array, this might improve cache performance (not verified)
- Read-only operations on iterators should be concurrency-safe but they might return null values unexpectedly under concurrent modification (not verified)
- removal is implemented with thombstone-keys, this can significantly increase the lookup time if many values are removed. Use compactify() for scrubbing
- entry set iterators and thus transfers to other maps are slower than compareable implementations
- the map does not store hashcodes and relies on either the key-objects themselves caching them (such as strings) or a fast computation of hashcodes
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
LightHashSet.HashIterator
-
Field Summary
Fields Modifier and Type Field Description (package private) java.lang.Object[]
data
private static int
DEFAULT_CAPACITY
private static float
DEFAULT_LOAD_FACTOR
(package private) float
loadFactor
private static java.lang.Object
NULLKEY
(package private) int
size
private static java.lang.Object
THOMBSTONE
-
Constructor Summary
Constructors Constructor Description LightHashSet()
LightHashSet(int initialCapacity)
LightHashSet(int initialCapacity, float loadFactor)
LightHashSet(java.util.Collection c)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
add(java.lang.Object key)
boolean
addAll(java.util.Collection c)
private boolean
addInternal(java.lang.Object key, boolean bulkAdd)
private void
adjustCapacity(int newSize)
int
capacity()
private void
checkCapacity(int n)
void
clear()
java.lang.Object
clone()
void
compactify(float compactingLoadFactor)
will shrink the internal storage size to the least possible amount, should be used after removing many entries for exampleboolean
contains(java.lang.Object key)
private int
findIndex(java.lang.Object keyToFind)
java.lang.Object
get(java.lang.Object key)
Fetches an element which does equal() the provided object but is not necessarily the same objectjava.util.Iterator
iterator()
private boolean
keysEqual(java.lang.Object o1, java.lang.Object o2)
static void
main(java.lang.String[] args)
private int
nonModifyingFindIndex(java.lang.Object keyToFind)
boolean
remove(java.lang.Object key)
private void
removeForIndex(int idx)
int
size()
(package private) static void
test()
-
Methods inherited from class java.util.AbstractCollection
containsAll, isEmpty, retainAll, toArray, toArray, toString
-
-
-
-
Field Detail
-
THOMBSTONE
private static final java.lang.Object THOMBSTONE
-
NULLKEY
private static final java.lang.Object NULLKEY
-
DEFAULT_LOAD_FACTOR
private static final float DEFAULT_LOAD_FACTOR
- See Also:
- Constant Field Values
-
DEFAULT_CAPACITY
private static final int DEFAULT_CAPACITY
- See Also:
- Constant Field Values
-
loadFactor
final float loadFactor
-
size
int size
-
data
java.lang.Object[] data
-
-
Method Detail
-
clone
public java.lang.Object clone()
- Overrides:
clone
in classjava.lang.Object
-
iterator
public java.util.Iterator iterator()
- Specified by:
iterator
in interfacejava.util.Collection
- Specified by:
iterator
in interfacejava.lang.Iterable
- Specified by:
iterator
in interfacejava.util.Set
- Specified by:
iterator
in classjava.util.AbstractCollection
-
add
public boolean add(java.lang.Object key)
- Specified by:
add
in interfacejava.util.Collection
- Specified by:
add
in interfacejava.util.Set
- Overrides:
add
in classjava.util.AbstractCollection
-
size
public int size()
- Specified by:
size
in interfacejava.util.Collection
- Specified by:
size
in interfacejava.util.Set
- Specified by:
size
in classjava.util.AbstractCollection
-
addAll
public boolean addAll(java.util.Collection c)
- Specified by:
addAll
in interfacejava.util.Collection
- Specified by:
addAll
in interfacejava.util.Set
- Overrides:
addAll
in classjava.util.AbstractCollection
-
capacity
public int capacity()
-
get
public java.lang.Object get(java.lang.Object key)
Fetches an element which does equal() the provided object but is not necessarily the same object- Parameters:
Object
- to retrieve- Returns:
- an object fulfilling the equals contract or null if no such object was found in this set
-
addInternal
private boolean addInternal(java.lang.Object key, boolean bulkAdd)
-
remove
public boolean remove(java.lang.Object key)
- Specified by:
remove
in interfacejava.util.Collection
- Specified by:
remove
in interfacejava.util.Set
- Overrides:
remove
in classjava.util.AbstractCollection
-
removeForIndex
private void removeForIndex(int idx)
-
clear
public void clear()
- Specified by:
clear
in interfacejava.util.Collection
- Specified by:
clear
in interfacejava.util.Set
- Overrides:
clear
in classjava.util.AbstractCollection
-
contains
public boolean contains(java.lang.Object key)
- Specified by:
contains
in interfacejava.util.Collection
- Specified by:
contains
in interfacejava.util.Set
- Overrides:
contains
in classjava.util.AbstractCollection
-
keysEqual
private boolean keysEqual(java.lang.Object o1, java.lang.Object o2)
-
findIndex
private int findIndex(java.lang.Object keyToFind)
-
nonModifyingFindIndex
private int nonModifyingFindIndex(java.lang.Object keyToFind)
-
checkCapacity
private void checkCapacity(int n)
-
compactify
public void compactify(float compactingLoadFactor)
will shrink the internal storage size to the least possible amount, should be used after removing many entries for example- Parameters:
compactingLoadFactor
- load factor for the compacting operation. Use 0f to compact with the load factor specified during instantiation. Use negative values of the desired load factors to compact only when it would reduce the storage size.
-
adjustCapacity
private void adjustCapacity(int newSize)
-
test
static void test()
-
main
public static void main(java.lang.String[] args)
-
-