📄 bloomfilter32bitsplit.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"><!--NewPage--><HTML><HEAD><!-- Generated by javadoc (build 1.5.0_06) on Wed Sep 27 16:03:12 PDT 2006 --><TITLE>BloomFilter32bitSplit (Heritrix 1.10.1)</TITLE><META NAME="keywords" CONTENT="org.archive.util.BloomFilter32bitSplit class"><LINK REL ="stylesheet" TYPE="text/css" HREF="../../../stylesheet.css" TITLE="Style"><SCRIPT type="text/javascript">function windowTitle(){ parent.document.title="BloomFilter32bitSplit (Heritrix 1.10.1)";}</SCRIPT><NOSCRIPT></NOSCRIPT></HEAD><BODY BGCOLOR="white" onload="windowTitle();"><!-- ========= START OF TOP NAVBAR ======= --><A NAME="navbar_top"><!-- --></A><A HREF="#skip-navbar_top" title="Skip navigation links"></A><TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY=""><TR><TD COLSPAN=2 BGCOLOR="#EEEEFF" CLASS="NavBarCell1"><A NAME="navbar_top_firstrow"><!-- --></A><TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY=""> <TR ALIGN="center" VALIGN="top"> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../overview-summary.html"><FONT CLASS="NavBarFont1"><B>Overview</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-summary.html"><FONT CLASS="NavBarFont1"><B>Package</B></FONT></A> </TD> <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> <FONT CLASS="NavBarFont1Rev"><B>Class</B></FONT> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="class-use/BloomFilter32bitSplit.html"><FONT CLASS="NavBarFont1"><B>Use</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A> </TD> <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A> </TD> </TR></TABLE></TD><TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM></EM></TD></TR><TR><TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2"> <A HREF="../../../org/archive/util/BloomFilter32bit.html" title="class in org.archive.util"><B>PREV CLASS</B></A> <A HREF="../../../org/archive/util/BloomFilter32bp2.html" title="class in org.archive.util"><B>NEXT CLASS</B></A></FONT></TD><TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2"> <A HREF="../../../index.html?org/archive/util/BloomFilter32bitSplit.html" target="_top"><B>FRAMES</B></A> <A HREF="BloomFilter32bitSplit.html" target="_top"><B>NO FRAMES</B></A> <SCRIPT type="text/javascript"> <!-- if(window==top) { document.writeln('<A HREF="../../../allclasses-noframe.html"><B>All Classes</B></A>'); } //--></SCRIPT><NOSCRIPT> <A HREF="../../../allclasses-noframe.html"><B>All Classes</B></A></NOSCRIPT></FONT></TD></TR><TR><TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2"> SUMMARY: NESTED | <A HREF="#field_summary">FIELD</A> | <A HREF="#constructor_summary">CONSTR</A> | <A HREF="#method_summary">METHOD</A></FONT></TD><TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">DETAIL: <A HREF="#field_detail">FIELD</A> | <A HREF="#constructor_detail">CONSTR</A> | <A HREF="#method_detail">METHOD</A></FONT></TD></TR></TABLE><A NAME="skip-navbar_top"></A><!-- ========= END OF TOP NAVBAR ========= --><HR><!-- ======== START OF CLASS DATA ======== --><H2><FONT SIZE="-1">org.archive.util</FONT><BR>Class BloomFilter32bitSplit</H2><PRE>java.lang.Object <IMG SRC="../../../resources/inherit.gif" ALT="extended by "><B>org.archive.util.BloomFilter32bitSplit</B></PRE><DL><DT><B>All Implemented Interfaces:</B> <DD>java.io.Serializable, <A HREF="../../../org/archive/util/BloomFilter.html" title="interface in org.archive.util">BloomFilter</A></DD></DL><HR><DL><DT><PRE>public class <B>BloomFilter32bitSplit</B><DT>extends java.lang.Object<DT>implements java.io.Serializable, <A HREF="../../../org/archive/util/BloomFilter.html" title="interface in org.archive.util">BloomFilter</A></DL></PRE><P>A Bloom filter. SLIGHTLY ADAPTED VERSION OF MG4J it.unimi.dsi.mg4j.util.BloomFilter <p>KEY CHANGES: <ul> <li>Adapted to use 32bit ops as much as possible... may be slightly faster on 32bit hardware/OS</li> <li>NUMBER_OF_WEIGHTS is 2083, to better avoid collisions between similar strings</li> <li>Removed dependence on cern.colt MersenneTwister (replaced with SecureRandom) and QuickBitVector (replaced with local methods).</li> </ul> <hr> <P>Instances of this class represent a set of character sequences (with false positives) using a Bloom filter. Because of the way Bloom filters work, you cannot remove elements. <P>Bloom filters have an expected error rate, depending on the number of hash functions used, on the filter size and on the number of elements in the filter. This implementation uses a variable optimal number of hash functions, depending on the expected number of elements. More precisely, a Bloom filter for <var>n</var> character sequences with <var>d</var> hash functions will use ln 2 <var>d</var><var>n</var> ≈ 1.44 <var>d</var><var>n</var> bits; false positives will happen with probability 2<sup>-<var>d</var></sup>. <P>Hash functions are generated at creation time using universal hashing. Each hash function uses <A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#NUMBER_OF_WEIGHTS"><CODE>NUMBER_OF_WEIGHTS</CODE></A> random integers, which are cyclically multiplied by the character codes in a character sequence. The resulting integers are XOR-ed together. <P>This class exports access methods that are very similar to those of <CODE>Set</CODE>, but it does not implement that interface, as too many non-optional methods would be unimplementable (e.g., iterators).<P><P><DL><DT><B>Author:</B></DT> <DD>Sebastiano Vigna</DD><DT><B>See Also:</B><DD><A HREF="../../../serialized-form.html#org.archive.util.BloomFilter32bitSplit">Serialized Form</A></DL><HR><P><!-- =========== FIELD SUMMARY =========== --><A NAME="field_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2"><B>Field Summary</B></FONT></TH></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected static long</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#ADDRESS_BITS_PER_UNIT">ADDRESS_BITS_PER_UNIT</A></B></CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected static long</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#BIT_INDEX_MASK">BIT_INDEX_MASK</A></B></CODE><BR> </TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> int</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#d">d</A></B></CODE><BR> The number of hash functions used by this filter.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> long</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#m">m</A></B></CODE><BR> The number of bits in this filter.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>static int</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#NUMBER_OF_WEIGHTS">NUMBER_OF_WEIGHTS</A></B></CODE><BR> The number of weights used to create hash functions.</TD></TR></TABLE> <!-- ======== CONSTRUCTOR SUMMARY ======== --><A NAME="constructor_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2"><B>Constructor Summary</B></FONT></TH></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#BloomFilter32bitSplit(int, int)">BloomFilter32bitSplit</A></B>(int n, int d)</CODE><BR> Creates a new Bloom filter with given number of hash functions and expected number of elements.</TD></TR></TABLE> <!-- ========== METHOD SUMMARY =========== --><A NAME="method_summary"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor"><TH ALIGN="left" COLSPAN="2"><FONT SIZE="+2"><B>Method Summary</B></FONT></TH></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> boolean</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#add(java.lang.CharSequence)">add</A></B>(java.lang.CharSequence s)</CODE><BR> Adds a character sequence to the filter.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> boolean</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#contains(java.lang.CharSequence)">contains</A></B>(java.lang.CharSequence s)</CODE><BR> Checks whether the given character sequence is in this filter.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected boolean</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#getBit(long)">getBit</A></B>(long bitIndex)</CODE><BR> Returns from the local bitvector the value of the bit with the specified index.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> long</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#getSizeBytes()">getSizeBytes</A></B>()</CODE><BR> The amount of memory in bytes consumed by the bloom bitfield.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected void</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#setBit(long)">setBit</A></B>(long bitIndex)</CODE><BR> Changes the bit with index <tt>bitIndex</tt> in local bitvector.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE>protected boolean</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#setGetBit(long)">setGetBit</A></B>(long bitIndex)</CODE><BR> Sets the bit with index <tt>bitIndex</tt> in local bitvector -- returning the old value.</TD></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD ALIGN="right" VALIGN="top" WIDTH="1%"><FONT SIZE="-1"><CODE> int</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter32bitSplit.html#size()">size</A></B>()</CODE><BR> The number of character sequences in the filter.</TD></TR></TABLE> <A NAME="methods_inherited_from_class_java.lang.Object"><!-- --></A><TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY=""><TR BGCOLOR="#EEEEFF" CLASS="TableSubHeadingColor"><TH ALIGN="left"><B>Methods inherited from class java.lang.Object</B></TH></TR><TR BGCOLOR="white" CLASS="TableRowColor"><TD><CODE>clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait</CODE></TD></TR></TABLE> <P><!-- ============ FIELD DETAIL =========== -->⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -