bloomfilter32bp2split.html

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

<a name="129" href="#129">129</a> 
<a name="130" href="#130">130</a>         <strong>if</strong> ( DEBUG ) System.err.println( <span class="string">"Number of bits: "</span> + m );
<a name="131" href="#131">131</a> 
<a name="132" href="#132">132</a>         <em class="comment">// seeded for reproduceable behavior in repeated runs; BUT: </em>
<a name="133" href="#133">133</a>         <em class="comment">// SecureRandom's default implementation (as of 1.5) </em>
<a name="134" href="#134">134</a>         <em class="comment">// seems to mix in its own seeding.</em>
<a name="135" href="#135">135</a>         <strong>final</strong> SecureRandom random = <strong>new</strong> SecureRandom(<strong>new</strong> byte[] {19,96});
<a name="136" href="#136">136</a>         weight = <strong>new</strong> <strong>int</strong>[ d ][];
<a name="137" href="#137">137</a>         <strong>for</strong>( <strong>int</strong> i = 0; i &lt; d; i++ ) {
<a name="138" href="#138">138</a>             weight[ i ] = <strong>new</strong> <strong>int</strong>[ NUMBER_OF_WEIGHTS ];
<a name="139" href="#139">139</a>             <strong>for</strong>( <strong>int</strong> j = 0; j &lt; NUMBER_OF_WEIGHTS; j++ )
<a name="140" href="#140">140</a>                  weight[ i ][ j ] = random.nextInt();
<a name="141" href="#141">141</a>         }
<a name="142" href="#142">142</a>     }
<a name="143" href="#143">143</a> 
<a name="144" href="#144">144</a>     <em>/**<em>* The number of character sequences in the filter.</em></em>
<a name="145" href="#145">145</a> <em>     *</em>
<a name="146" href="#146">146</a> <em>     * @return the number of character sequences in the filter (but see {@link #contains(CharSequence)}).</em>
<a name="147" href="#147">147</a> <em>     */</em>
<a name="148" href="#148">148</a> 
<a name="149" href="#149">149</a>     <strong>public</strong> <strong>int</strong> size() {
<a name="150" href="#150">150</a>         <strong>return</strong> size;
<a name="151" href="#151">151</a>     }
<a name="152" href="#152">152</a> 
<a name="153" href="#153">153</a>     <em>/**<em>* Hashes the given sequence with the given hash function.</em></em>
<a name="154" href="#154">154</a> <em>     *</em>
<a name="155" href="#155">155</a> <em>     * @param s a character sequence.</em>
<a name="156" href="#156">156</a> <em>     * @param l the length of &lt;code>s&lt;/code>.</em>
<a name="157" href="#157">157</a> <em>     * @param k a hash function index (smaller than {@link #d}).</em>
<a name="158" href="#158">158</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="159" href="#159">159</a> <em>     */</em>
<a name="160" href="#160">160</a> 	<strong>private</strong> <strong>int</strong> hash( <strong>final</strong> CharSequence s, <strong>final</strong> <strong>int</strong> l, <strong>final</strong> <strong>int</strong> k ) {
<a name="161" href="#161">161</a> 		<strong>final</strong> <strong>int</strong>[] w = weight[ k ];
<a name="162" href="#162">162</a> 		<strong>int</strong> h = 0, i = l;
<a name="163" href="#163">163</a> 		<strong>while</strong>( i-- != 0 ) h ^= s.charAt( i ) * w[ i % NUMBER_OF_WEIGHTS ];
<a name="164" href="#164">164</a> 		<strong>return</strong> h >>> (32-power); 
<a name="165" href="#165">165</a> 	}
<a name="166" href="#166">166</a> 
<a name="167" href="#167">167</a>     <em>/**<em>* Checks whether the given character sequence is in this filter.</em></em>
<a name="168" href="#168">168</a> <em>     *</em>
<a name="169" href="#169">169</a> <em>     * &lt;P>Note that this method may return true on a character sequence that is has</em>
<a name="170" href="#170">170</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="171" href="#171">171</a> <em>     * where &lt;var>d&lt;/var> is the number of hash functions specified at creation time, if</em>
<a name="172" href="#172">172</a> <em>     * the number of the elements in the filter is less than &lt;var>n&lt;/var>, the number</em>
<a name="173" href="#173">173</a> <em>     * of expected elements specified at creation time.</em>
<a name="174" href="#174">174</a> <em>     *</em>
<a name="175" href="#175">175</a> <em>     * @param s a character sequence.</em>
<a name="176" href="#176">176</a> <em>     * @return true if the sequence is in the filter (or if a sequence with the</em>
<a name="177" href="#177">177</a> <em>     * same hash sequence is in the filter).</em>
<a name="178" href="#178">178</a> <em>     */</em>
<a name="179" href="#179">179</a> 
<a name="180" href="#180">180</a>     <strong>public</strong> <strong>boolean</strong> contains( <strong>final</strong> CharSequence s ) {
<a name="181" href="#181">181</a>         <strong>int</strong> i = d, l = s.length();
<a name="182" href="#182">182</a>         <strong>while</strong>( i-- != 0 ) <strong>if</strong> ( ! getBit( hash( s, l, i ) ) ) <strong>return</strong> false;
<a name="183" href="#183">183</a>         <strong>return</strong> <strong>true</strong>;
<a name="184" href="#184">184</a>     }
<a name="185" href="#185">185</a> 
<a name="186" href="#186">186</a>     <em>/**<em>* Adds a character sequence to the filter.</em></em>
<a name="187" href="#187">187</a> <em>     *</em>
<a name="188" href="#188">188</a> <em>     * @param s a character sequence.</em>
<a name="189" href="#189">189</a> <em>     * @return true if the character sequence was not in the filter (but see {@link #contains(CharSequence)}).</em>
<a name="190" href="#190">190</a> <em>     */</em>
<a name="191" href="#191">191</a> 
<a name="192" href="#192">192</a>     <strong>public</strong> <strong>boolean</strong> add( <strong>final</strong> CharSequence s ) {
<a name="193" href="#193">193</a>         <strong>boolean</strong> result = false;
<a name="194" href="#194">194</a>         <strong>int</strong> i = d, l = s.length();
<a name="195" href="#195">195</a>         <strong>int</strong> h;
<a name="196" href="#196">196</a>         <strong>while</strong>( i-- != 0 ) {
<a name="197" href="#197">197</a>             h = hash( s, l, i );
<a name="198" href="#198">198</a>             <strong>if</strong> ( ! setGetBit( h ) ) result = <strong>true</strong>;
<a name="199" href="#199">199</a>         }
<a name="200" href="#200">200</a>         <strong>if</strong> ( result ) size++;
<a name="201" href="#201">201</a>         <strong>return</strong> result;
<a name="202" href="#202">202</a>     }
<a name="203" href="#203">203</a>     
<a name="204" href="#204">204</a>     <strong>protected</strong> <strong>final</strong> <strong>static</strong> <strong>int</strong> ADDRESS_BITS_PER_UNIT = 5; <em class="comment">// 32=2^5</em>
<a name="205" href="#205">205</a>     <strong>protected</strong> <strong>final</strong> <strong>static</strong> <strong>int</strong> BIT_INDEX_MASK = 31; <em class="comment">// = BITS_PER_UNIT - 1;</em>
<a name="206" href="#206">206</a> 
<a name="207" href="#207">207</a>     <em>/**<em>*</em></em>
<a name="208" href="#208">208</a> <em>     * Returns from the local bitvector the value of the bit with </em>
<a name="209" href="#209">209</a> <em>     * the specified index. The value is &lt;tt>true&lt;/tt> if the bit </em>
<a name="210" href="#210">210</a> <em>     * with the index &lt;tt>bitIndex&lt;/tt> is currently set; otherwise, </em>
<a name="211" href="#211">211</a> <em>     * returns &lt;tt>false&lt;/tt>.</em>
<a name="212" href="#212">212</a> <em>     *</em>
<a name="213" href="#213">213</a> <em>     * (adapted from cern.colt.bitvector.QuickBitVector)</em>
<a name="214" href="#214">214</a> <em>     * </em>
<a name="215" href="#215">215</a> <em>     * @param     bitIndex   the bit index.</em>
<a name="216" href="#216">216</a> <em>     * @return    the value of the bit with the specified index.</em>
<a name="217" href="#217">217</a> <em>     */</em>
<a name="218" href="#218">218</a>     <strong>protected</strong> <strong>boolean</strong> getBit(<strong>int</strong> bitIndex) {
<a name="219" href="#219">219</a>         <strong>int</strong> <strong>int</strong>Index = (<strong>int</strong>)(bitIndex >>> ADDRESS_BITS_PER_UNIT);
<a name="220" href="#220">220</a>         <strong>return</strong> ((bits[intIndex>>>aShift][intIndex&amp;bMask] &amp; (1 &lt;&lt; (bitIndex &amp; BIT_INDEX_MASK))) != 0);
<a name="221" href="#221">221</a>     }
<a name="222" href="#222">222</a> 
<a name="223" href="#223">223</a>     <em>/**<em>*</em></em>
<a name="224" href="#224">224</a> <em>     * Changes the bit with index &lt;tt>bitIndex&lt;/tt> in local bitvector.</em>
<a name="225" href="#225">225</a> <em>     *</em>
<a name="226" href="#226">226</a> <em>     * (adapted from cern.colt.bitvector.QuickBitVector)</em>
<a name="227" href="#227">227</a> <em>     * </em>
<a name="228" href="#228">228</a> <em>     * @param     bitIndex   the index of the bit to be set.</em>
<a name="229" href="#229">229</a> <em>     */</em>
<a name="230" href="#230">230</a>     <strong>protected</strong> <strong>void</strong> setBit(<strong>int</strong> bitIndex) {
<a name="231" href="#231">231</a>         <strong>int</strong> <strong>int</strong>Index = (<strong>int</strong>)(bitIndex >>> ADDRESS_BITS_PER_UNIT);
<a name="232" href="#232">232</a>         bits[intIndex>>>aShift][intIndex&amp;bMask] |= 1 &lt;&lt; (bitIndex &amp; BIT_INDEX_MASK);
<a name="233" href="#233">233</a>     }
<a name="234" href="#234">234</a>     
<a name="235" href="#235">235</a>     <em>/**<em>*</em></em>
<a name="236" href="#236">236</a> <em>     * Sets the bit with index &lt;tt>bitIndex&lt;/tt> in local bitvector -- </em>
<a name="237" href="#237">237</a> <em>     * returning the old value. </em>
<a name="238" href="#238">238</a> <em>     *</em>
<a name="239" href="#239">239</a> <em>     * (adapted from cern.colt.bitvector.QuickBitVector)</em>
<a name="240" href="#240">240</a> <em>     * </em>
<a name="241" href="#241">241</a> <em>     * @param     bitIndex   the index of the bit to be set.</em>
<a name="242" href="#242">242</a> <em>     */</em>
<a name="243" href="#243">243</a>     <strong>protected</strong> <strong>boolean</strong> setGetBit(<strong>int</strong> bitIndex) {
<a name="244" href="#244">244</a>         <strong>int</strong> <strong>int</strong>Index = (<strong>int</strong>)(bitIndex >>> ADDRESS_BITS_PER_UNIT);
<a name="245" href="#245">245</a>         <strong>int</strong> a = <strong>int</strong>Index>>>aShift;
<a name="246" href="#246">246</a>         <strong>int</strong> b = <strong>int</strong>Index&amp;bMask;
<a name="247" href="#247">247</a>         <strong>int</strong> mask = 1 &lt;&lt; (bitIndex &amp; BIT_INDEX_MASK);
<a name="248" href="#248">248</a>         <strong>boolean</strong> ret = ((bits[a][b] &amp; (mask)) != 0);
<a name="249" href="#249">249</a>         bits[a][b] |= mask;
<a name="250" href="#250">250</a>         <strong>return</strong> ret;
<a name="251" href="#251">251</a>     }
<a name="252" href="#252">252</a>     
<a name="253" href="#253">253</a> 	<em class="comment">/*<em class="comment"> (non-Javadoc)</em></em>
<a name="254" href="#254">254</a> <em class="comment">	 * @see org.archive.util.BloomFilter#getSizeBytes()</em>
<a name="255" href="#255">255</a> <em class="comment">	 */</em>
<a name="256" href="#256">256</a> 	<strong>public</strong> <strong>long</strong> getSizeBytes() {
<a name="257" href="#257">257</a> 		<strong>return</strong> bits.length*bits[0].length*4;
<a name="258" href="#258">258</a> 	}
<a name="259" href="#259">259</a> }
</pre>
<hr/><div id="footer">This page was automatically generated by <a href="http://maven.apache.org/">Maven</a></div></body>
</html>