Package org.apache.orc.util

Class CuckooSetBytes

java.lang.Object
org.apache.orc.util.CuckooSetBytes
public class CuckooSetBytes extends Object
A high-performance set implementation used to support fast set membership testing, using Cuckoo hashing. This is used to support fast tests of the form

column IN ( list-of-values )

For details on the algorithm, see R. Pagh and F. F. Rodler, "Cuckoo Hashing," Elsevier Science preprint, Dec. 2003. http://www.itu.dk/people/pagh/papers/cuckoo-jour.pdf.

Copied from CuckooSetBytes@Apache Hive project for convenience

  • Constructor Summary

    Constructors
    Constructor
    Description
    CuckooSetBytes(int expectedSize)
    Allocate a new set to hold expectedSize values.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    insert(byte[] x)
     
    void
    load(byte[][] a)
    Insert all values in the input array into the set.
    boolean
    lookup(byte[] b, int start, int len)
    Return true if and only if the value in byte array b beginning at start and ending at start+len is present in the set.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • CuckooSetBytes

      public CuckooSetBytes(int expectedSize)
      Allocate a new set to hold expectedSize values. Re-allocation to expand the set is not implemented, so the expected size must be at least the size of the set to be inserted.
      Parameters:
      expectedSize - At least the size of the set of values that will be inserted.

  • Method Details

    • lookup

      public boolean lookup(byte[] b, int start, int len)
      Return true if and only if the value in byte array b beginning at start and ending at start+len is present in the set.

    • insert

      public void insert(byte[] x)

    • load

      public void load(byte[][] a)
      Insert all values in the input array into the set.