bloomfilter32bp2.html

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

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