CuckooHash（布谷鸟散列）

概念

CuckooHash（布谷鸟散列），最早于2001 年由Rasmus Pagh 和Flemming Friche Rodler 提出。是为了解决哈希冲突问题，利用较少的计算换取较大的空间。
wikipedia - Cuckoo hashing
特点：占用空间少，查询速度快。
来源：之所以起这个名字是因为布谷鸟生性贪婪，不自己筑巢，而是在别的鸟巢里面鸟蛋孵化，先成长的幼鸟会将别的鸟蛋挤出，这样独享“母爱”，类似于哈希冲突处理过程。

算法描述

算法步骤

分别使用hashA、hashB计算对应的key位置：
1. 两个位置均为空，则任选一个插入；
2. 两个位置中一个为空，则插入到空的那个位置
3. 两个位置均不为空，则随机踢出一个位置上的keyx，被踢出的keyx再执行该算法找其另一个位置，循环直到插入成功。
4. 如果被踢出的次数达到一定的阈值，则认为hash表已满，并进行重新哈希rehash

其他

1. Cockoo hash 有两种变形。一种通过增加哈希函数进一步提高空间利用率；另一种是增加哈希表，每个哈希函数对应一个哈希表，每次选择多个张表中空余位置进行放置。三个哈希表可以达到80% 的空间利用率。
2. Cockoo hash 的过程可能因为反复踢出无限循环下去，这时候就需要进行一次循环踢出的限制，超过限制则认为需要添加新的哈希函数。
3. Cockoo hash 的应用，Cuckoo Filter。CUCKOO FILTER：设计与实现

算法实现

我们知道实现布谷鸟散列是需要一个散列函数的集合。因此，我们要定义一个接口来获取到这样的一个集合。

public interface HashFamily <AnyType>{//根据which来选择散列函数，并返回hash值int hash(AnyType x, int which);//返回集合中散列函数的个数int getNumberOfFunctions();//获取到新的散列函数void generateNewFunctions();
}

定义变量：

    //定义最大装填因子为0.4private static final double MAX_LOAD = 0.4;//定义rehash次数达到一定时，进行private static final int ALLOWED_REHASHES = 1;//定义默认表的大小private static final int DEFAULT_TABLE_SIZE = 101;//定义散列函数集合private final HashFamilysuper AnyType> hashFunctions;//定义散列函数个数private final int numHashFunctions;//定义当前表private AnyType[] array;//定义当前表的大小private int currentSize;//定义rehash的次数private int rehashes = 0;//定义一个随机数private Random r = new Random();

初始化操作：

    public CuckooHashTable(HashFamilysuper AnyType> hf){this(hf, DEFAULT_TABLE_SIZE);}//初始化操作public CuckooHashTable(HashFamilysuper 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函数：

    /**** @param x 当前的元素* @param which 选取的散列函数对应的位置* @return*/private int myHash(AnyType x, int which){//调用散列函数集合中的hash方法获取到hash值int hashVal = hashFunctions.hash(x, which);//再做一定的处理hashVal %= array.length;if (hashVal < 0){hashVal += array.length;}return hashVal;}

查询元素是否存在：

    /*** 查询元素的位置，若找到元素，则返回其当前位置，否则返回-1* @param x* @return*/private int findPos(AnyType x){//遍历散列函数集合，因为不确定元素所用的散列函数为哪个for (int i = 0; i < numHashFunctions; i ++){//获取到当前hash值int pos = myHash(x, i);//判断表中是否存在当前元素if (array[pos] != null && array[pos].equals(x)){return pos;}}return -1;}
public boolean contains(AnyType x){return findPos(x) != -1;}

删除元素：

    /*** 删除元素：先查询表中是否存在该元素，若存在，则进行删除该元素* @param x* @return*/public boolean remove(AnyType x){int pos = findPos(x);if (pos != -1){array[pos] = null;currentSize --;}return pos != -1;}

插入元素：

    /*** 插入：先判断该元素是否存在，若存在，在判断表的大小是否达到最大负载，* 若达到，则进行扩展，最后调用insertHelper方法进行插入元素* @param x* @return*/public boolean insert(AnyType x){if (contains(x)){return false;}if (currentSize >= array.length * MAX_LOAD){expand();}return insertHelper(x);}

具体的插入过程：

• a. 先遍历散列函数集合，找出元素所有的可存放的位置，若找到的位置为空，则放入即可，完成插入
• b. 若没有找到空闲位置，随机产生一个位置
• c. 将插入的元素替换随机产生的位置，并将要插入的元素更新为被替换的元素
• d. 替换后，回到步骤a.
• e. 若超过查找次数，还是没有找到空闲位置，那么根据rehash的次数，判断是否需要进行扩展表，若超过rehash的最大次数，则进行扩展表，否则进行rehash操作，并更新散列函数集合

    private boolean insertHelper(AnyType x) {//记录循环的最大次数final int COUNT_LIMIT = 100;while (true){//记录上一个元素位置int lastPos = -1;int pos;//进行查找插入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;}}//查找失败，进行替换操作，产生随机数位置，当产生的位置不能与原来的位置相同int i = 0;do {pos = myHash(x, r.nextInt(numHashFunctions));} while (pos == lastPos && i ++ < 5);//进行替换操作AnyType temp = array[lastPos = pos];array[pos] = x;x = temp;}//超过次数，还是插入失败，则进行扩表或rehash操作if (++ rehashes > ALLOWED_REHASHES){expand();rehashes = 0;} else {rehash();}}}

扩表和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);}}}

进行测试：

public class CuckooHashTableTest {//定义散列函数集合private static HashFamily hashFamily = new HashFamily() {//根据which选取不同的散列函数@Overridepublic 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;}//返回散列函数集合的个数@Overridepublic int getNumberOfFunctions() {return 2;}@Overridepublic void generateNewFunctions() {}};public static void main(String[] args){//定义布谷鸟散列CuckooHashTable cuckooHashTable = new CuckooHashTable(hashFamily, 5);String[] strs = {"abc","aba","abcc","abca"};//插入for (int i = 0; i < strs.length; i ++){cuckooHashTable.insert(strs[i]);}//打印表cuckooHashTable.printArray();}
}

运行结果：

当前散列表如下：
表的大小为：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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！