java 散列算法计算重复数据

package com.lance.algorithm.算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Sanlie {

private static Sanlie instance = new Sanlie();

private Sanlie() {
};

public static Sanlie getInstance() {
return instance;
}

public static void main(String[] args) {

Sanlie instance = Sanlie.getInstance();

String[] str1 = new String[] { "11", "3", "3", "3" };
String[] str2 = new String[] { "3" };

List<Result> result = instance.doSanlie(str1, str2);

// List<Result> result = instance.doSanlie(str1);

for (Result resultValue : result) {
System.out.println(resultValue.getIndex() + " "
+ resultValue.getValue());
}
}

/**
* 获取两个数组中相同的字符
*
* @param str1
*            str1
* @param str2
*            str2
* @return List<String>
*/
public List<Result> doSanlie(String[] str1, String[] str2) {
List<Result> result = new ArrayList<Result>();
int max = str1.length > str2.length ? str1.length : str2.length;
int min = str1.length < str2.length ? str1.length : str2.length;

int[][] cache = new int[max * min][];

for (String str1Value : str1) {
int hash = hash(str1Value.hashCode());
int index = index(hash, max * min);

if (cache[index] == null) {
cache[index] = new int[1];
} else {
cache[index] = Arrays.copyOf(cache[index],
cache[index].length + 1);
}

for (int j = 0; j < cache[index].length; j++) {
if (cache[index][j] == 0) {
cache[index][j] = hash;
break;
}
}
}

for (int i = 0; i < str2.length; i++) {
int hash = instance.hash(str2[i].hashCode());
int index = instance.index(hash, max * min);
if (cache[index] != null) {
for (int j = 0; j < cache[index].length; j++) {
if (cache[index][j] == hash) {
Result repReault = new Result();
repReault.setIndex(i + 1);
repReault.setValue(str2[i]);
result.add(repReault);
break;
}
}
}
}
return result;
}

/**
* 查找数组中重复的字符
*
* @param str1
* @return
*/
private List<Result> doSanlie(String[] str1) {
List<Result> result = new ArrayList<Result>();
int max = str1.length;

int[][] cache = new int[max * max][];

for (int i = 0; i < str1.length; i++) {
int hash = hash(str1[i].hashCode());
int index = index(hash, max * max);

if (cache[index] == null) {
cache[index] = new int[1];
} else {
cache[index] = Arrays.copyOf(cache[index],
cache[index].length + 1);
}

for (int j = 0; j < cache[index].length; j++) {
if (cache[index][j] == 0) {
cache[index][j] = hash;
break;
} else if (cache[index][j] == hash) {
Result repReault = new Result();
repReault.setIndex(i + 1);
repReault.setValue(str1[i]);
result.add(repReault);
break;
}
}
}
return result;
}

/**
* 这个地方是重点
*
* @param hashCode
*            hashCode
* @return
*/
private int hash(int hashCode) {
hashCode ^= (hashCode >>> 20) ^ (hashCode >>> 12);
return hashCode ^ (hashCode >>> 7) ^ (hashCode >>> 4);
}

private int index(int hash, int length) {
return hash & (length - 1);
}

class Result {
private int index;
private String value;

public int getIndex() {
return index;
}

public void setIndex(int index) {
this.index = index;
}

public String getValue() {
return value;
}

public void setValue(String value) {
this.value = value;
}

}

}