哈希表

什么是哈希表

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。

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