it.unimi.dsi.fastutil
Interface Hash
- All Known Implementing Classes:
- BooleanOpenHashSet, Byte2BooleanLinkedOpenHashMap, Byte2BooleanOpenHashMap, Byte2ByteLinkedOpenHashMap, Byte2ByteOpenHashMap, Byte2CharLinkedOpenHashMap, Byte2CharOpenHashMap, Byte2DoubleLinkedOpenHashMap, Byte2DoubleOpenHashMap, Byte2FloatLinkedOpenHashMap, Byte2FloatOpenHashMap, Byte2IntLinkedOpenHashMap, Byte2IntOpenHashMap, Byte2LongLinkedOpenHashMap, Byte2LongOpenHashMap, Byte2ObjectLinkedOpenHashMap, Byte2ObjectOpenHashMap, Byte2ReferenceLinkedOpenHashMap, Byte2ReferenceOpenHashMap, Byte2ShortLinkedOpenHashMap, Byte2ShortOpenHashMap, ByteLinkedOpenHashSet, ByteOpenHashSet, Char2BooleanLinkedOpenHashMap, Char2BooleanOpenHashMap, Char2ByteLinkedOpenHashMap, Char2ByteOpenHashMap, Char2CharLinkedOpenHashMap, Char2CharOpenHashMap, Char2DoubleLinkedOpenHashMap, Char2DoubleOpenHashMap, Char2FloatLinkedOpenHashMap, Char2FloatOpenHashMap, Char2IntLinkedOpenHashMap, Char2IntOpenHashMap, Char2LongLinkedOpenHashMap, Char2LongOpenHashMap, Char2ObjectLinkedOpenHashMap, Char2ObjectOpenHashMap, Char2ReferenceLinkedOpenHashMap, Char2ReferenceOpenHashMap, Char2ShortLinkedOpenHashMap, Char2ShortOpenHashMap, CharLinkedOpenHashSet, CharOpenHashSet, Double2BooleanLinkedOpenHashMap, Double2BooleanOpenHashMap, Double2ByteLinkedOpenHashMap, Double2ByteOpenHashMap, Double2CharLinkedOpenHashMap, Double2CharOpenHashMap, Double2DoubleLinkedOpenHashMap, Double2DoubleOpenHashMap, Double2FloatLinkedOpenHashMap, Double2FloatOpenHashMap, Double2IntLinkedOpenHashMap, Double2IntOpenHashMap, Double2LongLinkedOpenHashMap, Double2LongOpenHashMap, Double2ObjectLinkedOpenHashMap, Double2ObjectOpenHashMap, Double2ReferenceLinkedOpenHashMap, Double2ReferenceOpenHashMap, Double2ShortLinkedOpenHashMap, Double2ShortOpenHashMap, DoubleLinkedOpenHashSet, DoubleOpenHashSet, Float2BooleanLinkedOpenHashMap, Float2BooleanOpenHashMap, Float2ByteLinkedOpenHashMap, Float2ByteOpenHashMap, Float2CharLinkedOpenHashMap, Float2CharOpenHashMap, Float2DoubleLinkedOpenHashMap, Float2DoubleOpenHashMap, Float2FloatLinkedOpenHashMap, Float2FloatOpenHashMap, Float2IntLinkedOpenHashMap, Float2IntOpenHashMap, Float2LongLinkedOpenHashMap, Float2LongOpenHashMap, Float2ObjectLinkedOpenHashMap, Float2ObjectOpenHashMap, Float2ReferenceLinkedOpenHashMap, Float2ReferenceOpenHashMap, Float2ShortLinkedOpenHashMap, Float2ShortOpenHashMap, FloatLinkedOpenHashSet, FloatOpenHashSet, Int2BooleanLinkedOpenHashMap, Int2BooleanOpenHashMap, Int2ByteLinkedOpenHashMap, Int2ByteOpenHashMap, Int2CharLinkedOpenHashMap, Int2CharOpenHashMap, Int2DoubleLinkedOpenHashMap, Int2DoubleOpenHashMap, Int2FloatLinkedOpenHashMap, Int2FloatOpenHashMap, Int2IntLinkedOpenHashMap, Int2IntOpenHashMap, Int2LongLinkedOpenHashMap, Int2LongOpenHashMap, Int2ObjectLinkedOpenHashMap, Int2ObjectOpenHashMap, Int2ReferenceLinkedOpenHashMap, Int2ReferenceOpenHashMap, Int2ShortLinkedOpenHashMap, Int2ShortOpenHashMap, IntLinkedOpenHashSet, IntOpenHashSet, Long2BooleanLinkedOpenHashMap, Long2BooleanOpenHashMap, Long2ByteLinkedOpenHashMap, Long2ByteOpenHashMap, Long2CharLinkedOpenHashMap, Long2CharOpenHashMap, Long2DoubleLinkedOpenHashMap, Long2DoubleOpenHashMap, Long2FloatLinkedOpenHashMap, Long2FloatOpenHashMap, Long2IntLinkedOpenHashMap, Long2IntOpenHashMap, Long2LongLinkedOpenHashMap, Long2LongOpenHashMap, Long2ObjectLinkedOpenHashMap, Long2ObjectOpenHashMap, Long2ReferenceLinkedOpenHashMap, Long2ReferenceOpenHashMap, Long2ShortLinkedOpenHashMap, Long2ShortOpenHashMap, LongLinkedOpenHashSet, LongOpenHashSet, Object2BooleanLinkedOpenHashMap, Object2BooleanOpenHashMap, Object2ByteLinkedOpenHashMap, Object2ByteOpenHashMap, Object2CharLinkedOpenHashMap, Object2CharOpenHashMap, Object2DoubleLinkedOpenHashMap, Object2DoubleOpenHashMap, Object2FloatLinkedOpenHashMap, Object2FloatOpenHashMap, Object2IntLinkedOpenHashMap, Object2IntOpenHashMap, Object2LongLinkedOpenHashMap, Object2LongOpenHashMap, Object2ObjectLinkedOpenHashMap, Object2ObjectOpenHashMap, Object2ReferenceLinkedOpenHashMap, Object2ReferenceOpenHashMap, Object2ShortLinkedOpenHashMap, Object2ShortOpenHashMap, ObjectLinkedOpenHashSet, ObjectOpenHashSet, Reference2BooleanLinkedOpenHashMap, Reference2BooleanOpenHashMap, Reference2ByteLinkedOpenHashMap, Reference2ByteOpenHashMap, Reference2CharLinkedOpenHashMap, Reference2CharOpenHashMap, Reference2DoubleLinkedOpenHashMap, Reference2DoubleOpenHashMap, Reference2FloatLinkedOpenHashMap, Reference2FloatOpenHashMap, Reference2IntLinkedOpenHashMap, Reference2IntOpenHashMap, Reference2LongLinkedOpenHashMap, Reference2LongOpenHashMap, Reference2ObjectLinkedOpenHashMap, Reference2ObjectOpenHashMap, Reference2ReferenceLinkedOpenHashMap, Reference2ReferenceOpenHashMap, Reference2ShortLinkedOpenHashMap, Reference2ShortOpenHashMap, ReferenceLinkedOpenHashSet, ReferenceOpenHashSet, Short2BooleanLinkedOpenHashMap, Short2BooleanOpenHashMap, Short2ByteLinkedOpenHashMap, Short2ByteOpenHashMap, Short2CharLinkedOpenHashMap, Short2CharOpenHashMap, Short2DoubleLinkedOpenHashMap, Short2DoubleOpenHashMap, Short2FloatLinkedOpenHashMap, Short2FloatOpenHashMap, Short2IntLinkedOpenHashMap, Short2IntOpenHashMap, Short2LongLinkedOpenHashMap, Short2LongOpenHashMap, Short2ObjectLinkedOpenHashMap, Short2ObjectOpenHashMap, Short2ReferenceLinkedOpenHashMap, Short2ReferenceOpenHashMap, Short2ShortLinkedOpenHashMap, Short2ShortOpenHashMap, ShortLinkedOpenHashSet, ShortOpenHashSet
- public interface Hash
Basic data for all hash-based classes.
The classes in fastutil
are built around open-addressing hashing
implemented via double hashing. Following Knuth's suggestions in the third volume of The Art of Computer
Programming, we use for the table size a prime p such that
p-2 is also prime. In this way hashing is implemented with modulo p,
and secondary hashing with modulo p-2.
Entries in a table can be in three states: FREE
, OCCUPIED
or REMOVED
.
The naive handling of removed entries requires that you search for a free entry as if they were occupied. However,
fastutil
implements two useful optimizations, based on the following invariant:
Let i0, i1, &hellip, ip-1 be
the permutation of the table indices induced by the key k, that is, i0 is the hash
of k and the following indices are obtained by adding (modulo p) the secondary hash plus one.
If there is a OCCUPIED
entry with key k, its index in the sequence above comes before
the indices of any REMOVED
entries with key k.
When we search for the key k we scan the entries in the
sequence i0, i1, &hellip,
ip-1 and stop when k is found,
when we finished the sequence or when we find a FREE
entry. Note
that the correctness of this procedure it is not completely trivial. Indeed,
when we stop at a REMOVED
entry with key k we must rely
on the invariant to be sure that no OCCUPIED
entry with the same
key can appear later. If we insert and remove frequently the same entries,
this optimization can be very effective (note, however, that when using
objects as keys or values deleted entries are set to a special fixed value to
optimize garbage collection).
Moreover, during the probe we keep the index of the first REMOVED
entry we meet.
If we actually have to insert a new element, we use that
entry if we can, thus avoiding to pollute another FREE
entry. Since this position comes
a fortiori before any REMOVED
entries with the same key, we are also keeping the invariant true.
Field Summary |
static int |
DEFAULT_GROWTH_FACTOR
The default growth factor of a hash table. |
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. |
static byte |
FREE
The state of a free hash table entry. |
static byte |
OCCUPIED
The state of a occupied hash table entry. |
static int[] |
PRIMES
A list of primes to be used as table sizes. |
static byte |
REMOVED
The state of a hash table entry freed by a deletion. |
DEFAULT_INITIAL_SIZE
public static final int DEFAULT_INITIAL_SIZE
- The initial default size of a hash table.
- See Also:
- Constant Field Values
DEFAULT_LOAD_FACTOR
public static final float DEFAULT_LOAD_FACTOR
- The default load factor of a hash table.
- See Also:
- Constant Field Values
DEFAULT_GROWTH_FACTOR
public static final int DEFAULT_GROWTH_FACTOR
- The default growth factor of a hash table.
- See Also:
- Constant Field Values
FREE
public static final byte FREE
- The state of a free hash table entry.
- See Also:
- Constant Field Values
OCCUPIED
public static final byte OCCUPIED
- The state of a occupied hash table entry.
- See Also:
- Constant Field Values
REMOVED
public static final byte REMOVED
- The state of a hash table entry freed by a deletion.
- See Also:
- Constant Field Values
PRIMES
public static final int[] PRIMES
- A list of primes to be used as table sizes. The i-th element is
the largest prime p smaller than 2(i+28)/16
and such that p-2 is also prime (or 1, for the first few entries).