Class IdHashKey

java.lang.Object
org.troy.capstone.data_structures.item_table.IdHashKey
All Implemented Interfaces:
Cloneable
public class IdHashKey extends Object implements Cloneable
Class representing a hash key for item IDs, using universal hashing to minimize collisions in the item table. The hash code is computed by collapsing the string ID into an integer using a Rabin-Karp style polynomial rolling hash method, and then applying a universal hash function with random coefficients I and J and a prime modulus P. This approach helps ensure a good distribution of hash values even for similar string IDs, which is important for maintaining efficient lookups in the item table. Implements Cloneable to allow for deep copy of IdHashKey instances.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private static BigInteger
    I
    A random coefficient for the universal hash function, chosen uniformly from 1 to P-1.
    private static BigInteger
    J
    A random coefficient for the universal hash function, chosen uniformly from 0 to P-1.
    private static final BigInteger
    P
    A prime number larger than the maximum possible hash value from collapsing the strings, to ensure good distribution in universal hashing.
    private static final int
    TABLE_SIZE
    961 entries, 0.75 load factor -> 2048 table size 2048 is the lowest power of 2 above 961/0.75.
    private final String
    value
    The original string value of the item ID, stored for equality checks and potential debugging purposes.

  • Constructor Summary

    Constructors
    Constructor
    Description
    IdHashKey(String value)
    Constructor for the IdHashKey class.

  • Method Summary

    Modifier and Type
    Method
    Description
    Object
    clone()
    Returns a string representation of the IdHashKey, including the original string value and the computed hash code.
    private BigInteger
    collapseStringToInt(String str)
    Rabin-Karp style string to int collapse, using polynomial rolling hash method.
    boolean
    equals(Object obj)
    Checks if this IdHashKey is equal to another object.
    (package private) static BigInteger
    getI()
    Getter for the random coefficient I used in the universal hash function.
    (package private) static BigInteger
    getJ()
    Getter for the random coefficient J used in the universal hash function.
    (package private) static BigInteger
    getP()
    Getter for the prime modulus P used in the universal hash function.
    String
    getValue()
    Getter for the original string value of the item ID.
    int
    hashCode()
    Using universal hashing code from textbook, with small alterations.

    Methods inherited from class Object

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

  • Field Details

    • value

      private final String value
      The original string value of the item ID, stored for equality checks and potential debugging purposes.

    • P

      private static final BigInteger P
      A prime number larger than the maximum possible hash value from collapsing the strings, to ensure good distribution in universal hashing.

    • I

      private static BigInteger I
      A random coefficient for the universal hash function, chosen uniformly from 1 to P-1. Used as the multiplier in the universal hash formula. Not final to allow changing in testing.

    • J

      private static BigInteger J
      A random coefficient for the universal hash function, chosen uniformly from 0 to P-1. Used as the additive constant in the universal hash formula. Not final to allow changing in testing.

    • TABLE_SIZE

      private static final int TABLE_SIZE
      961 entries, 0.75 load factor -> 2048 table size 2048 is the lowest power of 2 above 961/0.75. The table size is chosen to be a power of 2 for efficient modulo operations.
      See Also:

  • Constructor Details

    • IdHashKey

      public IdHashKey(String value)
      Constructor for the IdHashKey class.
      Parameters:
      value - The original string value of the item ID to be hashed.

  • Method Details

    • getValue

      public String getValue()
      Getter for the original string value of the item ID.
      Returns:
      The original string value of the item ID.

    • getI

      static BigInteger getI()
      Getter for the random coefficient I used in the universal hash function.
      Returns:
      The random coefficient I.

    • getJ

      static BigInteger getJ()
      Getter for the random coefficient J used in the universal hash function.
      Returns:
      The random coefficient J.

    • getP

      static BigInteger getP()
      Getter for the prime modulus P used in the universal hash function.
      Returns:
      The prime modulus P.

    • hashCode

      public int hashCode()
      Using universal hashing code from textbook, with small alterations.
      Overrides:
      hashCode in class Object
      Returns:
      The hash code for the item ID.

    • collapseStringToInt

      private BigInteger collapseStringToInt(String str)
      Rabin-Karp style string to int collapse, using polynomial rolling hash method. Algorithm source is [3].
      Parameters:
      str - The string to collapse into an integer hash value.
      Returns:
      A hash value representing the input string collapsed via Rabin-Karp rolling hash.
      Preconditions:
      str is not null and only contains ASCII characters from '!' to '~' (printable characters excluding space and delete).

    • equals

      public boolean equals(Object obj)
      Checks if this IdHashKey is equal to another object.
      Overrides:
      equals in class Object
      Parameters:
      obj - The object to compare with.
      Returns:
      true if the objects are equal, false otherwise.

    • clone

      public Object clone() throws CloneNotSupportedException
      Returns a string representation of the IdHashKey, including the original string value and the computed hash code.
      Overrides:
      clone in class Object
      Returns:
      A string representation of the IdHashKey.
      Throws:
      CloneNotSupportedException