哈希表

朱雀 2022-05-16 10:11 310阅读 0赞

# 1. 什么是哈希表 #

我们先来做个题（leetCode上387题）

![70][]

public class Solution_387 {
        public int firstUniqChar(String s) {
            int[] freq = new int[26];
    
            for(int i=0 ; i<s.length() ; i++)
                freq[s.charAt(i)-'a'] ++;
    
            for(int i=0; i<s.length() ; i++)
                if(freq[s.charAt(i)-'a'] == 1)
                    return i;
            return -1;
        }
    }

这个题背后就隐藏着哈希表这种数据结构的思想

![70 1][]

它的本质就是把我们真正关心的那个内容，即字符（ch）转换成一个索引（index），然后直接用一个数组来存储相应的内容，由于我们数组本身是支持随机访问的，所以我们可以使用O(1)的时间复杂度来完成操作。

在哈希表中，我们是可以存储各种类型的数据，对于每种数据类型，我们都需要一个方法把它转换成索引，相应的我们关注的这个类型转换成索引的这个函数就称为哈希函数。很多时候哈希函数并不是像上一题那样容易.

![70 2][]

![70 3][]

![70 4][]

# 2. 哈希函数的设计 #

上一节我们说到“键”通过哈希函数得到的“索引”分布越均匀越好，但这个是很难做到的。对于一些特殊领域，有特殊哈希函数设计方法，甚至有专门的论文，所以我们主要关注一般的哈希函数的设计原则。

我们先来看下整型：

![70 5][]

![70 6][]

我们知道身份证倒数56位代表着这个人生日的日期，如上就是16号生日，而一个月最多也就31天，所以如果对于省份证只取后六位，会导致索引全部分布在320000以内，导致**分布不均匀，**并且只取六位也**没有利用所有信息，**这两点都会导致哈希冲突

![70 7][]

再来看下浮点型：

![70 8][]

我们看下字符串型：

![70 9][]

如果我们字符太多，上面的计算公式就很复杂。我们使用多项式的化简

![70 10][]

上面大括号里面的值可能会很大，大到产生整型溢出，所以我们可以把取模的过程挪到括号里面

![70 11][]

![70 12][]

最后来看下符合类型,其实它也可以套用上面的公式：

![70 13][]

可以看到上面，我们都是转成整型处理，但要记住，这并不是唯一办法，因为哈希函数的设计是一个很深奥的问题，每种不同的情况应该做不同的设计

![70 14][]

# 2. java中hashCode() #

在们具体使用java编程的时候，对于基本的数据类型如字符串String等，我们根本不需要自己去实现hash函数，在java语言中对于这些类型都可以调用其中的hashCode这样的一个方法直接获得我们当前的这个数据所对应的那个hash函数的值。

public class Main {
        public static void main(String[] args) {
            int a = 42;
            System.out.println( ((Integer)a).hashCode() );
    
            int b = -42;
            System.out.println( ((Integer)b).hashCode() );
    
            double c = 3.1415926;
            System.out.println( ((Double)c).hashCode() );
    
            String d = "yy";
            System.out.println( d.hashCode() );
    
        }
    }
    
    
    结果：
    42
    -42
    219937201
    3872

**我们java中的hashCode与我们开始说的哈希函数有些不同。对于java的hashCode,它的返回值是一个int值，由于int是有符号的，所以hashCode()返回的值有可能是正，有可能是负具体我们要将我们的hashCode转成一个索引，这个工作需要在哈希表的类中来完成**

其实这个也合理，我们在上一小节所讲的，整型转换成索引的方式，是对素数进行一个取模的运算，这个素数的值其实也是哈希表的大小，如果我们没有这个哈希表的话，我们也取不出我们的素数。所以我们定义这个类的时候就不能把它直接转换成我们的索引，这是因为我们不知道这个索引的最大值是多少。**所以在java的设计中的hashCode的接口只是将每一个数据类型和整型对应起来**，这个整型可正可负，而**这个整型如何和你的数组中的索引对应，这一点由我们的哈希表内部的逻辑来完成**

如果我们需要自定义一个类型，比如自定义学生类，对于这个类，我们可以覆盖Object类中的hashCode()函数来定义自己类相应的哈希值。

package com.javaweb.demo;
    
    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;
        }
    
        @Override
        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;
        }
    }

package com.javaweb.demo;
    
    public class Main {
        public static void main(String[] args) {
    
            Student student = new Student(3,2,"young","young");
            System.out.println(student.hashCode());
    
            Student student1 = new Student(3,2,"YOUNG","YOUNG");
            System.out.println(student1.hashCode());
    
    
        }
    }
    
    
    结果：
    -609474657
    -609474657

我们类有hashCode之后，从道理上我们就可以使用java为我们提供的和哈希表有关的数据结构了。java中为我们提供了两个和哈希表相关的结构，一个是HashSet（以哈希表为底层结构的集合），一个HashMap。

