《数据结构与算法分析-java语言描述》 - （自制）散列表 - 分离链接法（separate chaining）

类架构

分离链接散列表的类结构

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();
	}

}