java——哈希表 HashTable

在一个类中重写hashCode()和equals()

package Date_pacage.hash;

public class Student {
private int grade;
    private 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;
    }
    
    //如果没有覆盖这个方法，java会自动给Student这个类的每个对象分配一个hashCode，
    //这个自动分配的hashCode是根据对象的地址来分配的
    @Override
    public int hashCode() {
        
        int B = 31;
        
        int hash = 0;
        hash = hash * B + grade;
        hash = hash * B + cls;
        //字符串不区分大小写
        hash = hash * B + firstName.hashCode();
        hash = hash * B + lastName.hashCode();
        
        return hash;
    }

    @Override
    public boolean equals(Object o) {
        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());
                
    }
}

实现一个HashTable：

package Date_pacage.hash;

import java.util.TreeMap;

//哈希冲突的处理：链地址法
//哈希表的动态空间处理：平均每个地址承载的元素过多一定程度，即扩容
// N/M >= upperTol
//平均每个地址承载的元素过少一定程度，即缩容
//N/M <= lowerTol
public class HashTable<K, V> {

    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private static final int initCapacity = 7;
    //这里要求K extends Comparable
    private TreeMap<K, V> hashtable[];
    //TreeMap[]:这里表达的是一个存储TreeMap类型的数组！
    private int M;//hashTable中有M个位置
    private int size;//整个哈希表中元素的个数，就是N
    
    public HashTable(int M) {
        this.M = M;
        size = 0;
        //哈希表的底层用了TreeMap，那么hashMap是怎么实现的
        //Hashtable与HashMap类似，不同的是：它不允许记录的键或者值为空；
　　　　 //它支持线程的同步，即任一时刻只有一个线程能写Hashtable，然而，这也导致了Hashtable在写入时会比较慢。
        hashtable = new TreeMap[M];
        for(int i = 0 ; i < M ; i ++) {
            hashtable[i] = new TreeMap<>();
        }
    }
    
    public HashTable() {
        this(initCapacity);
    }
    
    private int hash(K key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
    
    public int getSize() {
        return size;
    }
    
    public void add(K key, V value) {
        //如果有两个字符串的哈希值相同，他们就被分配到一个TreeMap中去
        //在将数据传入TreeMap时使用(key, value)，
        //key是字符串，value是字符串出现的个数
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key)) {
            map.put(key,  value);
        }else {
            map.put(key,  value);
            size ++;
            if(size >= upperTol * M) {
                resize(2 * M);
            }
        }    
    }
    
    public V remove(K key) {
        TreeMap<K, V> map = hashtable[hash(key)];
        V ret = null;
        if(map.containsKey(key)) {
            ret = map.remove(key);
            size --;
            if(size < lowerTol * M && M / 2 >= initCapacity) {
                resize(M / 2);
            }
        }
        return ret;
    }
    
    public void set(K key, V value) {
        TreeMap<K, V> map = hashtable[hash(key)];
        if(!map.containsKey(key)) {
            throw new IllegalArgumentException(key + "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);
    }
    
    private void resize(int newM) {
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for(int i = 0 ; i < newM ; i ++) {
            newHashTable[i] = new TreeMap<>();
        }
        
        int oldM = M;
        this.M = newM;
        for(int i = 0 ; i < oldM ; i ++) {
            TreeMap<K, V> map = hashtable[i];
            for(K key : map.keySet()) {
                newHashTable[hash(key)].put(key, map.get(key));
            }
        }
        this.hashtable = newHashTable; 
    }
}

hashMap中的hash方法：

作用：是返回输入对象在hashMap数组中的下标值

具体做法：

原始想法是根据hashcode()得到的散列值^数组长度，得到所在数组下标值，缺点是碰撞严重，只用到了散列值中数组长度的低位信息。

优化想法：增加一个扰动函数，也就是

(var1 = var0.hashCode()) ^ var1 >>> 16
相当于是增加了返回值的信息量，扰动之后的值^数组长度，这时得到的数组下标值碰撞次数减少了很多