com.koloboke.collect.hash

Class HashConfig

Object

com.koloboke.collect.hash.HashConfig

public abstract class HashConfig
extends Object

A config object that holds configurations of hash container's loads and dynamic behaviour.

Instead of a single load factor, available for configuration in most other hash collections APIs, HashConfig allows to configure three loads:

• Target load denotes the desirable hash table load. On hash container construction capacity is chosen in order to table's load to be as close to the target load, as possible.
• Min load denotes the minimum load a hash table will try to never be sparser than.
• Max load denotes the maximum load a hash table will try to never be denser than.

There is an obvious invariant over the loads:

0 <= min load <= target load <= max load <= 1

But the target load shouldn't touch the bounds:

0 < target load < 1

The loads are bounded within the [0, 1] range, since all hashes in the library use open addressing method of collision resolution.

Also HashConfig allows to configure the growth factor. When elements are inserted into the hash container and it grows, when the hash container load reaches the max load, hash table's capacity is multiplied by the growth factor, immediately after that the current load is supposed to be at or a bit higher than the min load. That is why HashConfig keeps one more invariant:

1.0 < growth factor <= max load / min load

The schema explained above allows much more precise control over memory footprint -- performance tradeoff of hash containers, than a single load factor configuration.

Hash config is immutable, all "setters" return a new independent config object with the corresponding field changed.

See Also:

HashContainer, HashContainerFactory.withHashConfig(HashConfig)

Method Summary

Methods

Modifier and Type	Method and Description
static HashConfig	fromLoads(double minLoad, double targetLoad, double maxLoad) Returns a new hash config with the given loads and the growth factor set to maxLoad / minLoad.
static HashConfig	getDefault() Returns a hash config with 0.(3) min load, 0.5 target load, 0.(6) max load, 2.0 growth factor and null shrink condition.
abstract double	getGrowthFactor() Returns the growth factor of this hash config.
abstract double	getMaxLoad() Returns the max load of this hash config.
abstract double	getMinLoad() Returns the min load of this hash config.
abstract Predicate<HashContainer>	getShrinkCondition() Returns the shrink condition of this hash config.
abstract double	getTargetLoad() Returns the target load of this hash config.
HashConfig	withGrowthFactor(double growthFactor) Returns a copy of this hash config with the growth factor set to the given value.
HashConfig	withMaxLoad(double maxLoad) Returns a copy of this hash config with the max load set to the given value.
HashConfig	withMinLoad(double minLoad) Returns a copy of this hash config with the min load set to the given value.
HashConfig	withShrinkCondition(Predicate<HashContainer> condition) Returns a copy of this hash config with the shrink condition set to the given predicate.
HashConfig	withTargetLoad(double targetLoad) Returns a copy of this hash config with the target load set to the given value.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

getDefault

@Nonnull
public static HashConfig getDefault()

Returns a hash config with 0.(3) min load, 0.5 target load, 0.(6) max load, 2.0 growth factor and null shrink condition.

Returns:

the default hash config

fromLoads

@Nonnull
public static HashConfig fromLoads(double minLoad,
                           double targetLoad,
                           double maxLoad)

Returns a new hash config with the given loads and the growth factor set to maxLoad / minLoad.

The shrink condition in the returned hash config is left default, i. e. null.

Parameters:

minLoad - the min load, should be in the [0.0, targetLoad] range

targetLoad - the target load, should be in the [minLoad, maxLoad] range

maxLoad - the max load, should be in the [targetLoad, 1.0] range

Returns:

a hash config with the given loads and the growth factor of maxLoad / minLoad

Throws:

IllegalArgumentException - if the given loads violate the hash config invariants

getMinLoad

public abstract double getMinLoad()

Returns the min load of this hash config. It denotes the minimum load a hash table will try to never be sparser than.

The default is 0.(3) (one-third).

Returns:

the minimum load, a value in the [0.0, target load] range

See Also:

withMinLoad(double)

withMinLoad

public final HashConfig withMinLoad(double minLoad)

Returns a copy of this hash config with the min load set to the given value.

