?? bloomfilter64bit.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_07) on Sun May 06 17:59:51 GMT 2007 --><TITLE>BloomFilter64bit (Heritrix 1.12.1)</TITLE><META NAME="keywords" CONTENT="org.archive.util.BloomFilter64bit class"><LINK REL ="stylesheet" TYPE="text/css" HREF="../../../stylesheet.css" TITLE="Style"><SCRIPT type="text/javascript">function windowTitle(){ parent.document.title="BloomFilter64bit (Heritrix 1.12.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/BloomFilter64bit.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/BloomFilter32bp2Split.html" title="class in org.archive.util"><B>PREV CLASS</B></A> <A HREF="../../../org/archive/util/CachedBdbMap.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/BloomFilter64bit.html" target="_top"><B>FRAMES</B></A> <A HREF="BloomFilter64bit.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 BloomFilter64bit</H2><PRE>java.lang.Object <IMG SRC="../../../resources/inherit.gif" ALT="extended by "><B>org.archive.util.BloomFilter64bit</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>BloomFilter64bit</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>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> <li>Adapted to allow long bit indices so long as the index/64 (used an array index in bit vector) fits within Integer.MAX_VALUE</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/BloomFilter64bit.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.BloomFilter64bit">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/BloomFilter64bit.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/BloomFilter64bit.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/BloomFilter64bit.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/BloomFilter64bit.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/BloomFilter64bit.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/BloomFilter64bit.html#BloomFilter64bit(int, int)">BloomFilter64bit</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/BloomFilter64bit.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/BloomFilter64bit.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/BloomFilter64bit.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/BloomFilter64bit.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/BloomFilter64bit.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> int</CODE></FONT></TD><TD><CODE><B><A HREF="../../../org/archive/util/BloomFilter64bit.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>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -