散列，全散列

这是回复某一篇关于散列，完全散列的帖子写的代码。
再把问题描述一遍：
在两个很大的字符串数组中，求两个数组中共有的字符串

写一个o(m*n)的算法很容易
实际上引入hash，完全把复杂度降到o(m+n)

但是引入hash，需要注意hash冲突；当hashcode冲突时，需要在hash数组上纵向bucket；将重复hashcode存入到纵向bucket。
hash查询时，查询到某一bucket，再进行一次迭代查找hashcode

理想状态无冲突的复杂度为o(m+n)
假设平均冲突为常数k，则复杂度变为o(k(m+n))
实际情况下，当ary足够大，冲突会变得足够小，k可忽略不计。即o(k(m+n))=o(m+n)

下面是回复内容

mylazygirl 写道

leon_a 写道

算了，放代码，冲突是必须的，但当ary数组足够大，能有效避免冲突。

public class Main {

	public static void main(String[] args) {
		String[] strArr1 = { "xiaoxin", "niutou", "shanqiu", "luobo" };
		String[] strArr2 = { "xiaoxin", "ggg", "shanqiu", "meile", "dddsf", "niutou" };
		int max = strArr1.length > strArr2.length ? strArr1.length : strArr2.length;
		int[] ary = new int[max*4];
		for (int i = 0; i < strArr1.length; i++) {
			int hash = hash(strArr1[i].hashCode());
			int index = indexFor(hash,max*4);
			ary[index] = 1;
		}
		for (int i = 0; i < strArr2.length; i++) {
			int hash = hash(strArr2[i].hashCode());
			int index = indexFor(hash,max*4);
			if(ary[index] == 1){
				System.out.println(strArr2[i]);
			}
		}
	}

    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    static int indexFor(int h, int length) {
        return h & (length-1);
    }
}

这位兄弟的代码我没看懂，用hash我倒是明白，但hash()方法就不知道是做什么的了，打印了一下值，发现有重复，于是将输入换一下

String[] strArr1 = { "xiaoxin", "niutou", "shanqiu"};
		String[] strArr2 = { "ggg", "shanqiu", "meile", "dddsf", "niutou", "luobo"};

结果就错了，这个hash()方法莫不是随便做了做位操作而已，没什么意义？希望明白的人解答

那我就再放代码，无冲突版本

package test;

import java.util.Arrays;

public class Hash {

    public static void main(String[] args) {
        // String[] strArr1 = { "xiaoxin", "niutou", "shanqiu", "luobo" };
        // String[] strArr2 = { "xiaoxin", "ggg", "shanqiu", "meile", "dddsf", "niutou" };
        String[] strArr1 = { "xiaoxin", "niutou", "shanqiu" };
        String[] strArr2 = { "ggg", "shanqiu", "meile", "dddsf", "niutou", "luobo" };
        int max = strArr1.length > strArr2.length ? strArr1.length : strArr2.length;
        int[][] ary = new int[max * 4][];
        for (int i = 0; i < strArr1.length; i++) {
            int hash = hash(strArr1[i].hashCode());
            int index = indexFor(hash, max * 4);
            if (ary[index] == null) {
                ary[index] = new int[1];
            } else {
                ary[index] = Arrays.copyOf(ary[index], ary[index].length * 2);
            }
            for (int j = 0; j < ary[index].length; j++) {
                if (ary[index][j] == 0) {
                    ary[index][j] = hash;
                }
            }
        }
        for (int i = 0; i < strArr2.length; i++) {
            int hash = hash(strArr2[i].hashCode());
            int index = indexFor(hash, max * 4);
            if (ary[index] != null) {
                for (int j = 0; j < ary[index].length; j++) {
                    if (ary[index][j] == hash) {
                        System.out.println(strArr2[i]);
                    }
                }
            }
        }
    }

    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    static int indexFor(int h, int length) {
        return h & (length - 1);
    }
}