布谷鸟 散列java实现

package com.algorithm.charactor1;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 布谷鸟算法
 * 原理是，使用多个 散列函数，通过计算放到 表 中，当其中一个散列函数计算到的对应位置为空，则放入，
 * 当都不为空就进行一层层替换，达到一定次数后还是插入不了，则进行扩容，或者重新散列
 */
public class Cuckoo {
	private String [] array ;//表
	private static final int DEFAULTSIZE = 7;
	private int  size ;
	private int reHash =0;
	private int tryCount = 33;
	
	List<HashAlgorithm>  hashAlgorithmList = new ArrayList<HashAlgorithm>();
	{//初始2个换散列函数。
		hashAlgorithmList.add(new HashAlgorithm(17));
		hashAlgorithmList.add(new HashAlgorithm(23));
	}

	void remove(String key){
		if (key == null) {
			return;
		}
		for (HashAlgorithm hashAlgorithm : hashAlgorithmList) {//遍历算法集合 计算index值，
			int hashCode = hashAlgorithm.hashCode(key);
			int index = getIndex(hashCode);
			if (array[index]!=null && array[index].equals(key)) {
				array[index] = null;
				size--;
			}
		}
	}
	
	void insert(String key){
		while(true){
			for (int i = 0; i < tryCount; i++) {
				
				for (HashAlgorithm hashAlgorithm : hashAlgorithmList) {//遍历算法集合 计算index值，
					int hashCode = hashAlgorithm.hashCode(key);
					int index = getIndex(hashCode);
					if (array[index] == null ) {
						array[index] = key;//当表中索引无值，将元素放到表中
						size++;
						return;
					}
				}
				
				//执行到这说明 算法集合计算的index全部有值 进行替换操作
				
				int hashAlgorithmListIndex = new Random().nextInt(hashAlgorithmList.size());//随机选取一个函数
				int hashCode = hashAlgorithmList.get(hashAlgorithmListIndex).hashCode(key);
				int index = getIndex(hashCode);
				
				String oldKey = array[index];//原本表中这个索引对应的值
				array[index] = key;//把要插入的值 放到当前索引上
				key = oldKey; //现在就是要插入原来替换掉的值
				
			}
			
			if (++reHash >1 || size>=array.length) {//说明要进行扩容操作了
				expandArray();
				reHash =0;
			}else {
				computeHash();//重新计算hash值
			}
		}
	}
	/**
	 * 更新 hash函数 重新计算
	 */
	private void computeHash() {
		hashAlgorithmList.clear();//清空原有的函数
		int one = new Random().nextInt(100);
		int two = new Random().nextInt(100);
		two = one == two ? two*2 : two;//只是两个不一样的值
		hashAlgorithmList.add(new HashAlgorithm(one));
		hashAlgorithmList.add(new HashAlgorithm(two));
		rehash(array.length);
	}
	
	private void expandArray() {
		rehash(nextPrime(array.length*2));
	}
	
	/**
	 * 重新计算所有的 hash 同时放到表中
	 * @param length
	 */
	private void rehash(int length) {
		String [] oldArray = array;
		array = new String[length];
		size = 0 ;
		for (String string : oldArray) {
			if (string != null) {
				insert(string);
			}
		}
	}
	
	public static void main(String[] args) {
		Cuckoo cuckoo = new Cuckoo();
		for (int i = 0; i < 8; i++) {
			cuckoo.insert("a"+new Random().nextInt(1000));
		}
		for (String string : cuckoo.array) {
			System.out.println(string);
		}
	}
	
	
	//素数计算，网上抄的
		public static Integer nextPrime(Integer begin) {
			int i;
			int j;
			for (i = begin;; i++) {
				boolean flag = true;
				for (j = 2; j <= i / 2; j++) {
					if (i % j == 0) {
						flag = false;
						break;
					} else if (i % j != 0) {
						continue;
					} else {
						break;
					}
				}
				if (flag) {
					return i;
				}
			}
		}
	/**
	 * 是否包含当前元素
	 * @param key
	 * @return
	 */
	Boolean cotains(String key){
		for (HashAlgorithm hashAlgorithm : hashAlgorithmList) {
			int hashCode = hashAlgorithm.hashCode(key);
			int index = getIndex(hashCode);
			if (array[index] !=null ) {
				return true;
			}
		}
		return false;
	}
	
	
	/**
	 * 获取hash值对应的表中索引
	 * @param hashCode
	 * @return
	 */
	int getIndex(int hashCode){
		 int index = hashCode % array.length;
		 index =  index < 0 ? index + array.length : index;
	   return index;
	}
	
	public Cuckoo() {
		this(DEFAULTSIZE);
	}
	
	
	public Cuckoo(int size) {
		array = new String[size];
	}

	
	
	public int getSize() {
		return size;
	}

	//定义散列函数集合
	class HashAlgorithm{
		
		private int initNumber;

		public HashAlgorithm(int initNumber) {
			super();
			this.initNumber = initNumber;
		}
		
		public int hashCode(String key){
			return (initNumber +key).hashCode();//传递进来的固定值 +key 模拟两个不同的 hashcode
		}
	}
}