哈希表和SQRT分解01：哈希表

如果定义一个数组，每一个字符都和一个索引相对应，那么对元素的查找操作是O(1)级别的

这个数组就称作哈希表，而将字符转化为对应的索引的方法称为哈希函数，转化以后就可以只在哈希表上操作而无需关注原始的字符

哈希函数的设计思路

哈希表一个很重要的问题是，很难保证每一个元素通过哈希函数的转换，都能对应不同的索引，这称为哈希冲突，而解决哈希冲突是哈希表的难点

哈希表充分体现了算法设计领域的经典思想：空间换时间，哈希表是时间和空间之间的平衡

哈希函数的设计思想是：“键”通过哈希函数得到的“索引”分布越均匀越好，可以将所有数据类型哈希函数的设计都转换为对整型的哈希函数设计

整型转换为索引

浮点型转换为索引

浮点型在计算机中是用32位或者64位的二进制表示的，因此可以看作是大整数

字符串型转换为索引

类似于二进制的计算方法，可以将字符串看成是B进制的大整数，B取决于字符串中所有字符的种类，M是选择取模的素数，一般就是哈希表的长度

通过化简，在计算时避免出现整型溢出

hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) % M = ((((c % M) * B + o) % M * B + d) % M * B + e) % M

int hash = 0;
for (int i = 0; i < s.length(); i++){
    hash = (hash * B + s.charAt(i)) % M;
}

Java中的hashCode()方法

Java中hashCode()方法的返回值是int类型，对于整数而言其数值大小就是其本身，可正可负；对于字符串而言是区分大小写的，可以用toLowerCase()方法将其都转化为小写

对于自定义的类，在设计哈希函数的时候，需要同时重写hashCode()和equals()方法，分别调用每个属性的哈希函数进行求和

class Student{

    int grade;
    int classNum;
    String firstName;
    String lastName;

    public Student(int grade, int classNum, String firstName, String lastName){

        this.grade = grade;
        this.classNum = classNum;
        this.firstName = firstName;
        this.lastName = lastName;
    }

    /**
     * 对于自定义类，一定要重写hashCode()方法，因为Java默认是根据对象的地址来计算哈希值的，如果两个对象的学生信息完全一样，哈希值也不会相同，这不符合实际的需求
     */
    @Override
    public int hashCode(){

        int B = 31;
        int hash = 0;

        hash = hash * B + grade;
        hash = hash * B + classNum;
        hash = hash * B + firstName.toLowerCase().hashCode();
        hash = hash * B + lastName.toLowerCase().hashCode();

        return hash;
    }

    /**
     * 虽然重写了hashCode()方法可以使得同一个学生信息的哈希值肯定相等，但是不同对象的哈希值还是有可能相等，会产生哈希冲突
     * 因此还需要重写equals()来进一步判断这两个对象是不是相等
     */
    @Override
    public boolean equals(Object o){

        if (o == null){
            return false;
        }

        if (o == this){
            return true;
        }

        if (o.getClass() != this.getClass()) {
            return false;
        }

        Student newO = (Student) o;

        return  newO.grade == this.grade &&
                newO.classNum == this.classNum &&
                newO.firstName.toLowerCase().equals(this.firstName.toLowerCase()) &&
                newO.lastName.toLowerCase().equals(this.lastName.toLowerCase());
    }
}

拓展：Java中基于哈希表实现的数据结构是HashSet()和HashMap()

实现哈希表的方法——链地址法

Java的哈希方法结果可正可负，为了在取模时更方便计算，可以对结果取绝对值，或者和0x7fffffff进行与操作，将符号位转为0

当产生哈希冲突时，在相同索引的位置，以链表或者红黑树的结构进行存储

实现哈希表

import java.util.TreeMap;

/**
 * 哈希表不用进行比较，因此不用实现Comparable接口
 * 其底层直接采用TreeMap数组实现
 */
class HashTable{

    private TreeMap[] hashTable;
    private int M;
    private int size;

    /**
     * 用户可以自定义哈希表的长度，不同的长度性能会有所不同
     */
    public HashTable(int M){

        this.M = M;
        size = 0;
        hashTable = new TreeMap[M];

        /**
         * 创建一个TreeMap数组来存储哈希值，数组中每一个索引对应的也是一个TreeMap对象，也需要实例化
         */
        for (int i = 0; i < M; i++) {
            hashTable[i] = new TreeMap<>();
        }
    }

    public HashTable(){

        this(97);
    }

