SeparateChainingHashST
賈小強
转载请注明原创出处，谢谢！
package com.lab1.test3;
import java.util.LinkedList;
import java.util.Queue;
public class SeparateChainingHashST {
private static final int INIT_CAPACITY = 4;
private int n;
private int m;
private SequentailSearchST[] st;
public SeparateChainingHashST() {
this(INIT_CAPACITY);
}public SeparateChainingHashST(int m) {
this.m = m;
st = new SequentailSearchST[m];
for (int i = 0;
i < m;
i++) {
st[i] = new SequentailSearchST<>();
}
}private void resize(int capacity) {
SeparateChainingHashST temp = new SeparateChainingHashST<>(capacity);
for (int i = 0;
i < m;
i++) {
for (Key key : st[i].keys()) {
temp.put(key, st[i].get(key));
}
}
this.m = temp.m;
this.st = temp.st;
}private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % m;
}private void delete(Key key) {
int i = hash(key);
if (st[i].contains(key)) {
n--;
}
st[i].delete(key);
if (n <= m * 2) {
resize(m / 2);
}
}private Iterable keys() {
Queue queue = new LinkedList<>();
for (int i = 0;
i < m;
i++) {
for (Key key : st[i].keys()) {
queue.add(key);
}
}
return queue;
}private Value get(Key key) {
int i = hash(key);
return st[i].get(key);
}private boolean contains(Key key) {
return get(key) != null;
}private boolean isEmpty() {
return n == 0;
}private int size() {
return n;
}private void put(Key key, Value value) {
if (n >= m * 10) {
resize(m * 2);
}
int i = hash(key);
if (!st[i].contains(key)) {
n++;
}
st[i].put(key, value);
}public static void main(String[] args) {
SeparateChainingHashST st = new SeparateChainingHashST<>();
String test = "S E A R C H E X A M P L E";
String[] keys = test.split(" ");
for (int i = 0;
i < keys.length;
i++) {
st.put(keys[i], i);
}
System.out.println("size= " + st.size());
System.out.println("isEmpty= " + st.isEmpty());
System.out.println("contains= " + st.contains("S"));
st.delete("S");
System.out.println("contains= " + st.contains("S"));
for (String key : st.keys()) {
System.out.println(key + " " + st.get(key));
}
}
}
输出
size= 10
isEmpty= false
contains= true
contains= false
L 11
P 10
X 7
H 5
M 9
A 8
E 12
R 3
C 4
【SeparateChainingHashST】Happy learning !!
