布谷鸟散列的学习笔记1

短命女 2022-05-26 13:47 135阅读 0赞

布谷鸟散列接口:

public interface HashFamily<E> {
        int getNumOfFunctions();
    
        void generateNewFunctions();
    
        int hash(E e, int which);
    }

布谷鸟散列的类的框架

public class CuckooHashTable<E> {
        private static final float LOAD_FACTOR = 0.4f;
    
        private static final int ALLOWED_REHASHES = 1;
    
        private static final int DEFAULT_TABLE_SIZE = 101;
    
        private final HashFamily<? super E> hashFunctions;
    
        private final int numHashFunctions;
    
        private Object[] array;
    
        private int currentSize;
    
        public CuckooHashTable(HashFamily<? super E> hashFunctions) {
            this(hashFunctions, DEFAULT_TABLE_SIZE);
        }
    
        public CuckooHashTable(HashFamily<? super E> hashFunctions, int size) {
            allocateArray(nextPrime(size));
            currentSize = 0;
            this.hashFunctions = hashFunctions;
            numHashFunctions = hashFunctions.getNumOfFunctions();
        }
    
        private void allocateArray(int arraySize) {
            array = new Object[arraySize];
        }
    
        // 清空
        private void doClear() {
            currentSize = 0;
            for (int i = 0; i < array.length; i++)
                array[i] = null;
        }
    
        // 大小
        public int size() {
            return currentSize;
        }
    
        // 是否为空
        public boolean isEmpty() {
            return currentSize == 0;
        }
    
        public void clear() {
            doClear();
        }
    
        // 是否包含
        public boolean contains(E e) {
            return findPos(e) != -1;
        }
    
        /** * 布谷鸟散列的插入 * * @param e */
        public boolean add(E e) {
            if (contains(e))
                return false;
            if (currentSize >= array.length * LOAD_FACTOR)
                expand();
            return addHelper(e);
        }
    
        private int rehashes = 0;
    
        private Random r = new Random();
    
        private boolean addHelper(E e) {
            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(e, i);
                        if (array[pos] == null) {
                            array[pos] = e;
                            currentSize++;
                            return true;
                        }
                    }
                    int i = 0;
                    do {
                        pos = myHash(e, r.nextInt(numHashFunctions));
                    } while (pos == lastPos && i++ < 5);
                    E tmp = array(lastPos = pos);
                    array[pos] = e;
                    e = tmp;
                }
                if (++rehashes > ALLOWED_REHASHES) {
                    expand();
                    rehashes = 0;
                } else
                    rehash();
            }
        }
    
        // 扩展
        private void expand() {
            rehash((int) (array.length / LOAD_FACTOR));
        }
    
        // 再散列
        private void rehash() {
            hashFunctions.generateNewFunctions();
            rehash(array.length);
        }
    
        private void rehash(int newLength) {
            E[] oldArray = (E[]) array;
            allocateArray(nextPrime(newLength));
            currentSize = 0;
            for (E e : oldArray) {
                if (e != null)
                    add(e);
            }
        }
    
        private E array(int index) {
            return (E) array[index];
        }
    
        // 删除
        public boolean remove(E e) {
            int pos = findPos(e);
            if (pos != -1) {
                array[pos] = null;
                currentSize--;
            }
            return pos != -1;
        }
    
        // 在布谷列表中查找某项的位置
        private int findPos(E e) {
            for (int i = 0; i < numHashFunctions; i++) {
                int pos = myHash(e, i);
                if (array[pos] != null && array[pos].equals(e))
                    return pos;
            }
    
            return -1;
        }
    
        private int myHash(E e, int which) {
            int hashVal = hashFunctions.hash(e, which);
            hashVal %= array.length;
            if (hashVal < 0)
                hashVal += array.length;
            return hashVal;
        }
    
        @Override
        public String toString() {
            StringJoiner joiner = new StringJoiner(null);
            for (int i = 0; i < array.length; i++) {
                if (array[i] != null)
                    joiner.add((CharSequence) array[i]);
            }
            return joiner.toString();
        }
    
        private int nextPrime(int n) {
            if (n % 2 == 0)
                n++;
            while (!isPrime(n))
                n += 2;
            return n;
        }
    
        private boolean isPrime(int n) {
            if (n == 2 || n == 3)
                return true;
            if (n == 1 || n % 2 == 0)
                return false;
            for (int i = 3; i * i <= n; i += 2)
                if (n % i == 0)
                    return false;
            return true;
        }
    }