添加、查找
删除
- 惰性删除
HashEntry 引用数组的每一项是下列3钟情形之一：
- null。
- 非null。且该项是活动的（isActive 为 true）。
- 非null。且该标记已经被删除（isActive 为 false）。
代码
package cn.edut.algorithm;
import java.util.Currency;
import com.sun.webkit.ContextMenu.ShowContext;
public class QuadraticProbingHashTable<K,V> {
public QuadraticProbingHashTable() {
this(DEFAULT_TABLE_SIZE) ;
}
public QuadraticProbingHashTable(int tableSize) {
allocateTable(tableSize);
makeEmpty();
}
public void makeEmpty() {
size = 0 ;
for (int i = 0; i < table.length; i++) {
table[i] = null;
}
}
public boolean containsKey(K key ) {
int index = findIndex(key);
return isActive(index);
}
public void put(K key , V value ) {
if(size>=table.length/2) {
rehash((int) nextPrime(table.length*2));
}
int index = findIndex(key);
table[index] = new HashEntry<K, V>(hash(key), key, value, true) ;
size++ ;
}
private void rehash(int newSize) {
HashEntry<K, V>[] oldTable = table;
allocateTable(newSize);
size=0 ;
for (int i = 0; i < oldTable.length; i++) {
HashEntry<K, V> e = oldTable[i];
if(e!=null) {
put(e.key,e.value);
}
}
}
public int findIndex(K key ) {
int hash = hash(key);
int index = indexFor(hash);
int offset = 1 ;
while(isActive(index)) {
if(table[index].key.equals(key)) {
return index ;
}
index += offset ;
offset += 2; //
if(index>=table.length) {
index-=table.length;
}
}
return index ;
}
public void remove(K key) {
int index = findIndex(key);
table[index].isActive = false;
}
public void showTable() {
System.out.print("[");
for (int i = 0; i < table.length; i++) {
HashEntry<K, V> t = table[i] ;
if(isActive(i)) {
System.out.print(" "+t.key +":"+t.value+" ");
}else {
System.out.print( " ---- " );
}
}
System.out.println("]");
}
public int size() {
return size ;
}
private static final int DEFAULT_TABLE_SIZE = 11 ; //必须要是素数
private HashEntry<K, V>[] table ; //The array of elements ;
private int size ; //当前数据量
/** * 节点 */
private static class HashEntry<K,V> {
private int hash ;
private K key ;
private V value ;
private boolean isActive =false ;
public HashEntry(int hash, K key, V value, boolean isActive) {
super();
this.hash = hash;
this.key = key;
this.value = value;
this.isActive = isActive;
}
}
public int indexFor(int hash ) {
return hash % table.length ;
}
public int hash(K key) {
int h = key.hashCode();
return h^(h>>>4)^(h>>>7)^(h>>>12)^(h>>>20);
}
public long nextPrime(long n) {
if(n<2) return 2;
while(!isPrime(++n)) {
}
return n;
}
/** * 方法2 ： 位运算，快一点点 */
public boolean isPrime(long n) {
if(n<2) {
return false;
}else if(n>2) {
if(((n^0)&1) == 0) { //偶数
return false;
}
long len = (long) Math.sqrt(n);
for (int i = 3; i <= len; i++) {
if(n%i==0 ) {
return false;
}
}
}
return true;
}
@SuppressWarnings("unchecked")
private void allocateTable(int tableSize) {
table = new HashEntry[tableSize] ;
}
private void rehash() {
//TODO
}
private boolean isActive(int index) {
return table[index]!=null && table[index].isActive;
}
public static void main(String[] args) {
QuadraticProbingHashTable<Integer, Integer> map= new QuadraticProbingHashTable<>();
for (int i = 0; i < 100; i++) {
System.out.println(i+" : "+map.isPrime(i) + " : "+ map.nextPrime(i));
}
int key = 10101;
int hash = map.hash(key);
int index = map.indexFor(hash);
System.out.println("key:"+key + ", hash:"+ hash + ", index:"+index);
/* * show */
map.showTable();
map.put(key, 33 );
map.put(key, 66 );
map.put(key-11, 44 );
map.put(key-12, 55 );
map.showTable();
System.out.println(map.containsKey(key));
map.remove(key);
System.out.println(map.containsKey(key));
map.showTable();
System.out.println("---------------");
for (int i = 0; i < 10; i++) {
map.put(key+i, i);
map.showTable();
}
}
}
测试结果
0 : false : 2
1 : false : 2
2 : true : 3
3 : true : 5
4 : false : 5
5 : true : 7
6 : false : 7
7 : true : 11
8 : false : 11
9 : false : 11
10 : false : 11
11 : true : 13
12 : false : 13
13 : true : 17
14 : false : 17
15 : false : 17
16 : false : 17
17 : true : 19
18 : false : 19
19 : true : 23
20 : false : 23
21 : false : 23
22 : false : 23
23 : true : 29
24 : false : 29
25 : false : 29
26 : false : 29
27 : false : 29
28 : false : 29
29 : true : 31
30 : false : 31
31 : true : 37
32 : false : 37
33 : false : 37
34 : false : 37
35 : false : 37
36 : false : 37
37 : true : 41
38 : false : 41
39 : false : 41
40 : false : 41
41 : true : 43
42 : false : 43
43 : true : 47
44 : false : 47
45 : false : 47
46 : false : 47
47 : true : 53
48 : false : 53
49 : false : 53
50 : false : 53
51 : false : 53
52 : false : 53
53 : true : 59
54 : false : 59
55 : false : 59
56 : false : 59
57 : false : 59
58 : false : 59
59 : true : 61
60 : false : 61
61 : true : 67
62 : false : 67
63 : false : 67
64 : false : 67
65 : false : 67
66 : false : 67
67 : true : 71
68 : false : 71
69 : false : 71
70 : false : 71
71 : true : 73
72 : false : 73
73 : true : 79
74 : false : 79
75 : false : 79
76 : false : 79
77 : false : 79
78 : false : 79
79 : true : 83
80 : false : 83
81 : false : 83
82 : false : 83
83 : true : 89
84 : false : 89
85 : false : 89
86 : false : 89
87 : false : 89
88 : false : 89
89 : true : 97
90 : false : 97
91 : false : 97
92 : false : 97
93 : false : 97
94 : false : 97
95 : false : 97
96 : false : 97
97 : true : 101
98 : false : 101
99 : false : 101
key:10101, hash:9550, index:2
[ ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ]
[ ---- ---- 10101:66 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- ]
true
false
[ ---- ---- ---- ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- ]
《---------------
[ ---- ---- 10101:0 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- ]
[ ---- ---- ---- ---- 10102:1 10101:0 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ]
[ ---- ---- ---- 10103:2 10102:1 10101:0 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ]
[ ---- ---- ---- 10103:2 10102:1 10101:0 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- ---- ---- ---- 10104:3 ---- ---- ---- ---- ---- ]
[ ---- ---- ---- 10103:2 10102:1 10101:0 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- ---- ---- 10105:4 10104:3 ---- ---- ---- ---- ---- ]
[ ---- ---- ---- 10103:2 10102:1 10101:0 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- ---- 10106:5 10105:4 10104:3 ---- ---- ---- ---- ---- ]
[ ---- ---- ---- 10103:2 10102:1 10101:0 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- 10107:6 10106:5 10105:4 10104:3 ---- ---- ---- ---- ---- ]
[ ---- ---- ---- 10103:2 10102:1 10101:0 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- 10107:6 10106:5 10105:4 10104:3 ---- ---- ---- 10108:7 ---- ]
[ ---- ---- ---- 10103:2 10102:1 10101:0 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- 10107:6 10106:5 10105:4 10104:3 ---- ---- 10109:8 10108:7 ---- ]
[ 10110:9 10109:8 10108:7 ---- ---- ---- ---- 10103:2 10102:1 10101:0 ---- 10090:44 ---- ---- 10089:55 ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- ---- 10107:6 10106:5 10105:4 10104:3 ---- ]
京公网安备 11010502036488号