Package sc.util

Class CoalescedHashMap<K,​T>

  • All Implemented Interfaces:
    java.io.Serializable, java.lang.Cloneable

    public class CoalescedHashMap<K,​T>
    extends java.lang.Object
    implements java.lang.Cloneable, java.io.Serializable
    This should be a faster implementation of the basic operations for a table whose size is known roughly before populating, elements are never removed, hash functions are relatively good. No hash-table entries are created for adding a new item. Items are put into a slot based on their hash code. If that spot is filled, we start at the top of the list and put it in the first entry spot. So a full list can have O(N) insert and O(N) lookup. Resizing is expensive so avoid using this if you do not have a good estimate of the size when you create the object. TODO: adjust these tuning parameters for table size and pad amount, compare to existing implementations for speed and space efficiency TODO: performance suggestion: when inserting a new entry, into a populated slot, swap the entry with the existing one, choosing the one with the shortest probe size (i.e. delta between key % tabSize and the index of the slot). When looking for an entry that's not in the table, if we pass an element whose probe-size is longer than the element we are looking for, we can be sure it's not in the table.
    See Also:
    Serialized Form
    • Field Summary

      Fields 
      Modifier and Type Field Description
      java.lang.Object[] keyTable  
      int size  
      java.lang.Object[] valueTable  
    • Constructor Summary

      Constructors 
      Constructor Description
      CoalescedHashMap​(int sz)  
    • Field Detail

      • keyTable

        public java.lang.Object[] keyTable
      • valueTable

        public java.lang.Object[] valueTable
      • size

        public int size
    • Constructor Detail

      • CoalescedHashMap

        public CoalescedHashMap​(int sz)
    • Method Detail

      • get

        public T get​(K key)
      • contains

        public boolean contains​(K key)
      • put

        public T put​(K key,
                     T value)