bloomfilter64bit.html

用JAVA编写的,在做实验的时候留下来的,本来想删的,但是传上来,大家分享吧

<a name="109" href="#109">109</a>         <em class="comment">// seeded for reproduceable behavior in repeated runs; BUT: </em>
<a name="110" href="#110">110</a>         <em class="comment">// SecureRandom's default implementation (as of 1.5) </em>
<a name="111" href="#111">111</a>         <em class="comment">// seems to mix in its own seeding.</em>
<a name="112" href="#112">112</a>         <strong>final</strong> SecureRandom random = <strong>new</strong> SecureRandom(<strong>new</strong> byte[] {19,96});
<a name="113" href="#113">113</a>         weight = <strong>new</strong> <strong>long</strong>[ d ][];
<a name="114" href="#114">114</a>         <strong>for</strong>( <strong>int</strong> i = 0; i &lt; d; i++ ) {
<a name="115" href="#115">115</a>             weight[ i ] = <strong>new</strong> <strong>long</strong>[ NUMBER_OF_WEIGHTS ];
<a name="116" href="#116">116</a>             <strong>for</strong>( <strong>int</strong> j = 0; j &lt; NUMBER_OF_WEIGHTS; j++ )
<a name="117" href="#117">117</a>                  weight[ i ][ j ] = random.nextLong();
<a name="118" href="#118">118</a>         }
<a name="119" href="#119">119</a>     }
<a name="120" href="#120">120</a> 
<a name="121" href="#121">121</a>     <em>/**<em>* The number of character sequences in the filter.</em></em>
<a name="122" href="#122">122</a> <em>     *</em>
<a name="123" href="#123">123</a> <em>     * @return the number of character sequences in the filter (but see {@link #contains(CharSequence)}).</em>
<a name="124" href="#124">124</a> <em>     */</em>
<a name="125" href="#125">125</a> 
<a name="126" href="#126">126</a>     <strong>public</strong> <strong>int</strong> size() {
<a name="127" href="#127">127</a>         <strong>return</strong> size;
<a name="128" href="#128">128</a>     }
<a name="129" href="#129">129</a> 
<a name="130" href="#130">130</a>     <em>/**<em>* Hashes the given sequence with the given hash function.</em></em>
<a name="131" href="#131">131</a> <em>     *</em>
<a name="132" href="#132">132</a> <em>     * @param s a character sequence.</em>
<a name="133" href="#133">133</a> <em>     * @param l the length of &lt;code>s&lt;/code>.</em>
<a name="134" href="#134">134</a> <em>     * @param k a hash function index (smaller than {@link #d}).</em>
<a name="135" href="#135">135</a> <em>     * @return the position in the filter corresponding to &lt;code>s&lt;/code> for the hash function &lt;code>k&lt;/code>.</em>
<a name="136" href="#136">136</a> <em>     */</em>
<a name="137" href="#137">137</a> 
<a name="138" href="#138">138</a>     <strong>private</strong> <strong>long</strong> hash( <strong>final</strong> CharSequence s, <strong>final</strong> <strong>int</strong> l, <strong>final</strong> <strong>int</strong> k ) {
<a name="139" href="#139">139</a>         <strong>final</strong> <strong>long</strong>[] w = weight[ k ];
<a name="140" href="#140">140</a>         <strong>long</strong> h = 0;
<a name="141" href="#141">141</a>         <strong>int</strong> i = l;
<a name="142" href="#142">142</a>         <strong>while</strong>( i-- != 0 ) h ^= s.charAt( i ) * w[ i % NUMBER_OF_WEIGHTS ];
<a name="143" href="#143">143</a>         <strong>return</strong> ( h &amp; 0x7FFFFFFFFFFFFFFFL ) % m;
<a name="144" href="#144">144</a>     }
<a name="145" href="#145">145</a> 
<a name="146" href="#146">146</a>     <em>/**<em>* Checks whether the given character sequence is in this filter.</em></em>
<a name="147" href="#147">147</a> <em>     *</em>
<a name="148" href="#148">148</a> <em>     * &lt;P>Note that this method may return true on a character sequence that is has</em>
<a name="149" href="#149">149</a> <em>     * not been added to the filter. This will happen with probability 2&lt;sub>-&lt;var>d&lt;/var>&lt;/sub>,</em>
<a name="150" href="#150">150</a> <em>     * where &lt;var>d&lt;/var> is the number of hash functions specified at creation time, if</em>
<a name="151" href="#151">151</a> <em>     * the number of the elements in the filter is less than &lt;var>n&lt;/var>, the number</em>
<a name="152" href="#152">152</a> <em>     * of expected elements specified at creation time.</em>
<a name="153" href="#153">153</a> <em>     *</em>
<a name="154" href="#154">154</a> <em>     * @param s a character sequence.</em>
<a name="155" href="#155">155</a> <em>     * @return true if the sequence is in the filter (or if a sequence with the</em>
<a name="156" href="#156">156</a> <em>     * same hash sequence is in the filter).</em>
<a name="157" href="#157">157</a> <em>     */</em>
<a name="158" href="#158">158</a> 
<a name="159" href="#159">159</a>     <strong>public</strong> <strong>boolean</strong> contains( <strong>final</strong> CharSequence s ) {
<a name="160" href="#160">160</a>         <strong>int</strong> i = d, l = s.length();
<a name="161" href="#161">161</a>         <strong>while</strong>( i-- != 0 ) <strong>if</strong> ( ! getBit( hash( s, l, i ) ) ) <strong>return</strong> false;
<a name="162" href="#162">162</a>         <strong>return</strong> <strong>true</strong>;
<a name="163" href="#163">163</a>     }
<a name="164" href="#164">164</a> 
<a name="165" href="#165">165</a>     <em>/**<em>* Adds a character sequence to the filter.</em></em>
<a name="166" href="#166">166</a> <em>     *</em>
<a name="167" href="#167">167</a> <em>     * @param s a character sequence.</em>
<a name="168" href="#168">168</a> <em>     * @return true if the character sequence was not in the filter (but see {@link #contains(CharSequence)}).</em>
<a name="169" href="#169">169</a> <em>     */</em>
<a name="170" href="#170">170</a> 
<a name="171" href="#171">171</a>     <strong>public</strong> <strong>boolean</strong> add( <strong>final</strong> CharSequence s ) {
<a name="172" href="#172">172</a>         <strong>boolean</strong> result = false;
<a name="173" href="#173">173</a>         <strong>int</strong> i = d, l = s.length();
<a name="174" href="#174">174</a>         <strong>long</strong> h;
<a name="175" href="#175">175</a>         <strong>while</strong>( i-- != 0 ) {
<a name="176" href="#176">176</a>             h = hash( s, l, i );
<a name="177" href="#177">177</a>             <strong>if</strong> ( ! getBit( h ) ) result = <strong>true</strong>;
<a name="178" href="#178">178</a>             setBit( h );
<a name="179" href="#179">179</a>         }
<a name="180" href="#180">180</a>         <strong>if</strong> ( result ) size++;
<a name="181" href="#181">181</a>         <strong>return</strong> result;
<a name="182" href="#182">182</a>     }
<a name="183" href="#183">183</a>     
<a name="184" href="#184">184</a>     <strong>protected</strong> <strong>final</strong> <strong>static</strong> <strong>long</strong> ADDRESS_BITS_PER_UNIT = 6; <em class="comment">// 64=2^6</em>
<a name="185" href="#185">185</a>     <strong>protected</strong> <strong>final</strong> <strong>static</strong> <strong>long</strong> BIT_INDEX_MASK = 63; <em class="comment">// = BITS_PER_UNIT - 1;</em>
<a name="186" href="#186">186</a> 
<a name="187" href="#187">187</a>     <em>/**<em>*</em></em>
<a name="188" href="#188">188</a> <em>     * Returns from the local bitvector the value of the bit with </em>
<a name="189" href="#189">189</a> <em>     * the specified index. The value is &lt;tt>true&lt;/tt> if the bit </em>
<a name="190" href="#190">190</a> <em>     * with the index &lt;tt>bitIndex&lt;/tt> is currently set; otherwise, </em>
<a name="191" href="#191">191</a> <em>     * returns &lt;tt>false&lt;/tt>.</em>
<a name="192" href="#192">192</a> <em>     *</em>
<a name="193" href="#193">193</a> <em>     * (adapted from cern.colt.bitvector.QuickBitVector)</em>
<a name="194" href="#194">194</a> <em>     * </em>
<a name="195" href="#195">195</a> <em>     * @param     bitIndex   the bit index.</em>
<a name="196" href="#196">196</a> <em>     * @return    the value of the bit with the specified index.</em>
<a name="197" href="#197">197</a> <em>     */</em>
<a name="198" href="#198">198</a>     <strong>protected</strong> <strong>boolean</strong> getBit(<strong>long</strong> bitIndex) {
<a name="199" href="#199">199</a>         <strong>return</strong> ((bits[(<strong>int</strong>)(bitIndex >> ADDRESS_BITS_PER_UNIT)] &amp; (1L &lt;&lt; (bitIndex &amp; BIT_INDEX_MASK))) != 0);
<a name="200" href="#200">200</a>     }
<a name="201" href="#201">201</a> 
<a name="202" href="#202">202</a>     <em>/**<em>*</em></em>
<a name="203" href="#203">203</a> <em>     * Changes the bit with index &lt;tt>bitIndex&lt;/tt> in local bitvector.</em>
<a name="204" href="#204">204</a> <em>     *</em>
<a name="205" href="#205">205</a> <em>     * (adapted from cern.colt.bitvector.QuickBitVector)</em>
<a name="206" href="#206">206</a> <em>     * </em>
<a name="207" href="#207">207</a> <em>     * @param     bitIndex   the index of the bit to be set.</em>
<a name="208" href="#208">208</a> <em>     */</em>
<a name="209" href="#209">209</a>     <strong>protected</strong> <strong>void</strong> setBit( <strong>long</strong> bitIndex) {
<a name="210" href="#210">210</a>             bits[(<strong>int</strong>)(bitIndex >> ADDRESS_BITS_PER_UNIT)] |= 1L &lt;&lt; (bitIndex &amp; BIT_INDEX_MASK);
<a name="211" href="#211">211</a>     }
<a name="212" href="#212">212</a>     
<a name="213" href="#213">213</a> 	<em class="comment">/*<em class="comment"> (non-Javadoc)</em></em>
<a name="214" href="#214">214</a> <em class="comment">	 * @see org.archive.util.BloomFilter#getSizeBytes()</em>
<a name="215" href="#215">215</a> <em class="comment">	 */</em>
<a name="216" href="#216">216</a> 	<strong>public</strong> <strong>long</strong> getSizeBytes() {
<a name="217" href="#217">217</a> 		<strong>return</strong> bits.length*8;
<a name="218" href="#218">218</a> 	}
<a name="219" href="#219">219</a> }
</pre>
<hr/><div id="footer">This page was automatically generated by <a href="http://maven.apache.org/">Maven</a></div></body>
</html>