Package com.github.tommyettinger.textra.utils

Class CaseInsensitiveIntMap

java.lang.Object
com.github.tommyettinger.textra.utils.CaseInsensitiveIntMap
All Implemented Interfaces:
Iterable<CaseInsensitiveIntMap.Entry>
public class CaseInsensitiveIntMap extends Object implements Iterable<CaseInsensitiveIntMap.Entry>
An unordered map where the keys are case-insensitive Strings and the values are unboxed ints. Null keys are not allowed. No allocation is done except when growing the table size.

This class performs fast contains and remove (typically O(1), worst case O(n) but that is rare in practice). Add may be slightly slower, depending on hash collisions. Hashcodes are rehashed to reduce collisions and the need to resize. Load factors greater than 0.91 greatly increase the chances to resize to the next higher POT size.

This implementation uses linear probing with the backward shift algorithm for removal. Hashcodes are rehashed using a form of random hashing; a multiplier changes every time resize(int) gets called, which means if resize() has to be called early due to frequent collisions, the hashes will change when the multiplier does, and that may help alleviate the collisions. Linear probing continues to work even when all hashCodes collide, just more slowly.
This implementation is closely based on ObjectIntMap from libGDX, but also uses ideas from jdkgdxds, such as the randomized hashing (and the case-insensitive matching in general).

  • Field Details

    • size

      public int size

    • keyTable

      protected String[] keyTable

    • valueTable

      protected int[] valueTable

    • loadFactor

      protected float loadFactor

    • threshold

      protected int threshold

    • shift

      protected int shift
      Used by place(String) to bit shift the upper bits of a long into a usable range (>= 0 and <= mask). This class expects the shift to be > 32 and < 64, which, if used with an int, will still move the upper bits of an int to the lower bits due to Java's implicit modulus on shifts.

      Currently, shift isn't used to move bits in hashes, but it is updated and used to select different values for hashSeed, with the value changing when the map resizes.

    • mask

      protected int mask
      A bitmask used to confine hashcodes to the size of the table. Must be all 1-bits in its low positions, ie a power of two minus 1. In place(String), this is used to get the relevant low bits of a hash.

    • hashSeed

      protected int hashSeed
      Used by place(String) to modify hashCodeIgnoreCase(CharSequence, int) results. Changes on every call to resize(int) by default. This only needs to be serialized if the full key and value tables are serialized. Unless this is changed by some other code (which would need to be a subclass), hashSeed is fully determined by the shift when the map was constructed or last resized.

    • entries1

      protected transient CaseInsensitiveIntMap.Entries entries1

    • entries2

      protected transient CaseInsensitiveIntMap.Entries entries2

    • values1

      protected transient CaseInsensitiveIntMap.Values values1

    • values2

      protected transient CaseInsensitiveIntMap.Values values2

    • keys1

      protected transient CaseInsensitiveIntMap.Keys keys1

    • keys2

      protected transient CaseInsensitiveIntMap.Keys keys2

  • Constructor Details

    • CaseInsensitiveIntMap

      public CaseInsensitiveIntMap()
      Creates a new map with an initial capacity of 51 and a load factor of 0.6.

    • CaseInsensitiveIntMap

      public CaseInsensitiveIntMap(int initialCapacity)
      Creates a new map with a load factor of 0.6 .
      Parameters:
      initialCapacity - The backing array size is initialCapacity / loadFactor, increased to the next power of two.

    • CaseInsensitiveIntMap

      public CaseInsensitiveIntMap(int initialCapacity, float loadFactor)
      Creates a new map with the specified initial capacity and load factor. This map will hold initialCapacity items before growing the backing table.
      Parameters:
      initialCapacity - The backing array size is initialCapacity / loadFactor, increased to the next power of two.

    • CaseInsensitiveIntMap

      public CaseInsensitiveIntMap(String[] keys, int[] values)
      Creates a new map and puts key-value pairs sequentially from the two given arrays until either array is exhausted. The initial capacity will be the length of the shorter of the two arrays, and the load factor will be 0.6 .

    • CaseInsensitiveIntMap

      public CaseInsensitiveIntMap(CaseInsensitiveIntMap map)
      Creates a new map identical to the specified map.

  • Method Details

    • tableSize

      public static int tableSize(int capacity, float loadFactor)
      Used to establish the size of a hash table. The table size will always be a power of two, and should be the next power of two that is at least equal to capacity / loadFactor.
      Parameters:
      capacity - the amount of items the hash table should be able to hold
      loadFactor - between 0.0 (exclusive) and 1.0 (inclusive); the fraction of how much of the table can be filled
      Returns:
      the size of a hash table that can handle the specified capacity with the given loadFactor

    • place

      protected int place(String item)
      Returns an index >= 0 and <= mask for the specified item.

    • put

      public void put(String key, int value)

    • put

      public int put(String key, int value, int defaultValue)
      Returns the old value associated with the specified key, or the specified default value.

    • putAll

      public void putAll(String[] keys, int[] values)
      Puts keys with values in sequential pairs from the two arrays given, until either array is exhausted.

    • putAll

      public void putAll(CaseInsensitiveIntMap map)

    • get

      public int get(String key, int defaultValue)
      Returns the value for the specified key, or the default value if the key is not in the map.

    • getAndIncrement

      public int getAndIncrement(String key, int defaultValue, int increment)
      Returns the key's current value and increments the stored value. If the key is not in the map, defaultValue + increment is put into the map and defaultValue is returned.

    • remove

      public int remove(String key, int defaultValue)
      Returns the value for the removed key, or the default value if the key is not in the map.

    • notEmpty

      public boolean notEmpty()
      Returns true if the map has one or more items.

    • isEmpty

      public boolean isEmpty()
      Returns true if the map is empty.

    • shrink

      public void shrink(int maximumCapacity)
      Reduces the size of the backing arrays to be the specified capacity / loadFactor, or less. If the capacity is already less, nothing is done. If the map contains more items than the specified capacity, the next highest power of two capacity is used instead.

    • clear

      public void clear(int maximumCapacity)
      Clears the map and reduces the size of the backing arrays to be the specified capacity / loadFactor, if they are larger.

    • clear

      public void clear()

    • containsValue

      public boolean containsValue(int value)
      Returns true if the specified value is in the map. Note this traverses the entire map and compares every value, which may be an expensive operation.

    • containsKey

      public boolean containsKey(String key)

    • findKey

      public String findKey(int value)
      Returns the key for the specified value, or null if it is not in the map. Note this traverses the entire map and compares every value, which may be an expensive operation.

    • ensureCapacity

      public void ensureCapacity(int additionalCapacity)
      Increases the size of the backing array to accommodate the specified number of additional items / loadFactor. Useful before adding many items to avoid multiple backing array resizes.

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object

    • toString

      public String toString(String separator)

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • iterator

      public CaseInsensitiveIntMap.Entries iterator()
      Specified by:
      iterator in interface Iterable<CaseInsensitiveIntMap.Entry>

    • entries

      public CaseInsensitiveIntMap.Entries entries()
      Returns an iterator for the entries in the map. Remove is supported. Use the CaseInsensitiveIntMap.Entries constructor for nested or multithreaded iteration.

    • values

      public CaseInsensitiveIntMap.Values values()
      Returns an iterator for the values in the map. Remove is supported.

    • keys

      public CaseInsensitiveIntMap.Keys keys()
      Returns an iterator for the keys in the map. Remove is supported.

    • hashCodeIgnoreCase

      public static int hashCodeIgnoreCase(CharSequence data)
      Gets a 32-bit thoroughly-random hashCode from the given CharSequence, ignoring the case of any cased letters. Uses wyhash version 4.2, but shrunk down to work on 16-bit char values instead of 64-bit long values. This gets the hash as if all cased letters have been converted to upper case by Category.caseUp(char); this should be correct for all alphabets in Unicode except Georgian. Typically, place() methods in Sets and Maps here that want case-insensitive hashing would use this with (hashCodeIgnoreCase(text) >>> shift) or (hashCodeIgnoreCase(text) & mask).
      Parameters:
      data - a non-null CharSequence; often a String, but this has no trouble with a StringBuilder
      Returns:
      an int hashCode; quality should be similarly good across any bits

    • hashCodeIgnoreCase

      public static int hashCodeIgnoreCase(CharSequence data, int seed)
      Gets a 32-bit thoroughly-random hashCode from the given CharSequence, ignoring the case of any cased letters. UUses wyhash version 4.2, but shrunk down to work on 16-bit char values instead of 64-bit long values. This gets the hash as if all cased letters have been converted to upper case by Category.caseUp(char); this should be correct for all alphabets in Unicode except Georgian. Typically, place() methods in Sets and Maps here that want case-insensitive hashing would use this with (hashCodeIgnoreCase(text, seed) >>> shift) or (hashCodeIgnoreCase(text, seed) & mask).
      Parameters:
      data - a non-null CharSequence; often a String, but this has no trouble with a StringBuilder
      seed - any int; must be the same between calls if two equivalent values for data must be the same
      Returns:
      an int hashCode; quality should be similarly good across any bits