    /**
     * 哈希函数
     * 对传进来的任意元素，调用其自身的hashCode()方法获得对应的哈希值，该哈希值就是其存储在数组中的索引
     * 在该索引处的TreeMap中添加这个元素
     */
    private int hash(K key){

        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize(){

        return size;
    }

    /**
     * 增
     * 如果已经存在该元素，那只是修改，不会增加size
     */
    public void add(K key, V value){

        TreeMap map = hashTable[hash(key)];

        if (map.containsKey(key)){
            map.put(key, value);
        }
        else {
            map.put(key, value);
            size++;
        }
    }

    /**
     * 删
     * 如果该元素存在就进行删除
     */
    public V remove(K key){

        TreeMap map = hashTable[hash(key)];
        V value = null;

        if (map.containsKey(key)){

            value = map.remove(key);
            size--;
        }

        return value;
    }

    /**
     * 改
     */
    public void set(K key, V value){

        TreeMap map = hashTable[hash(key)];

        if (!map.containsKey(key)){
            throw new IllegalArgumentException("元素不存在");
        }

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

动态空间处理

哈希表在使用静态的数组时，其地址空间的个数是固定的，时间复杂度会受到元素个数n的影响，达不到O(1)级别

因此，需要进行动态空间处理，当平均每个地址承载的元素个数大到一定程度时就进行扩容，反之则进行缩容，均摊复杂度为O(1)

import java.util.TreeMap;

class HashTable{

    /**
     * 定义扩缩容的临界值和默认容量
     */
    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private static final int initCapacity = 7;

    private TreeMap[] 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(initCapacity);
    }

    private int hash(K key){

        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize(){

        return size;
    }

    /**
     * 增
     * 如果平均承载元素大于upperTol时容量翻倍
     */
    public void add(K key, V value){

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

    /**
     * 删
     * 如果平均承载元素小于lowerTol且容量减半后还大于默认容量时，容量减半
     */
    public V remove(K key){

        TreeMap map = hashTable[hash(key)];
        V value = null;

        if (map.containsKey(key)){

            value = map.remove(key);
            size--;

            if (size < lowerTol * M && M / 2 >= initCapacity){
                resize(M / 2);
            }
        }

        return value;
    }

    /**
     * 扩缩容
     */
    public void resize(int newM){

        TreeMap[] 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 map = hashTable[i];

            /**
             * 内层for循环的hash()方法中计算使用的应该是newM而不是原来的M
             * 而外层for循环中使用是原来的M，为了避免冲突，将其保存成oldM
             */
            for (K key : map.keySet()){
                newHashTable[hash(key)].put(key, map.get(key));
            }
        }

        this.hashTable = newHashTable;
    }

    public void set(K key, V value){

        TreeMap map = hashTable[hash(key)];

        if (!map.containsKey(key)){
            throw new IllegalArgumentException("元素不存在");
        }

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

改进的动态空间处理

虽然上述的扩缩容大大降低了时间复杂度，但在对容量M进行翻倍还有减半时，会让其不再是素数，这增加了哈希冲突的可能性

因此可以将已有的数学统计数据作为扩缩容的大小

import java.util.TreeMap;

class HashTable{

    /**
     * 使用数学上计算出来的最优容量来进行扩缩容（只截取了一部分）
     * 根据该数组的索引来选择，初始容量的索引为0
     */
    private static final int[] capacity = {53, 97, 193, 389, 769, 1543};
    private static final int upperTol = 10;
    private static final int lowerTol = 2;
    private int capacityIndex = 0;

    private TreeMap[] hashTable;
    private int M;
    private int size;

    public HashTable(){

        this.M = capacity[capacityIndex];
        size = 0;
        hashTable = new TreeMap[M];

        for (int i = 0; i < M; i++) {
            hashTable[i] = new TreeMap<>();
        }
    }

    private int hash(K key){

        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize(){

        return size;
    }

    public void add(K key, V value){

        TreeMap map = hashTable[hash(key)];

        if (map.containsKey(key)){
            map.put(key, value);
        }
        else {
            map.put(key, value);
            size++;

            /**
             * 扩容时使用最优容量数组的下一个元素
             */
            if (size >= upperTol * M && capacityIndex + 1 < capacity.length){
                resize(capacity[capacityIndex++]);
            }
        }
    }

    public V remove(K key){

        TreeMap map = hashTable[hash(key)];
        V value = null;

        if (map.containsKey(key)){

            value = map.remove(key);
            size--;

            if (size < lowerTol * M && capacityIndex - 1 >= 0){
                resize(capacity[capacityIndex--]);
            }
        }

        return value;
    }

    public void resize(int newM){

        TreeMap[] 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 map = hashTable[i];

            for (K key : map.keySet()){
                newHashTable[hash(key)].put(key, map.get(key));
            }
        }

        this.hashTable = newHashTable;
    }

    public void set(K key, V value){

        TreeMap map = hashTable[hash(key)];

        if (!map.containsKey(key)){
            throw new IllegalArgumentException("元素不存在");
        }

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

哈希表的性能

哈希表的均摊复杂度为O(1)，比平衡树还要低，但是以牺牲了顺序性为代价换来的。Java自带的集合框架中，有序集合和映射是使用平衡树实现，无序集合和映射则是采用哈希表实现

其他实现哈希表的方法

开放地址法

链地址法中，每个位置只存放哈希值相等的元素；而开放地址法相反，每个位置只存储一个元素，如果后来的元素产生了哈希冲突，就往后寻找第一个空的位置存放

再哈希法

产生哈希冲突时，使用另一个哈希方法进行计算