public final class HashOperations extends Object
Modifier and Type | Field and Description |
---|---|
static int |
STRIDE_MASK
The stride mask for the Open Address, Double Hashing (OADH) hash table algorithm.
|
Modifier and Type | Method and Description |
---|---|
static void |
checkHashCorruption(long hash) |
static void |
checkThetaCorruption(long thetaLong) |
static boolean |
continueCondition(long thetaLong,
long hash)
Return true (continue) if hash is greater than or equal to thetaLong, or if hash == 0,
or if hash == Long.MAX_VALUE.
|
static long[] |
convertToHashTable(long[] hashArr,
int count,
long thetaLong,
double rebuildThreshold)
Converts the given array to a hash table.
|
static int |
count(long[] srcArr,
long thetaLong)
Counts the cardinality of the given source array.
|
static int |
countPart(long[] srcArr,
int lgArrLongs,
long thetaLong)
Counts the cardinality of the first Log2 values of the given source array.
|
static int |
hashArrayInsert(long[] srcArr,
long[] hashTable,
int lgArrLongs,
long thetaLong)
Inserts the given long array into the given OADH hashTable of the target size,
ignores duplicates and counts the values inserted.
|
static int |
hashInsertOnly(long[] hashTable,
int lgArrLongs,
long hash)
This is a classical Knuth-style Open Addressing, Double Hash (OADH) insert scheme for on-heap.
|
static int |
hashInsertOnlyMemory(org.apache.datasketches.memory.WritableMemory wmem,
int lgArrLongs,
long hash,
int memOffsetBytes)
This is a classical Knuth-style Open Addressing, Double Hash (OADH) insert scheme for Memory.
|
static int |
hashSearch(long[] hashTable,
int lgArrLongs,
long hash)
This is a classical Knuth-style Open Addressing, Double Hash (OADH) search scheme for on-heap.
|
static int |
hashSearchMemory(org.apache.datasketches.memory.Memory mem,
int lgArrLongs,
long hash,
int memOffsetBytes)
This is a classical Knuth-style Open Addressing, Double Hash (OADH) search scheme for Memory.
|
static int |
hashSearchOrInsert(long[] hashTable,
int lgArrLongs,
long hash)
This is a classical Knuth-style Open Addressing, Double Hash (OADH) insert scheme for on-heap.
|
static int |
hashSearchOrInsertMemory(org.apache.datasketches.memory.WritableMemory wmem,
int lgArrLongs,
long hash,
int memOffsetBytes)
This is a classical Knuth-style Open Addressing, Double Hash insert scheme, but inserts
values directly into a Memory.
|
static int |
minLgHashTableSize(int count,
double rebuild_threshold)
Returns the smallest log hash table size given the count of items and the rebuild threshold.
|
public static final int STRIDE_MASK
public static int hashSearch(long[] hashTable, int lgArrLongs, long hash)
hashTable
- The hash table to search. Its size must be a power of 2.lgArrLongs
- The log_base2(hashTable.length).
See lgArrLongs.hash
- The hash value to search for. It must not be zero.public static int hashInsertOnly(long[] hashTable, int lgArrLongs, long hash)
hashTable
- the hash table to insert into. Its size must be a power of 2.lgArrLongs
- The log_base2(hashTable.length).
See lgArrLongs.hash
- The hash value to be potentially inserted into an empty slot. It must not be zero.public static int hashSearchOrInsert(long[] hashTable, int lgArrLongs, long hash)
hashTable
- The hash table to insert into. Its size must be a power of 2.lgArrLongs
- The log_base2(hashTable.length).
See lgArrLongs.hash
- The hash value to be potentially inserted into an empty slot only if it is not
a duplicate of any other hash value in the table. It must not be zero.public static int hashArrayInsert(long[] srcArr, long[] hashTable, int lgArrLongs, long thetaLong)
srcArr
- the source hash array to be potentially insertedhashTable
- The hash table to insert into. Its size must be a power of 2.lgArrLongs
- The log_base2(hashTable.length).
See lgArrLongs.thetaLong
- The theta value that all input hash values are compared against.
It must greater than zero.
See Theta Longpublic static int hashSearchMemory(org.apache.datasketches.memory.Memory mem, int lgArrLongs, long hash, int memOffsetBytes)
mem
- The Memory containing the hash table to search.
The hash table portion must be a power of 2 in size.lgArrLongs
- The log_base2(hashTable.length).
See lgArrLongs.hash
- The hash value to search for. Must not be zero.memOffsetBytes
- offset in the memory where the hashTable startspublic static int hashInsertOnlyMemory(org.apache.datasketches.memory.WritableMemory wmem, int lgArrLongs, long hash, int memOffsetBytes)
wmem
- The WritableMemory that contains the hashTable to insert into.
The size of the hashTable portion must be a power of 2.lgArrLongs
- The log_base2(hashTable.length.
See lgArrLongs.hash
- value that must not be zero and will be inserted into the array into an empty slot.memOffsetBytes
- offset in the WritableMemory where the hashTable startspublic static int hashSearchOrInsertMemory(org.apache.datasketches.memory.WritableMemory wmem, int lgArrLongs, long hash, int memOffsetBytes)
wmem
- The WritableMemory that contains the hashTable to insert into.lgArrLongs
- The log_base2(hashTable.length).
See lgArrLongs.hash
- The hash value to be potentially inserted into an empty slot only if it is not
a duplicate of any other hash value in the table. It must not be zero.memOffsetBytes
- offset in the WritableMemory where the hash array startspublic static void checkThetaCorruption(long thetaLong)
thetaLong
- must be greater than zero otherwise throws an exception.
See Theta Longpublic static void checkHashCorruption(long hash)
hash
- must be greater than -1 otherwise throws an exception.
Note a hash of zero is normally ignored, but a negative hash is never allowed.public static boolean continueCondition(long thetaLong, long hash)
thetaLong
- must be greater than the hash value
See Theta Longhash
- must be less than thetaLong and not less than or equal to zero.public static long[] convertToHashTable(long[] hashArr, int count, long thetaLong, double rebuildThreshold)
hashArr
- The given array of hashes. Gaps are OK.count
- The number of valid hashes in the arraythetaLong
- Any hashes equal to or greater than thetaLong will be ignoredrebuildThreshold
- The fill fraction for the hash table forcing a rebuild or resize.public static int minLgHashTableSize(int count, double rebuild_threshold)
count
- the given count of itemsrebuild_threshold
- the rebuild threshold as a fraction between zero and one.public static int countPart(long[] srcArr, int lgArrLongs, long thetaLong)
srcArr
- the given source arraylgArrLongs
- See lgArrLongsthetaLong
- See Theta Longpublic static int count(long[] srcArr, long thetaLong)
srcArr
- the given source arraythetaLong
- See Theta LongCopyright © 2015–2024 The Apache Software Foundation. All rights reserved.