Class KeyIdHasher
java.lang.Object
io.deephaven.engine.table.impl.join.KeyIdHasher
- Direct Known Subclasses:
IncrementalKeyIdHasherTypedBase,KeyIdHasherTypedBase
An open-addressed hash table that gives each distinct key a dense integer id.
Ids start at zero and stay with their key; moving entries during a rehash does not change them. Callers therefore keep per-key state in their own arrays indexed by id, and never need to update it when the table grows.
KeyIdHasherTypedBase only adds keys. IncrementalKeyIdHasherTypedBase also removes them, reusing their
ids, and grows incrementally.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic interfaceReceives the ids for one chunk of rows. -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected static final intprotected ImmutableIntArraySourceprotected final WritableColumnSource[]protected final doubleprotected intstatic final intThe idprobe(io.deephaven.engine.rowset.RowSequence, io.deephaven.engine.table.ColumnSource<?>[], boolean, io.deephaven.engine.table.impl.join.KeyIdHasher.IdChunkConsumer)reports for a key that is not in the table, and the state of a slot that holds no key.protected longHow many slots of the main table are occupied?protected int -
Constructor Summary
ConstructorsModifierConstructorDescriptionprotectedKeyIdHasher(ColumnSource<?>[] tableKeySources, int tableSize, double maximumLoadFactor) -
Method Summary
Modifier and TypeMethodDescriptionprotected abstract intallocateId(int slot) Hand out an id for a key inserted intoslot.voidbuild(@NotNull RowSequence rows, @NotNull ColumnSource<?>[] sources, @NotNull KeyIdHasher.IdChunkConsumer consumer) Find the id of each row's key, adding the keys that are not yet in the table.protected abstract voidbuild(RowSequence rowSequence, Chunk[] sourceKeyChunks, WritableIntChunk<Values> ids) protected inthashToTableLocation(int hash) intprotected voidonChunkBuilt(long entriesAdded) Called after each chunk is built, with the number of main table slots that it newly occupied.protected abstract voidprepareForChunk(int nextChunkSize) Make room to insert up tonextChunkSizekeys.voidprobe(@NotNull RowSequence rows, @NotNull ColumnSource<?>[] sources, boolean usePrev, @NotNull KeyIdHasher.IdChunkConsumer consumer) Find the id of each row's key, reportingNULL_IDfor a key that is not in the table.protected abstract voidprobe(RowSequence rowSequence, Chunk[] sourceKeyChunks, WritableIntChunk<Values> ids) protected abstract voidrehashInternalFull(int oldSize) abstract longsize()protected void
-
Field Details
-
NULL_ID
public static final int NULL_IDThe idprobe(io.deephaven.engine.rowset.RowSequence, io.deephaven.engine.table.ColumnSource<?>[], boolean, io.deephaven.engine.table.impl.join.KeyIdHasher.IdChunkConsumer)reports for a key that is not in the table, and the state of a slot that holds no key.- See Also:
-
EMPTY_ID
protected static final int EMPTY_ID- See Also:
-
tableSize
protected int tableSize -
numEntries
protected long numEntriesHow many slots of the main table are occupied? -
maximumLoadFactor
protected final double maximumLoadFactor -
mainKeySources
-
mainId
-
nextId
protected int nextId
-
-
Constructor Details
-
KeyIdHasher
-
-
Method Details
-
build
public void build(@NotNull @NotNull RowSequence rows, @NotNull @NotNull ColumnSource<?>[] sources, @NotNull @NotNull KeyIdHasher.IdChunkConsumer consumer) Find the id of each row's key, adding the keys that are not yet in the table.- Parameters:
rows- the rows to buildsources- the key sourcesconsumer- receives the ids, one chunk of rows at a time
-
probe
public void probe(@NotNull @NotNull RowSequence rows, @NotNull @NotNull ColumnSource<?>[] sources, boolean usePrev, @NotNull @NotNull KeyIdHasher.IdChunkConsumer consumer) Find the id of each row's key, reportingNULL_IDfor a key that is not in the table.- Parameters:
rows- the rows to probesources- the key sourcesusePrev- whether to read the previous values ofsourcesconsumer- receives the ids, one chunk of rows at a time
-
idCapacity
public int idCapacity()- Returns:
- one more than the largest id handed out; every id is in
[0, idCapacity())
-
size
public abstract long size()- Returns:
- the number of keys in the table
-
startBuild
protected void startBuild() -
prepareForChunk
protected abstract void prepareForChunk(int nextChunkSize) Make room to insert up tonextChunkSizekeys. -
onChunkBuilt
protected void onChunkBuilt(long entriesAdded) Called after each chunk is built, with the number of main table slots that it newly occupied. -
allocateId
protected abstract int allocateId(int slot) Hand out an id for a key inserted intoslot. -
hashToTableLocation
protected int hashToTableLocation(int hash) -
build
protected abstract void build(RowSequence rowSequence, Chunk[] sourceKeyChunks, WritableIntChunk<Values> ids) -
probe
protected abstract void probe(RowSequence rowSequence, Chunk[] sourceKeyChunks, WritableIntChunk<Values> ids) -
rehashInternalFull
protected abstract void rehashInternalFull(int oldSize)
-