一道算法面试题

用一个长度为2147483637的bit数组，数据量很小吧。

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
我试了。Eclipse堆设的512M。还是不行，看来还是只有用hash的方法了

提供一个新的思路：
数据库里开两张表，然后用SQL解决

这么长时间终于发现了.标准作法.

呵呵，，白猫黑猫，抓到老鼠的就是好猫

不知道，请指点！！

对于1000w这样的大数组，选择一个较好的Hash算法难度挺大，可以尝试使用Hash链表来做这件事情，将1000w的数据进行hash，比方说%16，这样就有0到15为索引的链表的数组
0--15，然后在每一个链表分别使用不同的hash算法求得它们建立hash之后的数值为key，value为出现的次数，<key,value>,在java中也就是HashMap,显然，等到遍历第二个数组的时候，出现value的值为2，则立刻将该数据输出到屏幕即可。

其实，这种大数据的，完全可以使用Hadoop来处理，当然得有多台机器，Hadoop的MapReduce框架非常适合处理这种问题。
只需使用它们例子的中wordcount来处理存储这两个数据的文件即可。(注意需要将数据转化成String存储才行)

最后，如果你只有一个很菜的机器，比方说1G内存，也没有关系，前面第一种方法hash%m之后，存成m个小文件，然后你就会了吧.这种问题就是效率太低了，频繁的文件IO。

最后，如果这个问题，你经过和面试官的讨论，说可以容忍一定的误差，是不是可以使使用BloomFilter来做这件事情呢？

面试没有标准答案，你发散一下思维就可以了。

关键词: 连接。

连接算法多种多样，从最sb的嵌套循环连接，到基于索引的连接，归并连接，散列连接，每一种都有他的适用场景。

package Test;

import java.util.ArrayList;
import java.util.HashSet;

public class Find {

	// 用于存储hash后的数组长度
	private static int num = 1 << 24;

	// 用hashMap的算法
	public static int hash(Object obj) {
		int hash = obj.hashCode();
		hash += ~(hash << 9);
		hash ^= (hash >>> 14);
		hash += (hash << 4);
		hash ^= (hash >>> 10);
		hash = hash & (num - 1);
		return hash;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		HashSet intersection = new HashSet();

		// 准备要比较的数组个数
		int seed = 10000000;
		int[] s = new int[seed];
		int[] s2 = new int[seed];
		int[] hash = new int[num + 1];
		for (int k = 0; k < seed; k++) {
			s[k] = (int) Math.round(Math.random() * seed);
		}
		for (int k = 0; k < seed; k++) {
			s2[k] = (int) Math.round(Math.random() * seed);
		}

		System.out.println("start....");
		long start3 = System.nanoTime();
		int size = 0;
		// hash方法 简单一点线性探测解决冲突问题
		for (int k = 0; k < seed; k++) {
			int index = hash(s[k]);
			int step = 0;
			while (hash[index] != 0) {
				index = index + 1;
				++step;
				if (index < num && hash[index] == 0) {
					hash[index] = s[k];
					break;
				} else if (index > num) {
					step = 0;
					index = 0;
				}
			}
			if (hash[index] == 0) {
				hash[index] = s[k];
			}
		}
		System.out.println("check...");
		// 检测
		for (int k = 0; k < seed; k++) {
			int index = hash(s2[k]);
			int step = 0;
			while (true) {
				if (index < num) {
					if (hash[index] == 0)
						break;
					if (hash[index] == s2[k]) {
						intersection.add(s2[k]);// 数量级为1000w时不能用hashset了，会out, 改用整数size计数
						size++;
						break;
					}
				} else if (index > num) {
					step = 0;
					index = 0;
				}
				index = index + 1;
				++step;
			}
		}

		long end3 = System.nanoTime();
		System.out.println("hash求合集方法用时:" + (end3 - start3)/1000 + "微秒");
		System.out.println("合集个数" + intersection.size());
		// System.out.println("合集个数" + size);

		// 加入arraylist后再比较
		intersection.clear();
		long start2 = System.nanoTime();
		ArrayList<Integer> list1 = new ArrayList<Integer>();
		for (int i = 0; i < seed; i++) {
			list1.add(s[i]);
		}
		for (int i = 0; i < seed; i++) {
			if (list1.contains(s2[i])) {
				intersection.add(s2[i]);
			}
		}
		long end2 = System.nanoTime();
		System.out.println("arryList求合集用时:" + (end2 - start2) / 1000 + "微秒");
		System.out.println("合集个数" + intersection.size());

		// 双循环数组比较
		intersection.clear();
		long start = System.nanoTime();
		for (int i = 0; i < s.length; i++) {
			for (int k = 0; k < s2.length; k++) {
				if (s[i] == s2[k]) {
					intersection.add(s2[k]);
					break;
				}
			}
		}
		long end = System.nanoTime();
		System.out.println("数组循环比较用时:" + (end - start) / 1000 + "微秒");
		System.out.println("合集个数" + intersection.size());

	}

/*
* 数量级为100时 num=2^8 seed=100 装载因子:0.39
* hash求合集方法用时:1358微秒 合集个数42
* arryList求合集用时:825微秒 合集个数42
* 数组循环比较用时:267微秒 合集个数42
*
*
* 数量级为1000时 num=2^11 seed=1000 装载因子:0.49
* hash求合集方法用时:5304微秒 合集个数400
* arryList求合集用时:9761微秒 合集个数400
* 数组循环比较用时:12741微秒 合集个数400
*
* 数量级为1w时 num=2^14 seed=10000 装载因子:0.61
* hash求合集方法用时:29544微秒 合集个数3937
* arryList求合集用时:735891微秒 合集个数3937
* 数组循环比较用时:446530微秒 合集个数3937
*
* 数量级为10w时 num=2^17 seed=100000 装载因子:0.76
* hash求合集方法用时:236525微秒 合集个数39893
* arryList求合集用时:1550918微秒 合集个数39893
* 数组循环比较用时:40506392微秒 合集个数39893
*
* 下面的级别的arraylist 双循环我就没耐心等了，不知道要十几分钟或更长或直接out
* 数量级为50w时 num=2^19 seed=500000
* 装载因子:0.95
* hash求合集方法用时:8.682693秒 合集个数316863
*
* 数量级为100w时 num=2^20 seed=1000000 装载因子:0.95
* hash求合集方法用时:21.539328秒
* 合集个数631746
*
* 数量级为100w时 num=2^21 seed=1000000 装载因子:0.48
* hash求合集方法用时:2.796136秒
* 合集个数399163
*
* 数量级为1000w时 num=2^24 seed=10000000 装载因子:0.60
* intersection.add(s2[k]);去掉,换成整数累加
*  hash求合集方法用时:4.282秒 合集个数6321063
*
*/