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:
Cloneable
,Iterable
,Collection
,Set
A lighter (on memory) hash set
Advantages over HashSet:
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 comparable 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 -
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionLightHashSet
(int initialCapacity) LightHashSet
(int initialCapacity, float loadFactor) -
Method Summary
Modifier and TypeMethodDescriptionboolean
boolean
addAll
(Collection c) private boolean
addInternal
(Object key, boolean bulkAdd) private void
adjustCapacity
(int newSize) int
capacity()
private void
checkCapacity
(int n) void
clear()
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
private int
Fetches an element which does equal() the provided object but is not necessarily the same objectiterator()
private boolean
static void
private int
nonModifyingFindIndex
(Object keyToFind) boolean
private void
removeForIndex
(int idx) int
size()
(package private) static void
test()
Methods inherited from class java.util.AbstractSet
equals, hashCode, removeAll
Methods inherited from class java.util.AbstractCollection
containsAll, isEmpty, retainAll, toArray, toArray, toString
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Collection
parallelStream, removeIf, stream, toArray
Methods inherited from interface java.util.Set
containsAll, isEmpty, retainAll, spliterator, toArray, toArray
-
Field Details
-
THOMBSTONE
-
NULLKEY
-
DEFAULT_LOAD_FACTOR
private static final float DEFAULT_LOAD_FACTOR- See Also:
-
DEFAULT_CAPACITY
private static final int DEFAULT_CAPACITY- See Also:
-
loadFactor
final float loadFactor -
size
int size -
data
Object[] data
-
-
Constructor Details
-
LightHashSet
public LightHashSet() -
LightHashSet
public LightHashSet(int initialCapacity) -
LightHashSet
-
LightHashSet
public LightHashSet(int initialCapacity, float loadFactor)
-
-
Method Details
-
clone
-
iterator
- Specified by:
iterator
in interfaceCollection
- Specified by:
iterator
in interfaceIterable
- Specified by:
iterator
in interfaceSet
- Specified by:
iterator
in classAbstractCollection
-
add
- Specified by:
add
in interfaceCollection
- Specified by:
add
in interfaceSet
- Overrides:
add
in classAbstractCollection
-
size
public int size()- Specified by:
size
in interfaceCollection
- Specified by:
size
in interfaceSet
- Specified by:
size
in classAbstractCollection
-
addAll
- Specified by:
addAll
in interfaceCollection
- Specified by:
addAll
in interfaceSet
- Overrides:
addAll
in classAbstractCollection
-
capacity
public int capacity() -
get
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
-
remove
- Specified by:
remove
in interfaceCollection
- Specified by:
remove
in interfaceSet
- Overrides:
remove
in classAbstractCollection
-
removeForIndex
private void removeForIndex(int idx) -
clear
public void clear()- Specified by:
clear
in interfaceCollection
- Specified by:
clear
in interfaceSet
- Overrides:
clear
in classAbstractCollection
-
contains
- Specified by:
contains
in interfaceCollection
- Specified by:
contains
in interfaceSet
- Overrides:
contains
in classAbstractCollection
-
keysEqual
-
findIndex
-
nonModifyingFindIndex
-
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
-