import java.util.BitSet;
public class BloomFilter
{
/* BitSet初始分配2^24个bit */
private static final int DEFAULT_SIZE = 1 << 25;
/* 不同哈希函数的种子,一般应取质数 */
private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37, 61 };
private BitSet bits = new BitSet(DEFAULT_SIZE);
/* 哈希函数对象 */
private SimpleHash[] func = new SimpleHash[seeds.length];
public BloomFilter()
{
for (int i = 0; i < seeds.length; i++)
{
func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
// 将字符串标记到bits中
public void add(String value)
{
for (SimpleHash f : func)
{
bits.set(f.hash(value), true);
}
}
//判断字符串是否已经被bits标记
public boolean contains(String value)
{
if (value == null)
{
return false;
}
boolean ret = true;
for (SimpleHash f : func)
{
ret = ret && bits.get(f.hash(value));
}
return ret;
}
/* 哈希函数类 */
public static class SimpleHash
{
private int cap;
private int seed;
public SimpleHash(int cap, int seed)
{
this.cap = cap;
this.seed = seed;
}
//hash函数,采用简单的加权和hash
public int hash(String value)
{
int result = 0;
int len = value.length();
for (int i = 0; i < len; i++)
{
result = seed * result + value.charAt(i);
}
return (cap - 1) & result;
}
}
}
参考:
http://blog.csdn.net/lmh12506/article/details/7575651
http://blog.csdn.net/dandingyy/article/details/7408058
分享到:
相关推荐
这表明了STORM和KAFKA组合在实际应用中的有效性,以及如何设计出满足实时数据统计需求的系统架构。 在了解这个系统设计方法时,我们需要注意几个关键点: 1. 分布式计算:STORM是分布式计算的一个实例,它要求在多...
在Python中进行海量数据处理是一项挑战,因为Python解释器在内存管理和性能方面相对于其他专为大数据设计的语言(如Java或C++)可能稍显不足。然而,通过一些策略和技巧,我们可以有效地处理大规模数据。以下是从...
海量数据处理方法 海量数据处理是指基于海量数据上的存储、处理、操作,解决方案包括巧妙的算法搭配适合的数据结构,如 Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie 树,以及大而化小、分而治之的策略。...
海量数据处理方法总结 本文总结了常用的海量数据处理方法,包括 Bloom filter、Hashing 和 bit-map 等。这些方法可以用来解决大数据量的问题,例如数据字典、判重、集合求交集等问题。 Bloom Filter Bloom filter...
海量数据处理是互联网公司技术面试中的一个重要环节,它主要考察应聘者处理大规模数据集的能力,以及对各种存储、计算、排序算法的理解和应用。以下针对提供的文件内容,提炼出相关的知识点。 首先,海量数据处理的...
的海量数据处理,如数据分析、海量数据统计、数据挖掘和商业智能领域。 ODPS 提供了数据上传下载通道, SQL 处理操作,并且提供了完善的安全解决方案, 当前开 放的功能有: 数据通道:提供高并发的数据上传下载...
本文主要介绍了将海量数据快速、准确地导入和导出MATLAB系统的方法,这些方法克服了过去在命令窗口直接键入原始数据进行处理的多个问题,保证了统计分析结果的准确性和加速了MATLAB在统计分析领域的应用。...
### 海量数据处理关键技术解析 #### 一、海量数据处理概述 在当前的大数据时代,数据量的急剧增长使得传统的数据处理技术面临着前所未有的挑战。海量数据处理是指在合理的时间内,对大规模数据集进行高效存储、...
《海量数据的设计(十三讲)》是一门深入探讨大数据处理与管理的课程,涵盖了大数据时代的背景、技术核心以及在实际应用中的策略。本课程通过十三个主题,详细讲解了如何应对和利用海量数据,旨在提升对大数据处理的...
### 大数据量,海量数据处理方法总结 在IT领域,特别是大数据分析、数据库管理和算法设计方面,处理海量数据的能力是至关重要的技能之一。本文旨在总结处理大数据量、海量数据的有效方法,涵盖从理论基础到实际应用...
### 海量数据处理与面试题解析 #### 1. URL 去重算法 在处理海量URL时,需要高效地进行去重处理。一种常见的方式是通过哈希集(hash set)来实现。 - **方法一**:对于每个URL,将其添加到一个哈希集中。如果哈希...
### 大数据量、海量数据处理方法总结 #### 一、引言 随着互联网技术的发展,数据量呈现出爆炸性增长的趋势。如何高效地处理这些大数据成为了一项挑战性的任务。在IT行业,尤其是在搜索引擎、社交媒体等领域,处理...
### 海量数据处理技术深度解析 在当前信息爆炸的时代,如何高效地处理海量数据成为企业和科研领域关注的焦点。本文将围绕“海量数据处理”这一主题,详细探讨几种核心的技术方法,包括Bloom Filter、Hashing以及Bit...
### 海量数据处理知识点详解 #### 一、海量数据处理面试题解析 **1、海量日志数据,提取出某日访问百度次数最多的那个IP** - **问题概述**: 给定一天内的海量日志数据,从中找出访问百度次数最多的IP地址。 - **...
本文介绍了几种处理海量数据的有效方法,包括分片存储与去重、使用布隆过滤器、MapReduce框架的应用、统计特定字段、TOP-K问题、精确去重以及高效统计等。这些方法不仅有助于优化存储空间和计算资源,还能大大提高...
在当前的大数据时代,海量数据处理技术已成为IT行业的重要技术之一。面试中,关于海量数据处理的问题往往占据着举足轻重的地位,特别是在涉及秒杀系统、高并发处理和多线程应用的场景中。本文件《海量数据处理面试题...