# Class HashOperations

java.lang.Object
org.apache.datasketches.thetacommon.HashOperations

public final class HashOperations extends Object
Helper class for the common hash table methods.

Author:
  Lee Rhodes, Kevin Lang

## Field Summary

Fields
Modifier and Type
Field
Description
`static final int`
`STRIDE_MASK`
The stride mask for the Open Address, Double Hashing (OADH) hash table algorithm.

## Method Summary

Modifier and Type
Method
Description
`static void`
`checkHashCorruption(long hash)`
Checks that the given hash value is not negative.
`static void`
`checkThetaCorruption(long thetaLong)`
Checks that the given theta is not negative nor zero.
`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`
`hashInsertOnlyMemorySegment(MemorySegment wseg, int lgArrLongs, long hash, int segOffsetBytes)`
This is a classical Knuth-style Open Addressing, Double Hash (OADH) insert scheme for MemorySegment.
`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`
`hashSearchMemorySegment(MemorySegment seg, int lgArrLongs, long hash, int segOffsetBytes)`
This is a classical Knuth-style Open Addressing, Double Hash (OADH) search scheme for MemorySegment.
`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`
`hashSearchOrInsertMemorySegment(MemorySegment wseg, int lgArrLongs, long hash, int segOffsetBytes)`
This is a classical Knuth-style Open Addressing, Double Hash insert scheme, but inserts values directly into a writable MemorySegment.
`static int`
`minLgHashTableSize(int count, double rebuild_threshold)`
Returns the smallest log hash table size given the count of items and the rebuild threshold.

### Methods inherited from class Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

## Field Details

### STRIDE_MASK

public static final int STRIDE_MASK
The stride mask for the Open Address, Double Hashing (OADH) hash table algorithm.

See Also:
  - Constant Field Values

## Method Details

### hashSearch

public 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. Returns the index if found, -1 if not found.

Parameters:
  `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.
Returns:
  Current probe index if found, -1 if not found.

### hashInsertOnly

public 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. This method assumes that the input hash is not a duplicate. Useful for rebuilding tables to avoid unnecessary comparisons. Returns the index of insertion, which is always positive or zero. Throws an exception if the table has no empty slot.

Parameters:
  `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.
Returns:
  index of insertion. Always positive or zero.

### hashSearchOrInsert

public 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. Returns index ≥ 0 if found (duplicate); < 0 if inserted, inserted at -(index + 1). Throws an exception if the value is not found and table has no empty slot.

Parameters:
  `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.
Returns:
  index ≥ 0 if found (duplicate); < 0 if inserted, inserted at -(index + 1).

### hashArrayInsert

public 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. The hash values must not be negative, zero values and values ≥ thetaLong are ignored. The given hash table may have values, but they must have been inserted by this method or one of the other OADH insert methods in this class. This method performs additional checks against potentially invalid hash values or theta values. Returns the count of values actually inserted.

Parameters:
  `srcArr` - the source hash array to be potentially inserted
  `hashTable` - 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 Long
Returns:
  the count of values actually inserted

### hashSearchMemorySegment

public static int hashSearchMemorySegment(MemorySegment seg, int lgArrLongs, long hash, int segOffsetBytes)
This is a classical Knuth-style Open Addressing, Double Hash (OADH) search scheme for MemorySegment. Returns the index if found, -1 if not found. The input MemorySegment may be read only.

Parameters:
  `seg` - The MemorySegment 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.
  `segOffsetBytes` - offset in the MemorySegment where the hashTable starts
Returns:
  Current probe index if found, -1 if not found.

### hashInsertOnlyMemorySegment

public static int hashInsertOnlyMemorySegment(MemorySegment wseg, int lgArrLongs, long hash, int segOffsetBytes)
This is a classical Knuth-style Open Addressing, Double Hash (OADH) insert scheme for MemorySegment. This method assumes that the input hash is not a duplicate. Useful for rebuilding tables to avoid unnecessary comparisons. Returns the index of insertion, which is always positive or zero. Throws an exception if table has no empty slot.

Parameters:
  `wseg` - The writable MemorySegment 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.
  `segOffsetBytes` - offset in the writable MemorySegment where the hashTable starts
Returns:
  index of insertion. Always positive or zero.

### hashSearchOrInsertMemorySegment

public static int hashSearchOrInsertMemorySegment(MemorySegment wseg, int lgArrLongs, long hash, int segOffsetBytes)
This is a classical Knuth-style Open Addressing, Double Hash insert scheme, but inserts values directly into a writable MemorySegment. Returns index ≥ 0 if found (duplicate); < 0 if inserted, inserted at -(index + 1). Throws an exception if the value is not found and table has no empty slot.

Parameters:
  `wseg` - The writable MemorySegment 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.
  `segOffsetBytes` - offset in the writable MemorySegment where the hash array starts
Returns:
  index ≥ 0 if found (duplicate); < 0 if inserted, inserted at -(index + 1).

### checkThetaCorruption

public static void checkThetaCorruption(long thetaLong)
Checks that the given theta is not negative nor zero.

Parameters:
  `thetaLong` - must be greater than zero otherwise throws an exception. See Theta Long

### checkHashCorruption

public static void checkHashCorruption(long hash)
Checks that the given hash value is not negative.

Parameters:
  `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.

### continueCondition

public 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.

Parameters:
  `thetaLong` - must be greater than the hash value See Theta Long
  `hash` - must be less than thetaLong and not less than or equal to zero.
Returns:
  true (continue) if hash is greater than or equal to thetaLong, or if hash == 0, or if hash == Long.MAX_VALUE.

### convertToHashTable

public static long[] convertToHashTable(long[] hashArr, int count, long thetaLong, double rebuildThreshold)
Converts the given array to a hash table.

Parameters:
  `hashArr` - The given array of hashes. Gaps are OK.
  `count` - The number of valid hashes in the array
  `thetaLong` - Any hashes equal to or greater than thetaLong will be ignored
  `rebuildThreshold` - The fill fraction for the hash table forcing a rebuild or resize.
Returns:
  a HashTable

### minLgHashTableSize

public static int minLgHashTableSize(int count, double rebuild_threshold)
Returns the smallest log hash table size given the count of items and the rebuild threshold.

Parameters:
  `count` - the given count of items
  `rebuild_threshold` - the rebuild threshold as a fraction between zero and one.
Returns:
  the smallest log hash table size

### countPart

public static int countPart(long[] srcArr, int lgArrLongs, long thetaLong)
Counts the cardinality of the first Log2 values of the given source array.

Parameters:
  `srcArr` - the given source array
  `lgArrLongs` - See lgArrLongs
  `thetaLong` - See Theta Long
Returns:
  the cardinality

### count

public static int count(long[] srcArr, long thetaLong)
Counts the cardinality of the given source array.

Parameters:
  `srcArr` - the given source array
  `thetaLong` - See Theta Long
Returns:
  the cardinality