craterdog.collections.primitives

Class HashTable<K,V>

java.lang.Object

java.util.AbstractMap<K,V>

craterdog.collections.primitives.HashTable<K,V>

Type Parameters:

K - The type of keys in the table.

V - The type of values in the table.

All Implemented Interfaces:

java.lang.Cloneable, java.util.Map<K,V>

public final class HashTable<K,V>
extends java.util.AbstractMap<K,V>
implements java.util.Map<K,V>, java.lang.Cloneable

This class provides an implementation of hash table that scales up and down geometrically as the number of elements increases and decreases. When the number of elements in the table reaches its current capacity, it automatically doubles its capacity. When the number of elements drops below 1/4th of its current capacity, it automatically halves its capacity. This ensures a hysteresis of 1/2 its capacity so that it won't oscillate up and down with small changes in number of elements near a boundary condition.

Author:

Derk Norton

Nested Class Summary

Nested classes/interfaces inherited from class java.util.AbstractMap

java.util.AbstractMap.SimpleEntry<K,V>, java.util.AbstractMap.SimpleImmutableEntry<K,V>

Nested classes/interfaces inherited from interface java.util.Map

java.util.Map.Entry<K,V>

Constructor Summary

Constructors

Constructor and Description
HashTable() This default constructor creates an instance of a hash table with the minimum capacity (16 elements).
HashTable(int minimumCapacity) This constructor creates an instance of a hash table with at least the specified minimum capacity.
HashTable(java.util.Map<? extends K,? extends V> elements) This constructor creates an instance of a hash table that contains the elements from the specified collection.

Method Summary

Modifier and Type	Method and Description
void	clear()
java.lang.Object	clone()
boolean	containsKey(java.lang.Object key)
boolean	containsValue(java.lang.Object value)
java.util.Set<java.util.Map.Entry<K,V>>	entrySet()
V	get(java.lang.Object key)
boolean	isEmpty()
V	put(K key, V value)
V	remove(java.lang.Object key)
int	size()

Methods inherited from class java.util.AbstractMap

equals, hashCode, keySet, putAll, toString, values

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, equals, forEach, getOrDefault, hashCode, keySet, merge, putAll, putIfAbsent, remove, replace, replace, replaceAll, values

Constructor Detail

HashTable

public HashTable()

This default constructor creates an instance of a hash table with the minimum capacity (16 elements).

HashTable

public HashTable(int minimumCapacity)

This constructor creates an instance of a hash table with at least the specified minimum capacity. The actual capacity will be a power of two that is greater or equal to the specified minimum capacity.

Parameters:

minimumCapacity - The minimum initial size of the table.

HashTable

public HashTable(java.util.Map<? extends K,? extends V> elements)

This constructor creates an instance of a hash table that contains the elements from the specified collection.

Parameters:

elements - The elements that should be used to seed the table.

Method Detail

size

public int size()

Specified by:

size in interface java.util.Map<K,V>

Overrides:

size in class java.util.AbstractMap<K,V>

clear

public void clear()

Specified by:

clear in interface java.util.Map<K,V>

Overrides:

clear in class java.util.AbstractMap<K,V>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Map<K,V>

Overrides:

isEmpty in class java.util.AbstractMap<K,V>

containsKey

public boolean containsKey(java.lang.Object key)

Specified by:

containsKey in interface java.util.Map<K,V>

Overrides:

containsKey in class java.util.AbstractMap<K,V>

containsValue

public boolean containsValue(java.lang.Object value)

Specified by:

containsValue in interface java.util.Map<K,V>

Overrides:

containsValue in class java.util.AbstractMap<K,V>

get

public V get(java.lang.Object key)

Specified by:

get in interface java.util.Map<K,V>

Overrides:

get in class java.util.AbstractMap<K,V>

put

public V put(K key,
             V value)

Specified by:

put in interface java.util.Map<K,V>

Overrides:

put in class java.util.AbstractMap<K,V>

remove

public V remove(java.lang.Object key)

Specified by:

remove in interface java.util.Map<K,V>

Overrides:

remove in class java.util.AbstractMap<K,V>

entrySet

public java.util.Set<java.util.Map.Entry<K,V>> entrySet()

Specified by:

entrySet in interface java.util.Map<K,V>

Specified by:

entrySet in class java.util.AbstractMap<K,V>

clone

public java.lang.Object clone()

Overrides:

clone in class java.util.AbstractMap<K,V>