布谷鸟搜索算法

代码参考

之前看到hashmap的解决哈希冲突的方式是通过链表存储甚至说用红黑树存储值，而这个算法处理的方式稍有不同。是冲突的时候，直接把当前位置的踢出去，让它再去找新的位置，如果被踢出去的次数达到一定值猜猜说明表满了需要扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//定义散列函数集合
    private static HashFamily<String> hashFamily = new HashFamily<String>() {
        //根据which选取不同的散列函数
        @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;
        }
        //返回散列函数集合的个数
        @Override
        public int getNumberOfFunctions() {
            return 2;
        }

        @Override
        public void generateNewFunctions() {

        }
    };

    public static void main(String[] args){
        //定义布谷鸟散列
        CuckooHash<String> cuckooHashTable = new CuckooHash<String>(hashFamily, 5);
        String[] strs = {"abc","aba","abcc","abca"};
        //插入
        for (int i = 0; i < strs.length; i ++){
            cuckooHashTable.insert(strs[i]);
        }
        //打印表
        cuckooHashTable.printArray();
    }

直接从测试方法开始看流程，HashFamily是一系列接口，定义了一个对象可能使用了多个哈希方法用来定义自己在表中的位置。

从插入方法开始查看

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

插入方法先判断是否已经存在，再判断是否已经满表，最后执行插入，直接先看插入函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
	 * 具体的插入过程：
	 *  a.先遍历散列函数集合，找出元素所有的可存放的位置，若找到的位置为空，则放入即可，完成插入 
	 *  b.若没有找到空闲位置，随机产生一个位置 
	 *  c.将插入的元素替换随机产生的位置，并将要插入的元素更新为被替换的元素 
	 *  d.替换后，回到步骤a. 
	 *  e.若超过查找次数，还是没有找到空闲位置，那么根据rehash的次数， 判断是否需要进行扩展表，若超过rehash的最大次数，则进行扩展表，
	 * 否则进行rehash操作，并更新散列函数集合
	 * 
	 * @param x
	 * @return
	 */
	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是交替操作，每次扩容都按照一定比例，不会死循环

查看插入代码，循环最大次数定义为100，然后查找位置根据myhash进行位置查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
	 *
	 * @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;
	}

根据定义的hash方法进行找位置，如果找到位置就返回，如果所有的哈希方法都不能够找到位置，那就进行一个随机替换，先把当前的值插入，而被替换的值会去用自己的hash方法去找新的位置

比如被替换的值，可能刚开始是用hash 1方法找到了位置，但是被替换了，后来用了hash 2方法找到了位置

如果它没找到位置，就去占用别人的位置，让别人去找。一直循环，直到循环次数超过了限制，进行扩容或者rehash操作

以上就是关键代码部分

以下为完整代码的备份

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
import java.util.Random;

public class CuckooHash<AnyType> {
	interface HashFamily<AnyType> {
		// 根据which来选择散列函数，并返回hash值
		int hash(AnyType x, int which);

		// 返回集合中散列函数的个数
		int getNumberOfFunctions();

		// 获取到新的散列函数
		void generateNewFunctions();
	}

	public CuckooHash(HashFamily<? super AnyType> hf) {
		this(hf, DEFAULT_TABLE_SIZE);
	}

	// 初始化操作
	public CuckooHash(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
	 *            当前的元素
	 * @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;
	}

	/**
	 * 删除元素：先查询表中是否存在该元素，若存在，则进行删除该元素
	 * 
	 * @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操作，并更新散列函数集合
	 * 
	 * @param x
	 * @return
	 */
	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();
			}
		}
	}

	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("当前散列表如下：");
		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次数达到一定时，进行
	private static final int ALLOWED_REHASHES = 1;
	// 定义默认表的大小
	private static final int DEFAULT_TABLE_SIZE = 101;
	// 定义散列函数集合
	private final HashFamily<? super AnyType> hashFunctions;
	// 定义散列函数个数
	private final int numHashFunctions;
	// 定义当前表
	private AnyType[] array;
	// 定义当前表的大小
	private int currentSize;
	// 定义rehash的次数
	private int rehashes = 0;
	// 定义一个随机数
	private Random r = new Random();

	// 返回下一个素数
	private static int nextPrime(int n) {
		while (!isPrime(n)) {
			n++;
		}
		return n;
	}

	// 判断是否为素数
	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;
	}
	
	
	
	//////////////////////////////////////////////////////////
	//定义散列函数集合
    private static HashFamily<String> hashFamily = new HashFamily<String>() {
        //根据which选取不同的散列函数
        @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;
        }
        //返回散列函数集合的个数
        @Override
        public int getNumberOfFunctions() {
            return 2;
        }

        @Override
        public void generateNewFunctions() {

        }
    };

    public static void main(String[] args){
        //定义布谷鸟散列
        CuckooHash<String> cuckooHashTable = new CuckooHash<String>(hashFamily, 5);
        String[] strs = {"abc","aba","abcc","abca"};
        //插入
        for (int i = 0; i < strs.length; i ++){
            cuckooHashTable.insert(strs[i]);
        }
        //打印表
        cuckooHashTable.printArray();
    }


}