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.