Min load allows to limit memory usage of hash containers.

Updatable and mutable linear hash tables can't have min load greater than 0.5.

Parameters:

minLoad - the new min load, a value in the [0.0, target load] range

Returns:

a copy of this hash config with the min load set to the given value

Throws:

IllegalArgumentException - if the resulting hash config violates the invariants

See Also:

getMinLoad()

getTargetLoad

public abstract double getTargetLoad()

Returns the target load of this hash config. It denotes the desirable hash table load. On hash container construction capacity is chosen in order to table's load to be as close to the target load, as possible.

HashContainer.shrink() rehashes a table to the target load.

Returns:

the target load, a value in the [min load, max load] range

See Also:

withTargetLoad(double)

withTargetLoad

public final HashConfig withTargetLoad(double targetLoad)

Returns a copy of this hash config with the target load set to the given value.

Target load allows to control basic memory usage -- performance tradeoff for hash tables.

Parameters:

targetLoad - the new target load, a value in the [min load, max load] range

Returns:

a copy of this hash config with the target load set to the given value

Throws:

IllegalArgumentException - if the resulting hash config violates the invariants

See Also:

getTargetLoad()

getMaxLoad

public abstract double getMaxLoad()

Returns the max load of this hash config. It denotes the maximum load a hash table will try to never be denser than.

Returns:

the maximum load, a value in the [target load, 1.0] range

See Also:

withMaxLoad(double)

withMaxLoad

public final HashConfig withMaxLoad(double maxLoad)

Returns a copy of this hash config with the max load set to the given value.

Max load allows to limit the minimum performance of hash tables, because too dense hash tables operate slowly.

Parameters:

maxLoad - the new max load, a value in the [target load, 1.0] range

Returns:

a copy of this hash config with the max load set to the given value

Throws:

IllegalArgumentException - if the resulting hash config violates the invariants

See Also:

getMaxLoad()

getGrowthFactor

public abstract double getGrowthFactor()

Returns the growth factor of this hash config. It denotes how much a hash container's capacity is increased on periodical rehashes on adding (putting) new elements (entries).

Returns:

the growth factor, a value in the [1.0, max load / min load] range

See Also:

withGrowthFactor(double)

withGrowthFactor

public final HashConfig withGrowthFactor(double growthFactor)

Returns a copy of this hash config with the growth factor set to the given value.

Growth factor allows to control memory usage -- performance tradeoff for steadily growing hash tables.

Linear hash tables can't have any growth factor other than 2.0.

Parameters:

growthFactor - the new growth factor, a value in the [1.0, max load / min load] range

Returns:

a copy of this hash config with the growth factor set to the given value

Throws:

IllegalArgumentException - if the resulting hash config violates the invariants

See Also:

getGrowthFactor()

getShrinkCondition

@Nullable
public abstract Predicate<HashContainer> getShrinkCondition()

Returns the shrink condition of this hash config.

Immediately after hash set or map construction from non-distinct sources (e. g. arrays) it's load could be significantly less than the target factor due to expansion. The shrink condition is a predicate which is used to shrink too sparse hash containers automatically.

null condition is considered as constant false predicate: never shrink. It is a default value.

Particularly useful for immutable containers construction, because they couldn't be shrunk manually after being returned from the factory method.

Returns:

the shrink condition of this hash config

See Also:

withShrinkCondition(com.koloboke.function.Predicate), HashContainer.shrink()

withShrinkCondition

public final HashConfig withShrinkCondition(@Nullable
                             Predicate<HashContainer> condition)

Returns a copy of this hash config with the shrink condition set to the given predicate.

An example of sensible shrink condition:

 
 conf.withShrinkCondition(new Predicate<HashContainer>() {
     @Override
     public boolean test(HashContainer h) {
         return h.currentLoad() + 0.1 < h.hashConfig().getTargetLoad();
     }
 });
 
 

Parameters:

condition - the new shrink condition

Returns:

a copy of this hash config with the shrink condition set to the given predicate

See Also:

getShrinkCondition()