类架构
分离链接散列表的类结构
package cn.edut.hash;
import java.util.List;
public class SeparateChainingHashTable <T>{
/** * 构造 * 使用默认大小 */
public SeparateChainingHashTable() {
// TODO Auto-generated constructor stub
}
/** * 构造 * 设定大小， * @param size */
public SeparateChainingHashTable(int size) {
// TODO Auto-generated constructor stub
}
/** * 添加 元素 * @param e */
public void insert(T e) {
// TODO Auto-generated method stub
}
/** * 删除 元素 * @param e */
public void remove(T e) {
// TODO Auto-generated method stub
}
/** * 判断是否包含元素 * @return */
public boolean contains() {
// TODO Auto-generated method stub
return false ;
}
/** * 清空散列 */
public void makeEmpty() {
// TODO Auto-generated method stub
}
/** * 需要是一个素数 */
private static final int DEFAULT_TABLE_SIZE = 101 ;
/** * list里面放链表，根据hashcode判断放在哪个链表里面 */
private List<T>[] keyList ;
/** * 存量多少个数据 */
private int currentSize ;
/** * 扩容 */
private void rehash() {
// TODO Auto-generated method stub
}
/** * 计算元素hashcode * @return */
private int myhash(T e) {
// TODO Auto-generated method stub
return 0 ;
}
/** * 生产下一个素数 * 是否要静态？ */
private long nextPrime(int n) {
// TODO Auto-generated method stub
return 0 ;
}
/** * 判断素数 * 是否要静态？ */
private boolean isPrime(int n ) {
// TODO Auto-generated method stub
return false ;
}
}
上面架构的实现
package cn.edut.algorithm;
import static org.junit.Assume.assumeNotNull;
public class SeparateChainingHashTable<K , V> {
/** * 构造 使用默认大小 */
public SeparateChainingHashTable() {
this(DEFAULT_TABLE_SIZE);
}
/** * 构造 设定大小， * * @param size */
@SuppressWarnings("unchecked")
public SeparateChainingHashTable(int size) {
table = new Entry[size];
}
public int size() {
return size ;
}
/** * 删除 元素 * * @param e */
public void remove(K key) {
int hash = hash(key);
int index = indexFor(hash , table.length);
Entry<K, V> preEntry =null;
for(Entry<K, V> e=table[index] ; e!=null ; e=e.next) {
if((e.key.equals(key) || e.key == key) && hash==e.hash) {
if(preEntry!= null) {
preEntry.next = e.next ;
}else {
//只有一个节点
table[index] = null;
}
size--;
}
preEntry = e;
}
}
/** * 判断是否包含元素 * * @return */
public boolean contains(K key) {
Entry<K, V> entry = getEntry(key);
return entry!=null;
}
/** * 清空散列 */
public void makeEmpty() {
for (int i = 0; i < table.length; i++) {
Entry<K, V> t = table[i] ;
table[i] = null ;
while(t!=null) {
Entry<K, V> next = t.next ;
t.clear();
t = next ;
}
}
this.size = 0 ;
}
public V get(K key) {
Entry<K, V> entry = getEntry(key);
return entry!=null?entry.value : null ;
}
/* ---------------- Fields -------------- */
/** * 需要是一个素数 */
private static final int DEFAULT_TABLE_SIZE = 3;
/** * list里面放链表，根据hashcode判断放在哪个链表里面 */
private Entry<K, V>[] table;
/** * 存量多少个数据 */
private int size;
/** * 扩容 */
private void rehash() {
// TODO Auto-generated method stub
}
private Entry<K, V> getEntry(K key) {
int hash = key==null?0 : hash(key);
int index = indexFor(hash , table.length);
for(Entry<K, V> e=table[index] ; e!=null ; e= e.next) {
K k = e.key;
if(k==key || (k!=null && k.equals(key))) {
return e;
}
}
return null;
}
/** * 计算元素hashcode * * @return */
private int hash(K e) {
int h = e.hashCode() ;
h ^= (h >> 20 )^(h >>12) ;
return h^(h >> 8) ^ (h >> 4 );
}
private int indexFor(int h , int size) {
return h%size;
}
/** * 生产下一个素数 是否要静态？ */
private long nextPrime(long n) {
while(isPrime(++n)) {}
return n;
}
/** * 判断素数 是否要静态？ */
private boolean isPrime(long n) {
if (n < 2) {
return false;
} else if (n > 2) {
if(n%2==0) {
return false ;
}else {
long len = (long) Math.sqrt(n);
for(long i=3 ; i < len ;i++) {
if(n%i==0) {
return false;
}
}
}
}
return true;
}
private void addEntry(K key, V value, int hash, int index) {
if(size>=table.length/2 && table[index]!=null ) {
resize((int) nextPrime(table.length*2));
index= indexFor(hash, table.length);
}
Entry<K, V> entry = new Entry<>(table[index], hash, value, key);
table[index] = entry ;
size++;
}
private void resize(int newSize) {
Entry<K, V>[] oldTable = table;
Entry[] newTable = new Entry[newSize];
transfer(newTable);
table = newTable;
}
private void transfer(Entry[] newTable) {
for (Entry<K,V> e : table) {
while(e!=null) {
Entry<K, V> next = e.next;
int index = indexFor(e.hash , newTable.length);
e.next = newTable[index];
newTable[index] = e ;
e = next;
}
}
}
/** * 添加 元素 * * @param e */
public V insert(K key , V value) {
int hash = key==null?0:hash(key);
int index = indexFor(hash , table.length);
Entry<K, V> e = table[index];
//桶上有元素，覆盖
while (e!=null) {
if( e.hash == hash && (e.key==key || e.key.equals(key))) {
V oldValue = e.value ;
e.value = value ;
return oldValue ;
}
e = e.next ;
}
//添加节点
addEntry(key,value,hash,index);
return null;
}
private static class Entry<K,V> {
private Entry<K, V> next ;
private int hash ;
private V value ;
private K key ;
public Entry(Entry<K, V> next, int hash, V value, K key) {
super();
this.next = next;
this.hash = hash;
this.value = value;
this.key = key;
}
public void clear() {
next = null;
hash = 0 ;
value = null;
key = null;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[ ") ;
for (Entry<K, V> e : table) {
while (e!=null) {
sb.append(e.key) ;
sb.append(":");
sb.append(e.value);
sb.append(", ");
e = e.next ;
}
}
sb.delete(sb.length()-", ".length(), sb.length());
sb.append("]") ;
return sb.toString();
}
}
京公网安备 11010502036488号