数据结构——哈希表

淩亂°似流年 2022-04-22 01:12 315阅读 0赞

## 一、从一道Leetcode题目认识哈希表 ##

[387. 字符串中的第一个唯一字符][387.]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70][]

因为该字符串只包含小写字母，即只存在a-z 26个小写字母，我们将其a-z对应到数组0-25索引的位置，出现一次，index+1

代码编写：

class Solution {
        public int firstUniqChar(String s) {
            int[] freq = new int[26];
    
            for(int i = 0 ; i < s.length() ; i++)
                //统计字符串s 中，a-z的个数
                freq[s.charAt(i) - 'a']++;
            for(int i = 0 ; i < s.length() ; i++)
                if(freq[s.charAt(i) - 'a'] == 1 )
                    return i;
            return -1;
        }
    }

这个问题内部隐藏着哈希表的结构思想，我们开辟的 int\[\] freq 实际上就是一个哈希表，每一个字符都和数组中的一个索引对应

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 1][]

此时我们简单地坐到了将字符与索引进行了一一对应，这种**将"键"转化为"索引"的方式，称为哈希函数**。

有如一个班总共有30名学生，我们可以使用数组0-29分别表示这30名学生。

但是在某些情况下，如我们需要保存居民身份证、字符串、浮点数、日期等信息，就很难保证每一个"键"通过哈希函数的转换对应不同的"索引"。

不同的"键"通过哈希函数对应了同一个"索引"，称为哈希冲突。

哈希表充分体现了算法设计领域的经典思想：**使用空间换取时间**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 2][]

**所以我们需要①设计一个合理的哈希函数实现"键"与"索引"的对应关系，"键"通过哈希函数得到的"索引"分布越均匀越好**

**                          ②解决哈希冲突**。

## 二、哈希函数的设计 ##

**"键"通过哈希函数得到的"索引"分布越均匀越好，**哈希函数的设计很复杂，我们并不关注某一个特殊的领域，本文只对一般的哈希函数进行设计。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 3][]

后6位的前两位"16"取值范围为01 ~ 31 表示日期，造成了分布不均的问题，可见对取模的值的选择十分重要，一般模一个素数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 4][]

**模以合数和素数的区别：**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 5][]**

浮点数--->转化为整形处理

字符串--->转化为整形处理

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 7][]

对应的代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 8][]

符合类型--->转化为整形处理

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 9][]

关于哈希函数设计的总结：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 10][]

## 三、Java中的hashCode() ##

Object类中的hashCode()方法，在整形中的hashCode为数字本身，Double、Float、String等都重写了Object类中的hashCode()。

略

## 四、解决哈希冲突方法(链地址法Seperate Chaining) ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 11][]

## 五、编码实现哈希表 ##

version1:

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

**分析此时间复杂度：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 12][]

要想尽可能达到O(1)，固定地址空间是不合理的，需要resize()。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 13][]

//HashTable类新建成员变量    
        private static final int upperTol = 10;
        private static final int lowerTol = 2;
        private static final int initCapacity = 7;
    
    
        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) {
            TreeMap<K, V> map = hashtable[hash(key)];
            V ret = null;
            if (map.containsKey(key)) {
                ret = map.remove(key);
                size--;
                if (size <= lowerTol * M && M > initCapacity)
                    resize(M / 2);
            }
            return ret;
        }
    
        private void resize(int newM){
            TreeMap<K, V>[] newHashTable = new TreeMap[newM];
            for(int i = 0 ; i < newM ; i ++)
                newHashTable[i] = new TreeMap<>();
    
            for(int i = 0 ; i < M ; i ++)
                for(K key: hashtable[i].keySet())
                    newHashTable[hash(key)].put(key, hashtable[i].get(key));
    
            this.M = newM;
            this.hashtable = newHashTable;
        }

**再次分析此时间复杂度：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 14][]

我们在add后的resize(2 \* M)方法中   扩容M ---> 2\*M  ，发现扩容后2 \* M 此时并不是一个素数。

改进：采用素数，考虑HashMap的扩容，略

## 哈希表的得失 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 15][]

[387.]: https://leetcode-cn.com/problems/first-unique-character-in-a-string/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70]: /images/20220422/82431f8c880f4758a6b9f40385632210.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 1]: /images/20220422/0610d3210b4d40b28865a070a9b853e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 2]: /images/20220422/35205a7b93ea444799f1433869d9c6ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 3]: /images/20220422/b20ae9c296e0400ab3f2801679a1df50.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 4]: /images/20220422/ec26078ca28a49fc901521421a4b8a32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 5]: /images/20220422/34842a7ec81b4fa38be9c472238dfe95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 6]: /images/20220422/337db9001e9b403695fea357162fb1f7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 7]: /images/20220422/4e5e873a2db14122a0d5d069182fcdd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 8]: /images/20220422/5888b0f83d8e463cbdf0c7b6c4fdc012.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 9]: /images/20220422/18351f3a4a9f40e6806c9381c1e096e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 10]: /images/20220422/0d60a8da4e8b465c8d8816f2809490e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 11]: /images/20220422/43528112f98c4ec6853bbf9a65937fc9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 12]: /images/20220422/6f79370a54cb478d980ad155598ea7dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 13]: /images/20220422/159d676a2841473cb5e2e5f15c17ab98.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 14]: /images/20220422/b0c09d5e01144b4c83e2c2978fb7a178.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l0Y2F0c19jbg_size_16_color_FFFFFF_t_70 15]: /images/20220422/0366eda386034b12ba4cbb5f4e237c7e.png