关于java:数据结构之哈希表

Hash 表也称散列表，也有间接译作哈希表，Hash 表是一种非凡的数据结构，它同数组、链表以及二叉排序树等相比拟有很显著的区别，它可能疾速定位到想要查找的记录，而不是与表中存在的记录的关键字进行比拟来进行查找。这个源于 Hash 表设计的特殊性，它采纳了函数映射的思维将记录的存储地位与记录的关键字关联起来，从而可能很疾速地进行查找。

要想理解哈希表咱们先从 LeetCode 的一道题目开始。

387. 字符串中的第一个惟一字符

给定一个字符串，找到它的第一个不反复的字符，并返回它的索引。如果不存在，则返回 -1。

案例:

s = “leetcode”
返回 0.

s = “loveleetcode”,
返回 2.

注意事项：您能够假设该字符串只蕴含小写字母。

public class Solution {public static int firstUniqChar(String s) {
        // 申明 26 个字母的长度数组
        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++) {
            // 判断从第一位开始哪一位是 1 则返回以后字符，1 表明只呈现了一次
            if(freq[s.charAt(i) - 'a'] == 1){return i;}
        }
        return -1;
    }

}

在这道题中，int[26] freq 就是一个哈希表！

每一个字符都和索引进行对应

a ===> 0

b ===> 1

c ===> 2

…..

z ===> 25

并且咱们的查找是 O(1) 级别！

“ 键 ” 通过哈希函数失去的 ” 索引 ” 散布越平均越好

准则：

一致性：如果 a ==b 则 hash(a) == hash(b)
高效性：计算高效不便
平均性：哈希值均匀分布

Hash 函数设计的好坏间接影响到对 Hash 表的操作效率。上面举例说明：

如果对上述的联系人信息进行存储时，采纳的 Hash 函数为：姓名的每个字的拼音结尾大写字母的 ASCII 码之和。

address(张三)=ASCII(Z)+ASCII(S)=90+83=173;
address(李四)=ASCII(L)+ASCII(S)=76+83=159;
address(王五)=ASCII(W)+ASCII(W)=87+87=174;
address(张帅)=ASCII(Z)+ASCII(S)=90+83=173;

如果只有这 4 个联系人信息须要进行存储，这个 Hash 函数设计的很蹩脚。

首先，它节约了大量的存储空间。因为如果采纳 char 型数组存储联系人信息的话，每个人的信息须要 12 个字节来存储。
（手机号为 11 位，数值上为 100 多亿，2^64 =1.844674407371 * 10^19，2^32 = 4294967296，所以须要 64 位也就是 8 个字节来存储手机号。
每个汉字占两个字节，两个汉字占四个字节。
所以总共须要 8 + 4 = 12Byte）
这样的话，至多须要开拓 174*12 字节的空间。然而空间利用率只有 4 /174，不到 3%。

另外，依据 Hash 函数计算结果之后，address(张三)和 address(张帅)具备雷同的地址，这种景象称作抵触，对于 174 个存储空间中只须要存储 4 条记录就产生了抵触，这样的 Hash 函数设计是很不合理的。所以在结构 Hash 函数时应尽量思考关键字的散布特点来设计函数使得 Hash 地址随机平均地散布在整个地址空间当中。

通常有以下几种结构 Hash 函数的办法：

1 间接定址法
取关键字或者关键字的某个线性函数为 Hash 地址，即 address(key)=a*key+b; 如晓得学生的学号从 2000 开始，最大为 4000，则能够将 address(key)=key-2000 作为 Hash 地址。

2 平方取中法
对关键字进行平方运算，而后取后果的两头几位作为 Hash 地址。如果有以下关键字序列 {421，423，436}，平方之后的后果为{177241，178929，190096}，那么能够取两头的两位数{72，89，00} 作为 Hash 地址。

3 折叠法
将关键字拆分成几局部，而后将这几局部组合在一起，以特定的形式进行转化造成 Hash 地址。如果晓得图书的 ISBN 号为 8903-241-23，能够将 address(key)=89+03+24+12+ 3 作为 Hash 地址。

4 除留取余法
如果晓得 Hash 表的最大长度为 m，能够取不大于 m 的最大质数 p，而后对关键字进行取余运算，address(key)=key%p。

在这里 p 的选取十分要害，p 抉择的好的话，可能最大水平地缩小抵触，p 个别取不大于 m 的最大质数。

哈希表设计

咱们首先建设一个数组，M = 素数

这个时候咱们增加进去 K1 和 K2

而后咱们再增加进去一个 K3，如果他和 K2 的哈希抵触了就会造成如下图这样。这样就会造成一个链表。

相应的咱们能够不必链表来存储，能够应用树结构 TreeMap 也是能够的。

在 Java8 中当哈希抵触达到肯定水平后，每一个地位就会转换为红黑树。

public class HashTable<K,V> {private TreeMap<K,V>[] hashTable;
    // 素数
    private int m;
    private int size;

    public HashTable(int m) {
        this.m = m;
        this.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)){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);
    }

}

public class HashTable<K,V> {private TreeMap<K,V>[] hashTable;
    // 素数
    private int m;
    private int size;
    // 哈希抵触上界
    private static final int upperTol = 10;
    // 哈希抵触下界
    private static final int lowerTol = 2;
    // 初始容量
    private static final int initCapacity = 7;

    public HashTable(int m) {
        this.m = m;
        this.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){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;
    }

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

    public void set(K key,V value){TreeMap<K,V> map = hashTable[hash(key)];
        if(map.containsKey(key)){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);
    }

}

除了链地址法解决哈希抵触外，还有很多种能够解决哈希抵触的办法，这里再说一下凋谢地址发。意思就是每一个地址都对所有的元素是凋谢的。

假如以后数组是这个样子。

咱们如果要增加一个 31，发现它和 11 的哈希值产生了抵触，这个时候他会去找 11 下一个索引为空位的中央来寄存。后果就是放在了 2 的地位。

如果又来了一个 81 也是抵触的呢，天然就是会放到 3 索引的地位上。

这就是凋谢地址法中的 线性探测法，遇到哈希抵触 +1。然而这个办法性能并不高，因为如果有一片都抵触了，要不停的往上来寻找。

另一种就是 平方探测法，具体就是先 + 1 去找如果 + 1 抵触了间接就 + 4 去找还抵触就是 +9、+16。

还有 再哈希法 等等，就是再用另一种哈希算法来算地址地位。

关于java:数据结构之哈希表

哈希表

什么是哈希表

哈希函数的设计

链地址法

实现咱们本人的哈希表

哈希表的动静空间

凋谢地址法