public class UnorderedSet<K>
extends java.lang.Object
implements java.util.Set<K>, java.io.Serializable, java.lang.Cloneable
OrderedSet
in this library, which is
based on the fastutil library's ObjectLinkedOpenHashSet class; the ordering and indexed access have been removed to
potentially reduce the time cost of insertion and removal at the expense of increasing time cost for access by index.
This does support optional hash strategies for array (and other) keys, which fastutil's collections can do in a
different way, and has better support than HashSet
for construction with an array of items or construction
with a Collection of items (this also helps addAll(Object[])
).
Instances of this class use a hash table to represent a set. The table is filled up to a specified load factor, and then doubled in size to accommodate new entries. If the table is emptied below one fourth of the load factor, it is halved in size. However, halving is not performed when deleting entries from an iterator, as it would interfere with the iteration process.
Note that clear()
does not modify the hash table size. Rather, a
family of trimming methods lets you control the size of
the table; this is particularly useful if you reuse instances of this class.
This class implements the interface of a Set, not a SortedSet.
You can pass an CrossHash.IHasher
instance such as CrossHash.generalHasher
as an extra parameter to
most of this class' constructors, which allows the OrderedSet to use arrays (usually primitive arrays) as items. If
you expect only one type of array, you can use an instance like CrossHash.intHasher
to hash int arrays, or
the aforementioned generalHasher to hash most kinds of arrays (it can't handle most multi-dimensional arrays well).
If you aren't using array items, you don't need to give an IHasher to the constructor and can ignore this feature.
Modifier and Type | Field and Description |
---|---|
protected boolean |
containsNull
Whether this set contains the key zero.
|
static int |
DEFAULT_INITIAL_SIZE
The initial default size of a hash table.
|
static float |
DEFAULT_LOAD_FACTOR
The default load factor of a hash table.
|
float |
f
The acceptable load factor.
|
static float |
FAST_LOAD_FACTOR
The load factor for a (usually small) table that is meant to be particularly fast.
|
protected CrossHash.IHasher |
hasher |
protected K[] |
key
The array of keys.
|
protected int |
mask
The mask for wrapping a position counter.
|
protected int |
maxFill
Threshold after which we rehash.
|
protected int |
n
The current table size.
|
protected int |
size
Number of entries in the set (including the key zero, if present).
|
static float |
VERY_FAST_LOAD_FACTOR
The load factor for a (usually very small) table that is meant to be extremely fast.
|
Constructor and Description |
---|
UnorderedSet()
Creates a new hash set with initial expected
DEFAULT_INITIAL_SIZE elements and
DEFAULT_LOAD_FACTOR as load factor. |
UnorderedSet(java.util.Collection<? extends K> c)
Creates a new hash set with
DEFAULT_LOAD_FACTOR as load
factor copying a given collection. |
UnorderedSet(java.util.Collection<? extends K> c,
CrossHash.IHasher hasher)
Creates a new hash set with
DEFAULT_LOAD_FACTOR as load
factor copying a given collection. |
UnorderedSet(java.util.Collection<? extends K> c,
float f)
Creates a new hash set copying a given collection.
|
UnorderedSet(java.util.Collection<? extends K> c,
float f,
CrossHash.IHasher hasher)
Creates a new hash set copying a given collection.
|
UnorderedSet(CrossHash.IHasher hasher)
Creates a new hash set with
DEFAULT_LOAD_FACTOR as load
factor. |
UnorderedSet(int expected)
Creates a new hash set with
DEFAULT_LOAD_FACTOR as load
factor. |
UnorderedSet(int expected,
CrossHash.IHasher hasher)
Creates a new hash set with
DEFAULT_LOAD_FACTOR as load
factor. |
UnorderedSet(int expected,
float f)
Creates a new hash map.
|
UnorderedSet(int expected,
float f,
CrossHash.IHasher hasher)
Creates a new hash map.
|
UnorderedSet(java.util.Iterator<? extends K> i)
Creates a new hash set with
DEFAULT_LOAD_FACTOR as load
factor using elements provided by a type-specific iterator. |
UnorderedSet(java.util.Iterator<? extends K> i,
float f)
Creates a new hash set using elements provided by a type-specific
iterator.
|
UnorderedSet(K[] a)
Creates a new hash set with
DEFAULT_LOAD_FACTOR as load
factor copying the elements of an array. |
UnorderedSet(K[] a,
CrossHash.IHasher hasher)
Creates a new hash set with
DEFAULT_LOAD_FACTOR as load
factor copying the elements of an array. |
UnorderedSet(K[] a,
float f)
Creates a new hash set copying the elements of an array.
|
UnorderedSet(K[] a,
float f,
CrossHash.IHasher hasher)
Creates a new hash set copying the elements of an array.
|
UnorderedSet(K[] a,
int offset,
int length)
Creates a new hash set with
DEFAULT_LOAD_FACTOR as load
factor and fills it with the elements of a given array. |
UnorderedSet(K[] a,
int offset,
int length,
CrossHash.IHasher hasher)
Creates a new hash set with
DEFAULT_LOAD_FACTOR as load
factor and fills it with the elements of a given array. |
UnorderedSet(K[] a,
int offset,
int length,
float f)
Creates a new hash set and fills it with the elements of a given array.
|
UnorderedSet(K[] a,
int offset,
int length,
float f,
CrossHash.IHasher hasher)
Creates a new hash set and fills it with the elements of a given array.
|
Modifier and Type | Method and Description |
---|---|
boolean |
add(K k) |
boolean |
addAll(java.util.Collection<? extends K> c) |
boolean |
addAll(K[] a) |
K |
addOrGet(K k)
Add a random element if not present, get the existing value if already
present.
|
static int |
arraySize(int expected,
float f)
Returns the least power of two smaller than or equal to 230 and larger than or equal to
Math.ceil( expected / f ) . |
void |
clear() |
java.lang.Object |
clone()
Returns a deep copy of this map.
|
boolean |
contains(java.lang.Object k) |
boolean |
containsAll(java.util.Collection<?> c)
Checks whether this collection contains all elements from the given
collection.
|
boolean |
equals(java.lang.Object o) |
K |
get(java.lang.Object k)
Returns the element of this set that is equal to the given key, or
null . |
long |
hash64() |
int |
hashCode()
Returns a hash code for this set.
|
boolean |
isEmpty() |
java.util.Iterator<K> |
iterator() |
static int |
maxFill(int n,
float f)
Returns the maximum number of entries that can be filled before rehashing.
|
static long |
maxFill(long n,
float f)
Returns the maximum number of entries that can be filled before rehashing.
|
protected int |
positionOf(java.lang.Object k) |
protected void |
rehash(int newN)
Rehashes the map.
|
boolean |
remove(java.lang.Object k) |
boolean |
removeAll(java.util.Collection<?> c)
Remove from this collection all elements in the given collection.
|
boolean |
retainAll(java.util.Collection<?> c)
Retains in this collection only elements from the given collection.
|
protected void |
shiftKeys(int pos)
Shifts left entries with the specified hash code, starting at the
specified position, and empties the resulting free entry.
|
int |
size() |
java.lang.Object[] |
toArray() |
<T> T[] |
toArray(T[] a) |
java.lang.String |
toString() |
boolean |
trim()
Rehashes the map, making the table as small as possible.
|
boolean |
trim(int n)
Rehashes this map if the table is too large.
|
protected K[] key
protected int mask
protected boolean containsNull
protected int n
protected int maxFill
f
.protected int size
public final float f
public static final int DEFAULT_INITIAL_SIZE
public static final float DEFAULT_LOAD_FACTOR
public static final float FAST_LOAD_FACTOR
public static final float VERY_FAST_LOAD_FACTOR
protected final CrossHash.IHasher hasher
public UnorderedSet(int expected, float f)
The actual table size will be the least power of two greater than expected
/f
.
expected
- the expected number of elements in the hash set.f
- the load factor.public UnorderedSet(int expected)
DEFAULT_LOAD_FACTOR
as load
factor.expected
- the expected number of elements in the hash set.public UnorderedSet()
DEFAULT_INITIAL_SIZE
elements and
DEFAULT_LOAD_FACTOR
as load factor.public UnorderedSet(java.util.Collection<? extends K> c, float f)
c
- a Collection
to be copied into the new hash set.f
- the load factor.public UnorderedSet(java.util.Collection<? extends K> c)
DEFAULT_LOAD_FACTOR
as load
factor copying a given collection.c
- a Collection
to be copied into the new hash set.public UnorderedSet(java.util.Iterator<? extends K> i, float f)
i
- a type-specific iterator whose elements will fill the set.f
- the load factor.public UnorderedSet(java.util.Iterator<? extends K> i)
DEFAULT_LOAD_FACTOR
as load
factor using elements provided by a type-specific iterator.i
- a type-specific iterator whose elements will fill the set.public UnorderedSet(K[] a, int offset, int length, float f)
a
- an array whose elements will be used to fill the set.offset
- the first element to use.length
- the number of elements to use.f
- the load factor.public UnorderedSet(K[] a, int offset, int length)
DEFAULT_LOAD_FACTOR
as load
factor and fills it with the elements of a given array.a
- an array whose elements will be used to fill the set.offset
- the first element to use.length
- the number of elements to use.public UnorderedSet(K[] a, float f)
a
- an array to be copied into the new hash set.f
- the load factor.public UnorderedSet(K[] a)
DEFAULT_LOAD_FACTOR
as load
factor copying the elements of an array.a
- an array to be copied into the new hash set.public UnorderedSet(int expected, float f, CrossHash.IHasher hasher)
The actual table size will be the least power of two greater than expected
/f
.
expected
- the expected number of elements in the hash set.f
- the load factor.hasher
- used to hash items; typically only needed when K is an array, where CrossHash has implementationspublic UnorderedSet(CrossHash.IHasher hasher)
DEFAULT_LOAD_FACTOR
as load
factor.hasher
- used to hash items; typically only needed when K is an array, where CrossHash has implementationspublic UnorderedSet(int expected, CrossHash.IHasher hasher)
DEFAULT_LOAD_FACTOR
as load
factor.hasher
- used to hash items; typically only needed when K is an array, where CrossHash has implementationspublic UnorderedSet(java.util.Collection<? extends K> c, float f, CrossHash.IHasher hasher)
c
- a Collection
to be copied into the new hash set.f
- the load factor.hasher
- used to hash items; typically only needed when K is an array, where CrossHash has implementationspublic UnorderedSet(java.util.Collection<? extends K> c, CrossHash.IHasher hasher)
DEFAULT_LOAD_FACTOR
as load
factor copying a given collection.c
- a Collection
to be copied into the new hash set.hasher
- used to hash items; typically only needed when K is an array, where CrossHash has implementationspublic UnorderedSet(K[] a, int offset, int length, float f, CrossHash.IHasher hasher)
a
- an array whose elements will be used to fill the set.offset
- the first element to use.length
- the number of elements to use.f
- the load factor.public UnorderedSet(K[] a, int offset, int length, CrossHash.IHasher hasher)
DEFAULT_LOAD_FACTOR
as load
factor and fills it with the elements of a given array.a
- an array whose elements will be used to fill the set.offset
- the first element to use.length
- the number of elements to use.public UnorderedSet(K[] a, float f, CrossHash.IHasher hasher)
a
- an array to be copied into the new hash set.f
- the load factor.public UnorderedSet(K[] a, CrossHash.IHasher hasher)
DEFAULT_LOAD_FACTOR
as load
factor copying the elements of an array.a
- an array to be copied into the new hash set.public boolean addAll(java.util.Collection<? extends K> c)
public boolean addAll(K[] a)
public boolean add(K k)
public K addOrGet(K k)
This is equivalent to (but faster than) doing a:
K exist = set.get(k); if (exist == null) { set.add(k); exist = k; }
protected final void shiftKeys(int pos)
pos
- a starting position.public boolean remove(java.lang.Object k)
public K get(java.lang.Object k)
null
.null
.public boolean contains(java.lang.Object k)
protected int positionOf(java.lang.Object k)
public void clear()
public int size()
public boolean containsAll(java.util.Collection<?> c)
public boolean retainAll(java.util.Collection<?> c)
public boolean removeAll(java.util.Collection<?> c)
public boolean isEmpty()
public java.util.Iterator<K> iterator()
public boolean trim()
This method rehashes the table to the smallest size satisfying the load factor. It can be used when the set will not be changed anymore, so to optimize access speed and size.
If the table size is already the minimum possible, this method does nothing.
trim(int)
public boolean trim(int n)
Let N be the smallest table size that can hold max(n,
entries, still satisfying the load factor. If the current table size is smaller than or equal to
N, this method does nothing. Otherwise, it rehashes this map in a table of size N.
size()
)
This method is useful when reusing maps. Clearing a map leaves the table size untouched. If you are reusing a map many times, you can call this method with a typical size to avoid keeping around a very large table just because of a few large transient maps.
n
- the threshold for the trimming.trim()
protected void rehash(int newN)
This method implements the basic rehashing strategy, and may be overriden by subclasses implementing different rehashing strategies (e.g., disk-based rehashing). However, you should not override this method unless you understand the internal workings of this class.
newN
- the new sizepublic java.lang.Object clone()
This method performs a deep copy of this hash map; the data stored in the map, however, is not cloned. Note that this makes a difference only for object keys.
clone
in class java.lang.Object
public int hashCode()
This method overrides the generic method provided by the superclass.
Since equals()
is not overriden, it is important that the
value returned by this method is the same value as the one returned by
the overriden method.
public long hash64()
public static int maxFill(int n, float f)
n
- the size of the backing array.f
- the load factor.public static long maxFill(long n, float f)
n
- the size of the backing array.f
- the load factor.public static int arraySize(int expected, float f)
Math.ceil( expected / f )
.expected
- the expected number of elements in a hash table.f
- the load factor.java.lang.IllegalArgumentException
- if the necessary size is larger than 230.public java.lang.Object[] toArray()
public <T> T[] toArray(T[] a)
public java.lang.String toString()
toString
in class java.lang.Object
Copyright © Eben Howard 2012–2022. All rights reserved.