哈希表

哈希函数设定

student类 、equals类

public class Student {

	int grade;
	int cls;
	String firstName;
	String lastName;
	
	Student(int grade,int cls,String firstName,String lastName){
		this.grade=grade;
		this.cls=cls;
		this.firstName=firstName;
		this.lastName=lastName;
	}
	
	public int hashCode() {
		
		int B=31;
		int hash=0;
		hash=hash*B+grade;
		hash=hash*B+cls;
		hash=hash*B+firstName.toLowerCase().hashCode();
		hash=hash*B+lastName.toLowerCase().hashCode(); 
		
		return hash;
		
	}
	
	public boolean equals(Object o) { //Object可以覆盖
		
		if(this==o)
			return true;
		if(o==null)
			return false;
		if(getClass()!=o.getClass())
			return false;
		Student another = (Student)o;
		return this.grade==another.grade&&
				this.cls==another.cls&&
				this.firstName.toLowerCase().equals(another.firstName.toLowerCase())&&
				this.lastName.toLowerCase().equals(another.lastName.toLowerCase());
		
		
	}
	 
	
}
           

哈希冲突

自建哈希表

public class HashTable<K,V> {
	
	private TreeMap<K,V>[] hashtable;
	private int M;
	private int size;
	
	public HashTable(int M) {
		this.M=M;
		size=0;
		hashtable=new TreeMap[M];
		for(int i=0;i<M;i++)
			hashtable[i]=new TreeMap<>();
		
	}
	
	public HashTable() {
		this(97);
	}
	
	private int hash(K key) {
		return key.hashCode()&0x7fffffff)%M;
	}
	
	public int getSize() {
		return size;
	}
	
	public void add(K key,V value) {
		
		TreeMap<K,V> map=hashtable[hash(key)];
		if(map.containsKey(key))
			map.put(key,value);
		else {
			map.put(key,value);
			size++;
		}
	}
	
	public V remove(K key) {
		TreeMap<K,V> map=hashtable[hash(key)];
		V ret=null;
		if(map.containsKey(key)) {
			ret=map.remove(key);
			size--;
		}
		return ret;
			
	}
	
	public void set(K key,V value) {
		TreeMap<K,V> map=hashtable[hash(key)];
		if(!map.containsKey(key))
			throw new IllegalArgumentException("doesn't exist");
		
		map.put(key,value);
	}
	
	public boolean contains(K key) {
		return hashtable[hash(key)].containsKey(key);
	}
	
	public V get(K key) {
		return hashtable[hash(key)].get(key);
	}
}
           

哈希冲突