Package dev.tylermong.customhashmap

Class CustomHashMap<K,V>

java.lang.Object
dev.tylermong.customhashmap.CustomHashMap<K,V>
Type Parameters:
K - the type of keys maintained by this map
V - the type of mapped values
public class CustomHashMap<K,V> extends Object
This class is a custom implementation of a HashMap data structure using an array of linked lists for each bucket. This class handles generic key-value pairs and provides basic public methods such as: put, get, contains, and size. Internally, it has methods for hashing keys (simpleHash) and resizing the map when the load factor exceeds a predefined threshold (resize).
Version:
1.0
Author:
Tyler Mong

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private ArrayList<LinkedList<Entry<K,V>>>
    buckets
    Buckets used to store the key-value pairs.
    private int
    capacity
    The capacity of the HashMap.
    private static final int
    INITIAL_CAPACITY
    The initial capacity of the HashMap.
    private static final float
    LOAD_FACTOR
    The load factor threshold for resizing the HashMap.
    private int
    size
    The size of the HashMap, which is the number of key-value pairs currently stored in it.

  • Constructor Summary

    Constructors
    Constructor
    Description
    CustomHashMap()
    Constructs an empty HashMap with the default initial capacity of 16.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    contains(K key)
    Returns true if this HashMap contains a mapping for the specified key.
    V
    get(K key)
    Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
    private int
    hash(K key)
    Hashes the specified key to an index in the buckets array.
    V
    put(K key, V value)
    Associates the specified value with the specified key in this HashMap.
    V
    remove(K key)
    Removes the mapping for the specified key from this HashMap if present.
    private void
    resize()
    Resizes the HashMap by doubling its capacity and rehashing all existing entries.
    private int
    simpleHash(K key)
    Deprecated.
    This method uses a simple hashing algorithm, based on the length of the key, which causes a high number of collisions.
    int
    size()
    Returns the number of key-value mappings in this HashMap.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • INITIAL_CAPACITY

      private static final int INITIAL_CAPACITY
      The initial capacity of the HashMap. "1 invalid input: '<'invalid input: '<' 4" is "1" (0001) bitwise left shifted 4 times, which is equal to 16 (10000). "1 invalid input: '<'invalid input: '<' 4" is used to signify that the initial capacity is a power of 2, which is important for the getting the index in the hash method.
      See Also:

    • LOAD_FACTOR

      private static final float LOAD_FACTOR
      The load factor threshold for resizing the HashMap.
      See Also:

    • buckets

      private ArrayList<LinkedList<Entry<K,V>>> buckets
      Buckets used to store the key-value pairs. Each bucket is a linked list of entries.

    • capacity

      private int capacity
      The capacity of the HashMap. By default, it is set to INITIAL_CAPACITY, which is 16. The capacity is doubled when the load factor exceeds the threshold.

    • size

      private int size
      The size of the HashMap, which is the number of key-value pairs currently stored in it. The size is incremented when a new key-value pair is added and decremented when a key-value pair is removed. It is also used to determine when to resize the HashMap.

  • Constructor Details

    • CustomHashMap

      public CustomHashMap()
      Constructs an empty HashMap with the default initial capacity of 16. The size is initialized to 0, and each bucket is initialized as an empty linked list.

  • Method Details

    • put

      public V put(K key, V value)
      Associates the specified value with the specified key in this HashMap. If the HashMap previously contained a mapping for the key, the old value is replaced. Resizes the map if the load factor exceeds the threshold.
      Parameters:
      key - the key to be inserted into the HashMap
      value - the value to be associated with the key
      Returns:
      the old value associated with the key, or null if the key was not already present

    • get

      public V get(K key)
      Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
      Parameters:
      key - the key whose value is to be returned
      Returns:
      the value to which the key is mapped, or null if the key is not found in the HashMap

    • remove

      public V remove(K key)
      Removes the mapping for the specified key from this HashMap if present. If the map contains a mapping for the key, the value is removed and returned. Otherwise, it returns null.
      Parameters:
      key - the key whose mapping is to be removed
      Returns:
      the value to which the key was mapped, or null if the key is not found

    • simpleHash

      @Deprecated(since="1.0", forRemoval=false) private int simpleHash(K key)
      Deprecated.
      This method uses a simple hashing algorithm, based on the length of the key, which causes a high number of collisions. Use hash(Object) instead for a more efficient hashing algorithm, which implements Java's standard HashMap hashing algorithm.
      Hashes the specified key to an index in the buckets array.
      Parameters:
      key - the key to be hashed
      Returns:
      the length of the key, used as the index in the buckets array

    • hash

      private int hash(K key)
      Hashes the specified key to an index in the buckets array. This implementation is based on Java's standard HashMap hashing algorithm, which uses the key's hashCode method and applies a bitwise XOR operation to reduce collisions. It also ensures that the index is within the bounds of the buckets array by applying a bitwise AND operation with the capacity minus one, also from Java's standard HashMap implementation.
      Parameters:
      key - the key to be hashed
      Returns:
      the index in the buckets array where the key-value pair should be stored

    • contains

      public boolean contains(K key)
      Returns true if this HashMap contains a mapping for the specified key.
      Parameters:
      key - the key whose presence in this HashMap is to be tested
      Returns:
      true if this map contains a mapping for the specified key, false otherwise

    • resize

      private void resize()
      Resizes the HashMap by doubling its capacity and rehashing all existing entries.

    • size

      public int size()
      Returns the number of key-value mappings in this HashMap.
      Returns:
      the number of key-value mappings in this HashMap