カッコウハッシュJava実装

Cuckoo Hashing Java Implementation

package com.algorithm.charactor1 import java.util.ArrayList import java.util.List import java.util.Random /** * Cuckoo Algorithm * The principle is to use multiple hash functions and put them in the table through calculation. When the corresponding position calculated by one of the hash functions is empty, put it in, * When it is not empty, perform layer-by-layer replacement. After reaching a certain number of times, it still cannot be inserted, then expand or re-hash */ public class Cuckoo { private String [] array //table private static final int DEFAULTSIZE = 7 private int size private int reHash =0 private int tryCount = 33 List hashAlgorithmList = new ArrayList() {//Initial 2 exchange hash functions. hashAlgorithmList.add(new HashAlgorithm(17)) hashAlgorithmList.add(new HashAlgorithm(23)) } void remove(String key){ if (key == null) { return } for (HashAlgorithm hashAlgorithm: hashAlgorithmList) {//Traverse the algorithm set to calculate the index value, 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 1 || size>=array.length) {//Explain that it is time to expand expandArray() reHash =0 }else { computeHash()//Recalculate the hash value } } } /** * Update hash function and recalculate */ private void computeHash() { hashAlgorithmList.clear()//Clear the original function int one = new Random().nextInt(100) int two = new Random().nextInt(100) two = one == two? two*2: two//Just two different values hashAlgorithmList.add(new HashAlgorithm(one)) hashAlgorithmList.add(new HashAlgorithm(two)) rehash(array.length) } private void expandArray() { rehash(nextPrime(array.length*2)) } /** * Recalculate all hashes and put them in the table at the same time * @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) } } //Prime number calculation, copied online 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 } } } /** * Whether to include the current element * @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 } /** * Get the index in the table corresponding to the hash value * @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 } //Define a set of hash functions class HashAlgorithm{ private int initNumber public HashAlgorithm(int initNumber) { super() this.initNumber = initNumber } public int hashCode(String key){ return (initNumber +key).hashCode()//The fixed value +key passed in simulates two different hashcodes } } }