概念：
- 定義：
CuckooHash（布谷鳥散列）是為了解決哈希沖突問題而提出配深，利用較少的計算換取較大的空間兆蕉。
- 特點(diǎn)：
占用空間少昧穿，查詢速度快厕妖。 - 來源：
之所以起這個名字是因為布谷鳥生性貪婪第美，不自己筑巢蝶锋，而是在別的鳥巢里面鳥蛋孵化，先成長的幼鳥會將別的鳥蛋擠出什往，這樣獨(dú)享“母愛”扳缕，類似于哈希沖突處理過程。 - 算法描述:
使用hashA别威、hashB計算對應(yīng)的key位置：
1躯舔、兩個位置均為空，則任選一個插入省古；
2粥庄、兩個位置中一個為空，則插入到空的那個位置
3豺妓、兩個位置均不為空惜互，則踢出一個位置后插入，被踢出的對調(diào)用該算法琳拭，再執(zhí)行該算法找其另一個位置训堆，循環(huán)直到插入成功。
4臀栈、如果被踢出的次數(shù)達(dá)到一定的閾值蔫慧，則認(rèn)為hash表已滿，并進(jìn)行重新哈希rehash
轉(zhuǎn)自：http://www.blogs8.cn/posts/WyXIBP4
實現(xiàn)過程：
- 我們知道實現(xiàn)布谷鳥散列是需要一個散列函數(shù)的集合权薯。因此姑躲，我們要定義一個接口來獲取到這樣的一個集合睡扬。
public interface HashFamily <AnyType>{
//根據(jù)which來選擇散列函數(shù)，并返回hash值
int hash(AnyType x, int which);
//返回集合中散列函數(shù)的個數(shù)
int getNumberOfFunctions();
//獲取到新的散列函數(shù)
void generateNewFunctions();
}
- 定義變量：
//定義最大裝填因子為0.4
private static final double MAX_LOAD = 0.4;
//定義rehash次數(shù)達(dá)到一定時黍析，進(jìn)行
private static final int ALLOWED_REHASHES = 1;
//定義默認(rèn)表的大小
private static final int DEFAULT_TABLE_SIZE = 101;
//定義散列函數(shù)集合
private final HashFamily<? super AnyType> hashFunctions;
//定義散列函數(shù)個數(shù)
private final int numHashFunctions;
//定義當(dāng)前表
private AnyType[] array;
//定義當(dāng)前表的大小
private int currentSize;
//定義rehash的次數(shù)
private int rehashes = 0;
//定義一個隨機(jī)數(shù)
private Random r = new Random();
- 初始化操作：
public CuckooHashTable(HashFamily<? super AnyType> hf){
this(hf, DEFAULT_TABLE_SIZE);
}
//初始化操作
public CuckooHashTable(HashFamily<? super AnyType> hf, int size){
allocateArray(nextPrime(size));
doClear();
hashFunctions = hf;
numHashFunctions = hf.getNumberOfFunctions();
}
public void makeEmpty(){
doClear();
}
//清空操作
private void doClear(){
currentSize = 0;
for (int i = 0; i < array.length; i ++){
array[i] = null;
}
}
//初始化表
private void allocateArray(int arraySize){
array = (AnyType[]) new Object[arraySize];
}
- 定義hash函數(shù)：
/**
*
* @param x 當(dāng)前的元素
* @param which 選取的散列函數(shù)對應(yīng)的位置
* @return
*/
private int myHash(AnyType x, int which){
//調(diào)用散列函數(shù)集合中的hash方法獲取到hash值
int hashVal = hashFunctions.hash(x, which);
//再做一定的處理
hashVal %= array.length;
if (hashVal < 0){
hashVal += array.length;
}
return hashVal;
}
- 查詢元素是否存在：
/**
* 查詢元素的位置卖怜，若找到元素，則返回其當(dāng)前位置阐枣，否則返回-1
* @param x
* @return
*/
private int findPos(AnyType x){
//遍歷散列函數(shù)集合马靠，因為不確定元素所用的散列函數(shù)為哪個
for (int i = 0; i < numHashFunctions; i ++){
//獲取到當(dāng)前hash值
int pos = myHash(x, i);
//判斷表中是否存在當(dāng)前元素
if (array[pos] != null && array[pos].equals(x)){
return pos;
}
}
return -1;
}
public boolean contains(AnyType x){
return findPos(x) != -1;
}
- 刪除元素：
/**
* 刪除元素：先查詢表中是否存在該元素，若存在蔼两，則進(jìn)行刪除該元素
* @param x
* @return
*/
public boolean remove(AnyType x){
int pos = findPos(x);
if (pos != -1){
array[pos] = null;
currentSize --;
}
return pos != -1;
}
- 插入元素：
/**
* 插入：先判斷該元素是否存在甩鳄，若存在，在判斷表的大小是否達(dá)到最大負(fù)載额划，
* 若達(dá)到妙啃，則進(jìn)行擴(kuò)展，最后調(diào)用insertHelper方法進(jìn)行插入元素
* @param x
* @return
*/
public boolean insert(AnyType x){
if (contains(x)){
return false;
}
if (currentSize >= array.length * MAX_LOAD){
expand();
}
return insertHelper(x);
}
- 具體的插入過程：
* a. 先遍歷散列函數(shù)集合俊戳，找出元素所有的可存放的位置揖赴，若找到的位置為空，則放入即可抑胎，完成插入
* b. 若沒有找到空閑位置燥滑，隨機(jī)產(chǎn)生一個位置
* c. 將插入的元素替換隨機(jī)產(chǎn)生的位置，并將要插入的元素更新為被替換的元素
* d. 替換后阿逃，回到步驟a.
* e. 若超過查找次數(shù)铭拧，還是沒有找到空閑位置，那么根據(jù)rehash的次數(shù)盆昙，判斷是否需要進(jìn)行擴(kuò)展表羽历，若超過rehash的最大次數(shù)，則進(jìn)行擴(kuò)展表淡喜，否則進(jìn)行rehash操作秕磷，并更新散列函數(shù)集合
private boolean insertHelper(AnyType x) {
//記錄循環(huán)的最大次數(shù)
final int COUNT_LIMIT = 100;
while (true){
//記錄上一個元素位置
int lastPos = -1;
int pos;
//進(jìn)行查找插入
for (int count = 0; count < COUNT_LIMIT; count ++){
for (int i = 0; i < numHashFunctions; i ++){
pos = myHash(x, i);
//查找成功，直接返回
if (array[pos] == null){
array[pos] = x;
currentSize ++;
return true;
}
}
//查找失敗炼团，進(jìn)行替換操作澎嚣，產(chǎn)生隨機(jī)數(shù)位置，當(dāng)產(chǎn)生的位置不能與原來的位置相同
int i = 0;
do {
pos = myHash(x, r.nextInt(numHashFunctions));
} while (pos == lastPos && i ++ < 5);
//進(jìn)行替換操作
AnyType temp = array[lastPos = pos];
array[pos] = x;
x = temp;
}
//超過次數(shù)瘟芝，還是插入失敗易桃，則進(jìn)行擴(kuò)表或rehash操作
if (++ rehashes > ALLOWED_REHASHES){
expand();
rehashes = 0;
} else {
rehash();
}
}
}
- 擴(kuò)表和rehash操作：
private void expand(){
rehash((int) (array.length / MAX_LOAD));
}
private void rehash(){
hashFunctions.generateNewFunctions();
rehash(array.length);
}
private void rehash(int newLength){
AnyType [] oldArray = array;
allocateArray(nextPrime(newLength));
currentSize = 0;
for (AnyType str : oldArray){
if (str != null){
insert(str);
}
}
}
進(jìn)行測試：
public class CuckooHashTableTest {
//定義散列函數(shù)集合
private static HashFamily<String> hashFamily = new HashFamily<String>() {
//根據(jù)which選取不同的散列函數(shù)
@Override
public int hash(String x, int which) {
int hashVal = 0;
switch (which){
case 0:{
for (int i = 0; i < x.length(); i ++){
hashVal += x.charAt(i);
}
break;
}
case 1:
for (int i = 0; i < x.length(); i ++){
hashVal = 37 * hashVal + x.charAt(i);
}
break;
}
return hashVal;
}
//返回散列函數(shù)集合的個數(shù)
@Override
public int getNumberOfFunctions() {
return 2;
}
@Override
public void generateNewFunctions() {
}
};
public static void main(String[] args){
//定義布谷鳥散列
CuckooHashTable<String> cuckooHashTable = new CuckooHashTable<String>(hashFamily, 5);
String[] strs = {"abc","aba","abcc","abca"};
//插入
for (int i = 0; i < strs.length; i ++){
cuckooHashTable.insert(strs[i]);
}
//打印表
cuckooHashTable.printArray();
}
}
運(yùn)行結(jié)果：
當(dāng)前散列表如下：
表的大小為：13
current pos: 1 current value: abca
current pos: 3 current value: abcc
current pos: 6 current value: aba
current pos: 8 current value: abc
CuckooHashTable完整代碼：
public class CuckooHashTable<AnyType> {
public CuckooHashTable(HashFamily<? super AnyType> hf){
this(hf, DEFAULT_TABLE_SIZE);
}
//初始化操作
public CuckooHashTable(HashFamily<? super AnyType> hf, int size){
allocateArray(nextPrime(size));
doClear();
hashFunctions = hf;
numHashFunctions = hf.getNumberOfFunctions();
}
public void makeEmpty(){
doClear();
}
public boolean contains(AnyType x){
return findPos(x) != -1;
}
/**
*
* @param x 當(dāng)前的元素
* @param which 選取的散列函數(shù)對應(yīng)的位置
* @return
*/
private int myHash(AnyType x, int which){
//調(diào)用散列函數(shù)集合中的hash方法獲取到hash值
int hashVal = hashFunctions.hash(x, which);
//再做一定的處理
hashVal %= array.length;
if (hashVal < 0){
hashVal += array.length;
}
return hashVal;
}
/**
* 查詢元素的位置，若找到元素锌俱，則返回其當(dāng)前位置晤郑，否則返回-1
* @param x
* @return
*/
private int findPos(AnyType x){
//遍歷散列函數(shù)集合，因為不確定元素所用的散列函數(shù)為哪個
for (int i = 0; i < numHashFunctions; i ++){
//獲取到當(dāng)前hash值
int pos = myHash(x, i);
//判斷表中是否存在當(dāng)前元素
if (array[pos] != null && array[pos].equals(x)){
return pos;
}
}
return -1;
}
/**
* 刪除元素：先查詢表中是否存在該元素，若存在造寝，則進(jìn)行刪除該元素
* @param x
* @return
*/
public boolean remove(AnyType x){
int pos = findPos(x);
if (pos != -1){
array[pos] = null;
currentSize --;
}
return pos != -1;
}
/**
* 插入：先判斷該元素是否存在磕洪，若存在，在判斷表的大小是否達(dá)到最大負(fù)載诫龙，
* 若達(dá)到析显，則進(jìn)行擴(kuò)展，最后調(diào)用insertHelper方法進(jìn)行插入元素
* @param x
* @return
*/
public boolean insert(AnyType x){
if (contains(x)){
return false;
}
if (currentSize >= array.length * MAX_LOAD){
expand();
}
return insertHelper(x);
}
/**
* 具體的插入過程：
* a. 先遍歷散列函數(shù)集合签赃，找出元素所有的可存放的位置谷异，若找到的位置為空，則放入即可锦聊，完成插入
* b. 若沒有找到空閑位置歹嘹，隨機(jī)產(chǎn)生一個位置
* c. 將插入的元素替換隨機(jī)產(chǎn)生的位置，并將要插入的元素更新為被替換的元素
* d. 替換后括丁，回到步驟a.
* e. 若超過查找次數(shù)荞下，還是沒有找到空閑位置伶选，那么根據(jù)rehash的次數(shù)史飞，
* 判斷是否需要進(jìn)行擴(kuò)展表，若超過rehash的最大次數(shù)仰税，則進(jìn)行擴(kuò)展表构资，
* 否則進(jìn)行rehash操作，并更新散列函數(shù)集合
* @param x
* @return
*/
private boolean insertHelper(AnyType x) {
//記錄循環(huán)的最大次數(shù)
final int COUNT_LIMIT = 100;
while (true){
//記錄上一個元素位置
int lastPos = -1;
int pos;
//進(jìn)行查找插入
for (int count = 0; count < COUNT_LIMIT; count ++){
for (int i = 0; i < numHashFunctions; i ++){
pos = myHash(x, i);
//查找成功陨簇，直接返回
if (array[pos] == null){
array[pos] = x;
currentSize ++;
return true;
}
}
//查找失敗吐绵，進(jìn)行替換操作，產(chǎn)生隨機(jī)數(shù)位置河绽，當(dāng)產(chǎn)生的位置不能與原來的位置相同
int i = 0;
do {
pos = myHash(x, r.nextInt(numHashFunctions));
} while (pos == lastPos && i ++ < 5);
//進(jìn)行替換操作
AnyType temp = array[lastPos = pos];
array[pos] = x;
x = temp;
}
//超過次數(shù)己单，還是插入失敗，則進(jìn)行擴(kuò)表或rehash操作
if (++ rehashes > ALLOWED_REHASHES){
expand();
rehashes = 0;
} else {
rehash();
}
}
}
private void expand(){
rehash((int) (array.length / MAX_LOAD));
}
private void rehash(){
hashFunctions.generateNewFunctions();
rehash(array.length);
}
private void rehash(int newLength){
AnyType [] oldArray = array;
allocateArray(nextPrime(newLength));
currentSize = 0;
for (AnyType str : oldArray){
if (str != null){
insert(str);
}
}
}
//清空操作
private void doClear(){
currentSize = 0;
for (int i = 0; i < array.length; i ++){
array[i] = null;
}
}
//初始化表
private void allocateArray(int arraySize){
array = (AnyType[]) new Object[arraySize];
}
public void printArray(){
System.out.println("當(dāng)前散列表如下：");
System.out.println("表的大小為：" + array.length);
for (int i = 0; i < array.length; i ++){
if (array[i] != null)
System.out.println("current pos: " + i + " current value: " + array[i]);
}
}
//定義最大裝填因子為0.4
private static final double MAX_LOAD = 0.4;
//定義rehash次數(shù)達(dá)到一定時耙饰，進(jìn)行
private static final int ALLOWED_REHASHES = 1;
//定義默認(rèn)表的大小
private static final int DEFAULT_TABLE_SIZE = 101;
//定義散列函數(shù)集合
private final HashFamily<? super AnyType> hashFunctions;
//定義散列函數(shù)個數(shù)
private final int numHashFunctions;
//定義當(dāng)前表
private AnyType[] array;
//定義當(dāng)前表的大小
private int currentSize;
//定義rehash的次數(shù)
private int rehashes = 0;
//定義一個隨機(jī)數(shù)
private Random r = new Random();
//返回下一個素數(shù)
private static int nextPrime(int n){
while (!isPrime(n)){
n ++;
}
return n;
}
//判斷是否為素數(shù)
private static boolean isPrime(int n){
for (int i = 2; i <= Math.sqrt(n); i ++){
if (n % i == 0 && n != 2){
return false;
}
}
return true;
}
}
優(yōu)化（減少哈希碰撞）：
1纹笼、將一維改成多維，使用桶（bucket）的4路槽位（slot）苟跪；
2廷痘、一個key對應(yīng)多個value；
3件已、增加哈希函數(shù)笋额，從兩個增加到多個；
4篷扩、增加哈希表兄猩，類似于第一種；
