正文
java代码实现去重队列 java去重复代码
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
java url参数去重
言归正传。
所谓的Url去重（我一直没找到对应的英文，URL Filtering ?），就是爬虫将重复抓取的URL去除，避免多次抓取同一网页。爬虫一般会将待抓取的URL放在一个队列中，从抓取后的网页中提取到新的URL，在他们被放入队列之前，首先要确定这些新的URL没有被抓取过，如果之前已经抓取过了，就不再放入队列。
最直观的做法 – hash表
为了尽快把整个爬虫搭建起来，最开始的URL去重采用方案是一个内存中的HashSet，这是最直观的方法，所有人都能想得到。HashSet中放置的就是URL的字符串，任何一个新的URL首先在HashSet中进行查找，如果HashSet中没有，就将新的URL插入HashSet，并将URL放入待抓取队列。
这个方案的好处是它的去重效果精确，不会漏过一个重复的URL。它的缺点是，我的爬虫第二天早上就挂了，Out Of Memory。因为随着抓取网页的增加，HashSet会一直无限制的增长。另外，网络中的很多URL其实是很长的，有大量的URL长度达到上百个字符。当然，因为我的爬虫是跑在一个小服务器上，JVM的内存本来就不多，否则它应该能再多撑1-2天。
简单估算一下，假设单个URL的平均长度是100 byte（我觉着这已经非常保守了），那么抓取1000万的URL就需要：
100 byte * 10 000 000 = 1 GB
而1000万URL在整个互联网中实在是沧海一粟。可以了解，需要多大的内存才能装下所有URL的HashSet。
压缩URL
为了我的爬虫能再多撑几天，同时不想改动太多的代码，第二个版本增加了一个小功能，就是HashSet中不存储原始的URL，而是将URL压缩后再放进去。貌似有不少paper中讨论过如何对URL进行压缩，包括新浪微博中的短URL其实也是个不错的方案，可惜这些方法我都不会。为了偷懒，我直接用MD5对URL做编码。
MD5的结果是128 bit也就是16 byte的长度。相比于之间估计的URL平均长度100byte已经缩小了好几倍，可以多撑好多天了。
当然，哪怕找个一个可以压缩到极致的算法，随着URL越来越多，终有一天会Out Of Memory。所以，这个方案不解决本质问题。
MD5另外一个问题是，有可能两个相同的URL被映射成同一个MD5值，这样的话，它们中有一个就永远不会被抓取了。我不太确定的是，这个概率会有多大。如果非常小的话，这微小的误差倒也不会有太大影响。
Bloom Filter
基于内存的HashSet的方法存在一个本质的问题，就是它消耗的内存是随着URL的增长而不断增长的。除非能够保证内存的大小能够容纳下所有需要抓取的URL，否则这个方案终有一天会到达瓶颈。
这时候就会想，要找一个类似于HashSet的但所消耗的内存相对固定而不会不断增长的方案，于是自然想到了Bloom Filter。关于Bloom Filter的概念这里就不多谈了，网上随处可以找到。我简单尝试了一下Bloom Filter，但是很快就放弃了。基于Bloom Filter的方案有几个问题：
第一个是理论上的。Bloom Filter会将一些正常的样本（在我这就是没有抓取过的URL）过滤掉，即所谓的False Positive。当然，这概率有多大，取决于Bloom Filter的参数设置。但这引出了下一个问题；
第二个是实践中的，即Bloom Filter的那几个参数应该如何设置？m，k，n应该设置成多少才合适，这个我没有经验，而且可能需要反复的实验和测试才能够比较好的确定下来；
以上两个问题还不是我放弃Bloom Filter的根本原因，真实的原因是我在做的是一个爬虫框架，上面可以会启动很多的爬虫任务，每个任务可能抓取自己特定的URL，而且任务之间是独立的。这样，对于每个任务都需要有一个Bloom Filter，虽然对于单一任务它使用Bloom Filter所消耗的内存是固定的，但是任务的增多会导致更多的Bloom Filter，从而导致更多的内存消耗。仍然存在内存溢出的可能。
但如果只是一个抓取任务，那么采用Bloom Filter应该是一个非常不错的选择。
BerkeleyDB
我终于明白我所需要的其实是一个可以放在disk上的去重方案，这样，内存溢出将永远成不了可能。很早就知道有BerkeleyDB这么一个东西，但第一次真正了解还是在Amazon的Dynamo那篇论文中提到过采用了BerkeleyDB作为单机上的底层存储。当时觉着这东西真另类，原来还有叫做“DB”的东西却不支持SQL。那时候还没有NOSQL这词，把这样的东西叫做non-relational database。
BerkeleyDB是一个key-value database，简单的说，就是一个在disk上的hash表，这也是为什么它可以被用来做URL去重的原因。它另外一个另类的地方是，它是和程序运行在同一个进程空间中的，而不像一般的db，是做为单独的程序运行。
这里附上Heritrix中使用BerkeleyDB做URL去重的代码，一探究竟：（代码位于Heritrix源代码的org.archive.crawler.util.BdbUriUniqFilter）
有一堆做初始化和配置的函数就直接忽略了，真正相关的函数就只有两个：
[java] view plaincopy
/**
* Create fingerprint.
* Pubic access so test code can access createKey.
* @param uri URI to fingerprint.
* @return Fingerprint of passed codeurl/code.
*/
public static long createKey(CharSequence uri) {
String url = uri.toString();
int index = url.indexOf(COLON_SLASH_SLASH);
if (index 0) {
index = url.indexOf('/', index + COLON_SLASH_SLASH.length());
}
CharSequence hostPlusScheme = (index == -1)? url: url.subSequence(0, index);
long tmp = FPGenerator.std24.fp(hostPlusScheme);
return tmp | (FPGenerator.std40.fp(url) 24);
}
[java] view plaincopy
/**
* value: only 1 byte
*/
private static DatabaseEntry ZERO_LENGTH_ENTRY = new DatabaseEntry(
new byte[0]);
protected boolean setAdd(CharSequence uri) {
DatabaseEntry key = new DatabaseEntry();
LongBinding.longToEntry(createKey(uri), key);
long started = 0;
OperationStatus status = null;
try {
if (logger.isLoggable(Level.INFO)) {
started = System.currentTimeMillis();
}
status = alreadySeen.putNoOverwrite(null, key, ZERO_LENGTH_ENTRY);
if (logger.isLoggable(Level.INFO)) {
aggregatedLookupTime +=
(System.currentTimeMillis() - started);
}
} catch (DatabaseException e) {
logger.severe(e.getMessage());
}
if (status == OperationStatus.SUCCESS) {
count++;
if (logger.isLoggable(Level.INFO)) {
final int logAt = 10000;
if (count 0 ((count % logAt) == 0)) {
logger.info("Average lookup " +
(aggregatedLookupTime / logAt) + "ms.");
aggregatedLookupTime = 0;
}
}
}
if(status == OperationStatus.KEYEXIST) {
return false; // not added
} else {
return true;
}
}
简单解释一下：
第一个函数createKey是在做URL的压缩，它将任意长度的URL转换成一个long型的值。long型的取值范围有2^64，因此两个URL映射成同一个long型值的概率应该挺低的。但我也没太细看这个函数，所以它的效果到底如何不确定。
第二个函数setAdd就是将被压缩的URL写入到BerkeleyDB。之前说过，BerkeleyDB是一个key-value database，它的每条记录都包括了一个key和一个value。但是在URL去重中，value不重要（比如我们之前内存中用的也是HashSet而不是HashMap），因此这里统一用一个byte长度的值来表示value，就是这个static变量ZERO_LENGTH_ENTRY。
别看setAdd有这么多行，真正有用的就这一行：
[java] view plaincopy
status = alreadySeen.putNoOverwrite(null, key, ZERO_LENGTH_ENTRY);
将压缩后得到的long型值作为key，ZERO_LENGTH_ENTRY作为value插入到BerkeleyDB中，如果db中已经有了这个long型值，就会返回OperationStatus.KEYEXIST，表示对应的URL之前已经抓取到了，那么这个URL就不会放入待抓取队列中。
最后
比较遗憾的是，我还没抽出空对BerkeleyDB这个方案做性能测试，不确定它每秒能执行多少次setAdd操作，是否足够满足我们性能的要求。以后补上。
另外，虽然我不了解，但我认为像百度这样专业的搜索引擎，它的爬虫的URL去重方案可能比这里列举的要复杂的多，毕竟那个的各方面的要求也要更高。
相关问答
Q1: 用Java或C++编程实现10000个整数去重，效率要高些
追求效率的话，肯定得用C++
整数有范围限制吗？如果范围小的话，可以打表，比如1000万以内的数字的话，用1M多的bit表就可以一次性筛选出来。int范围的话，用512M内存，可以一次循环扫过，但是内存开销太大
如果没有内存上的限制 这个方法绝对是最快的。而且也可以找到重复的
如果没有范围，或者范围太大，不适合达标，可以用C++ STL中的priority_queue 依次压入 然后弹出，有重复的去掉
Q2: 用java实现循环队列？
简单写了下，希望你能看明白
import java.util.ArrayList;
public class SeqQueue {
ArrayListString list;
public SeqQueue() {
list = new ArrayListString();
}
public String getFirst() {
if (!list.isEmpty()) {
String s = list.get(0);
list.remove(0);
return s;
}
return null;
}
public void insertLast(String s) {
list.add(s);
}
public static void main(String[] args) {
SeqQueue seq = new SeqQueue();
seq.insertLast("111");
seq.insertLast("222");
seq.insertLast("333");
System.out.println(seq.getFirst());
System.out.println(seq.getFirst());
System.out.println(seq.getFirst());
}
}
Q3: java List怎么分组去重
使用set集合啊java代码实现去重队列，set集合是不能放重复的数据的。
Set hashSet = new HashSet(list);
然后在转过来就行了java代码实现去重队列，set去除重复是调用了equals方法，所以你在Sh里面要重写equals方法，自定义比较的规则，例如：
public boolean equals(Object obj) {
if(obj==null) return false;
if(obj==this) return true;
Sh sh = (Sh)obj;
if(sh.getHm()==this.getHm()){
return true;
}
return false;
}
Q4: java 用什么实现 FIFO队列？
java使用数据结构来实现FIFO先进先出的队列，实例如下：
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package linkedlisttest;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
/**
*
* @author Vicky.H
* @email eclipser@163.com
*/
public class FIFOTest {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
FIFOA fifo = new FIFOImplA(5);
for (int i = 0; i 20; i++) {
A a = new A("A:" + i);
A head = fifo.addLastSafe(a);
System.out.println(i + "\thead:" + head + "\tsize:" + fifo.size());
}
System.out.println("---------------");
System.out.println("弹出数据");
ListA polls = fifo.setMaxSize(3);
for (A a : polls) {
System.out.println("\thead:" + a);
}
System.out.println("剩余数据");
for (A a : fifo) {
System.out.println("\thead:" + a);
}
System.out.println(fifo.size());
}
}
interface FIFOT extends ListT, DequeT, Cloneable, java.io.Serializable {
/**
* 向最后添加一个新的，如果长度超过允许的最大值，则弹出一个 *
*/
T addLastSafe(T addLast);
/**
* 弹出head，如果Size = 0返回null。而不同于pop抛出异常
* @return
*/
T pollSafe();
/**
* 获得最大保存
*
* @return
*/
int getMaxSize();
/**
* 设置最大存储范围
*
* @return 返回的是，因为改变了队列大小，导致弹出的head
*/
ListT setMaxSize(int maxSize);
}
class FIFOImplT extends LinkedListT implements FIFOT {
private int maxSize = Integer.MAX_VALUE;
private final Object synObj = new Object();
public FIFOImpl() {
super();
}
public FIFOImpl(int maxSize) {
super();
this.maxSize = maxSize;
}
@Override
public T addLastSafe(T addLast) {
synchronized (synObj) {
T head = null;
while (size() = maxSize) {
head = poll();
}
addLast(addLast);
return head;
}
}
@Override
public T pollSafe() {
synchronized (synObj) {
return poll();
}
}
@Override
public ListT setMaxSize(int maxSize) {
ListT list = null;
if (maxSize this.maxSize) {
list = new ArrayListT();
synchronized (synObj) {
while (size() maxSize) {
list.add(poll());
}
}
}
this.maxSize = maxSize;
return list;
}
@Override
public int getMaxSize() {
return this.maxSize;
}
}
class A {
private String name;
public A() {
}
public A(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "A{" + "name=" + name + '}';
}
}
Q5: 急求！！！！用java 写一个 字符串去重 的程序！
可以利用SET里元素不重复的功能实现， 将字符串按照、分割成数组， 然后挨个放入SET中， 最后遍历SET 将里面每个元素组合成一个字符串 。
String s[] = “人、药物、疾病、药物、疾病、人、药物、” 按照、分割。
Set set = new HashSet();
遍历数组s[]
将数组每个元素放入set
遍历结束
定义字符串result=""
遍历set
result = result + "、" + set的该次遍历的元素
遍历结束， 得到结果result
关于java代码实现去重队列和java去重复代码的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
