Class Common_hash_support

    • Field Detail

      • loadFactor

        protected final float loadFactor
      • initialCapacity

        protected final int initialCapacity
      • histogram

        protected int[] histogram
      • maxProbe

        protected int maxProbe
      • sizeWhichTriggersExpansion

        protected int sizeWhichTriggersExpansion
      • size

        private int size
      • removed

        protected int removed
      • found_removed

        protected int found_removed
        set to the first found_removed when searching
      • secondTimeShrinkable

        protected boolean secondTimeShrinkable
    • Constructor Detail

      • Common_hash_support

        public Common_hash_support​(int initialSizeBeforeExpanding)
        Parameters:
        initialSizeBeforeExpanding - the number of elements the table should hold before expanding
      • Common_hash_support

        public Common_hash_support​(int initialSizeBeforeExpanding,
                                   float factor)
    • Method Detail

      • clear

        public void clear()
      • clearExisting

        private void clearExisting()
      • findPosition

        protected int findPosition​(int hash,
                                   java.util.function.IntPredicate is_eq_or_not_present,
                                   java.util.function.IntPredicate is_removed_key)
        It gets a ref to the current value of table, and then searches that array. Side effect: found_removed is set to the position of the first REMOVED_KEY (if any) encountered during the search.
        Parameters:
        hash - the hash code of the key
        is_eq_or_not_present - true if the key at the int position is == to the key, or is 0
        is_removed_key - true if the key at the int position is "removed"
        Returns:
        the probeAddr in keys array. The value is the not-present-value if not found
      • maybeRebalanceRemoves

        private void maybeRebalanceRemoves()
        As REMOVED tokens populate, the number of 0's (representing free cells and also the end of bucket chain searches) drops. If this drops a lot, then searches take much longer. If there are no 0's left, searches never terminate! Keep the number of 0's at about 1 - load factor
      • copyOld2New

        private void copyOld2New​(int new_capacity,
                                 int old_capacity)
        This method calls the subclass's copy_to_new_table method, passing an inner lambda containing common code for copying old to new. That inner lambda, when invoked by the copy_to_new_table method, is passed another lambda of one argument (the old index) which is called to copy each element.
        Parameters:
        new_capacity -
        old_capacity -
      • moveToNextFilled

        protected int moveToNextFilled​(int pos)
        advance pos until it points to a non 0 or is 1 past end If pos is negative, start at 0. Don't move if pos already has valid key
        Parameters:
        pos - -
        Returns:
        updated pos
      • moveToPreviousFilled

        protected int moveToPreviousFilled​(int pos)
        decrement pos until it points to a non 0 or is -1 If pos is beyond end start at end. Don't move if pos already has valid key
        Parameters:
        pos - -
        Returns:
        updated pos
      • newTable

        protected void newTable​(int capacity)
      • incrementSize

        protected void incrementSize()
      • maybeIncreaseTableCapacity

        private void maybeIncreaseTableCapacity()
      • commonPutOrAddNotFound

        protected void commonPutOrAddNotFound()
      • commonRemove

        protected void commonRemove()
        only called if actually found and removed an entry
      • size

        public int size()
      • is_valid_key

        protected abstract boolean is_valid_key​(int pos)
      • keys_length

        protected abstract int keys_length()
      • newKeysAndValues

        protected abstract void newKeysAndValues​(int capacity)
      • clearKeysAndValues

        protected abstract void clearKeysAndValues()
      • resetHistogram

        protected void resetHistogram()
      • updateHistogram

        private void updateHistogram​(int nbrProbes)
      • showHistogram

        public void showHistogram()
      • getCapacity

        int getCapacity()
      • tableSpace

        public static int tableSpace​(int numberOfElements,
                                     java.lang.Float factor)
        Parameters:
        numberOfElements - -
        factor - -
        Returns:
        capacity of the main table (either 2 byte or 4 byte entries)
      • debugValidate

        protected void debugValidate()