![70 15][]

将student传进去，在具体存储上，他就会自动调用我们Student类中的hashCode,然后计算出一个索引值，存储到一个相应的位置中。

需要注意的是：

1）对于我们Student类如果没有重写HashCode方法的话，我们调用的就是Object类中的hashCode方法，它是将我们创建的每个类的地址相应的把它转换成一个整型。

2）当我们使用HashSet和HashMap的时候，**hashCode方法只是用于帮我们就算哈希函数的值，但是在产生哈希冲突的时候，我们同样是要比较两个不同的对象他们之间是否是相等的**，也就是他们对应的哈希函数的值虽然相等，此时我们要辨别两个对象的不同，我们就要真正的看两个类是否是相等的，正因为如此，**我们要将这个类作为哈希表的键的话，我们只复写了hashCode方法是不够的，我们还要对这个类复写equals方法（判断两个对象是否相等）**

![70 16][]

这样，当我们覆盖了自定义类里面equals方法以后，我们再来把我们的类作为HashSet或者HashMap的键来使用才是真正的放心了，此时在产生哈希冲突时，虽然两个对象对应同样的哈希值，我们也可以使用equals这样的方法来区分这两个类对象的不同。

# 3.哈希冲突处理—链地址法（Seperate Chaining） #

其中M就是一个整数求哈希值的时候对一个素数取模的模

![70 17][]

![70 18][]

![70 19][]

# 4. 自己写HashTable #

import java.util.TreeMap;
    
    public class HashTable<K, V> {
    
        private TreeMap<K, V>[] hashtable;
        private int size;
        private int M;
    
        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){
            V ret = null;
            TreeMap<K, V> map = hashtable[hash(key)];
            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(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);
        }
    }

**  因为M是固定的，如果N无线大的话，那么N/M也是无限大的。所以我们的数组如果是基于一个静态数组的话，显然是不合理的（N增加M不能改变）**

![70 20][]

![70 21][]

![70 22][]

![70 23][]

import java.util.TreeMap;
    
    public class HashTable<K , V> {
        private static final int upperTol = 10;
        private static final int lowerTol = 2;
        private static final int initCapacity = 7;
    
        private TreeMap<K, V>[] hashtable;
        private int size;
        private int M;
    
        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;
        }
    
        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 ++;
    
                if(size >= upperTol * M)
                    resize(2 * M);
            }
        }
    
        public V remove(K key){
            V ret = null;
            TreeMap<K, V> map = hashtable[hash(key)];
            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;
        }
    
    }

[70]: /images/20220516/6d51063cac8d469d9f5abf2dbbb54427.png
[70 1]: /images/20220516/93d0fc6dd9424f27807699d7c966f2fe.png
[70 2]: /images/20220516/58fd289e692c439aabf974b5400c4ede.png
[70 3]: /images/20220516/73ff013939c840be80160046a00330ff.png
[70 4]: /images/20220516/8a7fbaca6f984b929c915d4608200486.png
[70 5]: /images/20220516/f136927d2b0e498e8e645a0d0c25002e.png
[70 6]: /images/20220516/40ebc1d32b8245eba365a8289a51f356.png
[70 7]: /images/20220516/c9f1715f940645aeafdefa49f43c079e.png
[70 8]: /images/20220516/8d7232cbff76450d8f540cbd27343669.png
[70 9]: /images/20220516/6a16775ee46a47c0bd169d358340254c.png
[70 10]: /images/20220516/f77ada205c95467d884ecbb0ba8ff8cb.png
[70 11]: /images/20220516/6d100af063414ca0818b18c0ccb37660.png
[70 12]: /images/20220516/88c4665bdabc4fa4af1e8bc53ce32e53.png
[70 13]: /images/20220516/d1020d233e984d5fa1a95200305b0b52.png
[70 14]: /images/20220516/a623079aad3d4e519ecdcc8811e1fb8a.png
[70 15]: /images/20220516/ba4f33750fde42a1bd98682982a81cd6.png
[70 16]: /images/20220516/402e68c9e38e4e7ea740099de03b94fd.png
[70 17]: /images/20220516/113f242629ce473883f05bbd2476bd3f.png
[70 18]: /images/20220516/a311773d11d74b4596441857129c7033.png
[70 19]: /images/20220516/09c5b7e5b43b47bbabf0ecdadd06e25e.png
[70 20]: /images/20220516/bc28cc503f824d318228a741a16d3e75.png
[70 21]: /images/20220516/ae8d207c9ef142589cce132b3bc77337.png
[70 22]: /images/20220516/145fd651354844a3ac8eea808cfb0b26.png
[70 23]: /images/20220516/8bf79e14c63f428e968eaa7b6c9d9cd3.png