Module org.apache.jena.core
Package org.apache.jena.mem2.collection

Class FastHashBase<K>

java.lang.Object
org.apache.jena.mem2.collection.FastHashBase<K>
Type Parameters:
K - the type of the keys
All Implemented Interfaces:
JenaMapSetCommon<K>
Direct Known Subclasses:
FastHashMap, FastHashSet
public abstract class FastHashBase<K> extends Object implements JenaMapSetCommon<K>
This is the base class for FastHashSet and FastHashSet. It only grows but never shrinks. This map does not guarantee any order. Although due to the way it is implemented the elements have a certain order. This map does not allow null keys. This map is not thread safe.

The positions array stores negative indices to the entries and hashCode arrays. The positions array is implemented as a power of two sized array. (like in HashMap) This allows to use a fast modulo operation to calculate the index. The indices of the positions array are derived from the hashCodes. Any position 0 indicates an empty element. The comparison with 0 is faster than comparing elements with null.

The keys are stored in a keys array and the hashCodesOrDeletedIndices array stores the hashCodes of the keys. hashCodesOrDeletedIndices is also used to store the indices of the deleted keys to save memory. It works like a linked list of deleted keys. The index of the previously deleted key is stored in the hashCodesOrDeletedIndices array. lastDeletedIndex is the index of the last deleted key in the hashCodesOrDeletedIndices array and serves as the head of the linked list of deleted keys. These two arrays grow together. They grow like ArrayList with a factor of 1.5.

keysPos is the index of the next free position in the keys array. The keys array is usually completely filled from index 0 to keysPos. Exceptions are the deleted keys. Indices that have been deleted are reused for new keys before the keys array is extended. The dense nature of the keys array enables fast iteration.

The index of a key in the keys array never changes. So the index of a key can be used as a handle to the key and for random access.

  • Method Details

    • size

      public int size()
      Returns the number of elements in this collection. If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.
      Specified by:
      size in interface JenaMapSetCommon<K>
      Returns:
      the number of elements in this collection

    • tryRemove

      public final boolean tryRemove(K o)
      Description copied from interface: JenaMapSetCommon
      Tries to remove a key from the collection.
      Specified by:
      tryRemove in interface JenaMapSetCommon<K>
      Parameters:
      o - the key to remove
      Returns:
      true if the key was removed. If the key was not present, false is returned.

    • tryRemove

      public final boolean tryRemove(K e, int hashCode)

    • removeAndGetIndex

      public final int removeAndGetIndex(K e)
      Removes the element at the given position.
      Parameters:
      e - the element
      Returns:
      the index of the removed element or -1 if the element was not found

    • removeAndGetIndex

      public final int removeAndGetIndex(K e, int hashCode)
      Removes the element at the given position.
      Parameters:
      e - the element
      hashCode - the hash code of the element. This is a performance optimization.
      Returns:
      the index of the removed element or -1 if the element was not found

    • removeUnchecked

      public final void removeUnchecked(K e)
      Description copied from interface: JenaMapSetCommon
      Removes a key from the collection. Attention: Implementations may assume that the key is present.
      Specified by:
      removeUnchecked in interface JenaMapSetCommon<K>
      Parameters:
      e - the key to remove

    • removeUnchecked

      public final void removeUnchecked(K e, int hashCode)

    • isEmpty

      public final boolean isEmpty()
      Returns true if this collection contains no elements.
      Specified by:
      isEmpty in interface JenaMapSetCommon<K>
      Returns:
      true if this collection contains no elements

    • containsKey

      public final boolean containsKey(K o)
      Description copied from interface: JenaMapSetCommon
      Check whether the collection contains a given key.
      Specified by:
      containsKey in interface JenaMapSetCommon<K>
      Parameters:
      o - the key to look for
      Returns:
      true if the collection contains the key

    • anyMatch

      public final boolean anyMatch(Predicate<K> predicate)
      Attentions: Due to the ordering of the keys, this method may be slow if matching elements are at the start of the list. Try to use anyMatchRandomOrder(Predicate) instead.
      Specified by:
      anyMatch in interface JenaMapSetCommon<K>
      Parameters:
      predicate - the predicate to match
      Returns:
      true if the collection contains any element matching the predicate

    • anyMatchRandomOrder

      public final boolean anyMatchRandomOrder(Predicate<K> predicate)
      This method can be faster than anyMatch(Predicate) if one expects to find many matches. But it is slower if one expects to find no matches or just a single one.
      Parameters:
      predicate - the predicate to apply to elements of this collection
      Returns:
      true if any element of the collection matches the predicate

    • keyIterator

      public final ExtendedIterator<K> keyIterator()
      Description copied from interface: JenaMapSetCommon
      Get an iterator over the keys in the collection.
      Specified by:
      keyIterator in interface JenaMapSetCommon<K>
      Returns:
      an iterator over the keys in the collection

    • clear

      public void clear()
      Removes all the elements from this collection (optional operation). The collection will be empty after this method returns.
      Specified by:
      clear in interface JenaMapSetCommon<K>
      Throws:
      UnsupportedOperationException - if the clear operation is not supported by this collection

    • keySpliterator

      public final Spliterator<K> keySpliterator()
      Description copied from interface: JenaMapSetCommon
      Get a spliterator over the keys in the collection.
      Specified by:
      keySpliterator in interface JenaMapSetCommon<K>
      Returns:
      a spliterator over the keys in the collection