哈希表
哈希表
1.什么是哈希表
int[26] freq 就是一个哈希表！每一个字符都和一个索引相对应！
将我们关注的值，转化为索引，使用哈希函数。当然在大多数情况下，我们的哈希函数没有那么简单。
在实际中可能索引为字符串，或者为浮点数，日期，我们在使用哈希表的时候，都需要设计一个哈希函数转换为索引。
这是设计hashTable的第一个任务。
我们在实际操作中，很难保证每一个“键”通过哈希函数的转换时，可能两个不同的键对应相同的索引，这就是哈希冲突。这也是hash表需要解决的第二个问题。
在设计hashTable时我们需要解决两个问题：
1.哈希函数的设计
2.哈希冲突
哈希表充分体现了算法设计领域的金典思想：空间换时间，哈希表是时间和空间之间的平衡
如果我们有 999999999999999999的空间，我们可以用O(1)的时间完成各项操作
如果我们有1的空间，我们只能用O（n）时间完成各项操作（线性表）
“键”通过哈希函数得到的“索引”分布越均匀越好
2哈希函数的设计
对于一些特殊的领域，有特殊领域的哈希函数设计方式，甚至有专门的论文，我们这里只关注哈希函数的一般设计原则。
a.整形（对于所有的类型都可以转换成整形）
对于上面这个身份证，其实就是取6666，我们知道空间越大那么就是哈希冲突越小。
对于身份证我们取后6位，看起来很好其实倒数第6为为日期，日期最大为31，这就会造成分布不均匀。这个问题就是这个问题的陷阱，所以取模的这个数就很重要了，还有一个小的问题，没有利用所有的问题，直接将前面的信息给丢掉了。
一个简单的办法：模一个素数（背后有强大的数学理论）
其实如果我们的大整数，都是均匀分布的，那么模任何一个数都是可以的；但是就怕这个大整数规律性特别强。看下面的这个：哈希冲突的规律比较大。
关于素数的选择，有专门的人去研究，在这个网站中有详细的说明，可看出在不同的数据范围，我们可以选择合适的素数
http://planetmath.org/goodhashtableprimes
b.浮点型
转成整形来处理，然后根据整形来处理就行
b.字符串
转成整型处理
变形：
有可能里面计算会有整形的溢出，我们可以将%M 移到括号的里面
代码实现：
int hash = 0;
for(int i = 0 ; i < s.length(); i ++)
hash = (hash * B + s.charAt(i)) % M
c.复合类型
比如一个学生有：姓名，学号，年级，日期等等
符合类型：转换成整型处理
转换成整型处理，并不是唯一的方法！不管怎样都符合下面的原则
原则：
1. 一致性： 如果 a==b， 则hash(a) == hash(b)
2. 高效性： 计算高效简便
3. 均匀性：哈希均匀分布
3. 哈希冲突的处理
a. 链地址法（Seperate Chaining）
此时来了一个k3，k3与k2冲突了，我们将k3也存到1的位置，链表的存储方式，实现方式底层不见得是一个链表，我们也完全可以使用平衡树结构，我们可以存一个TreeMap，相应的我们来一个元素，找到这个索引位置的这个TreeMap，插进这个TreeMap里面就好了。
HashMap 就是一个 TreeMap的数组； HashSet 就是一个TreeSet 数组
一定程度：就是说每一个地址的平均冲突达到某一个值，就使用红黑树，其实是一个TreeMap（java中TreeMap就是使用红黑树实现的）当数据规模比较小的时候冲突小，使用链表要快。
b.使用链地址法处理冲突，哈希表的时间度分析
时间消耗，其实就是在链表的时间消耗上
平均来看，非常差，全部发生地址冲突。那么链地址法就需要O(N)的时间复杂度。如果是平衡树:O(log(N))，这里如果是一个静态数组的话，我们的N无穷大的时候，那么N/M就无穷大了，所以我们的地址固定为M个显然不太合理。
改进的方案，空间应该随着N的改变自适应。
哈希表的动态空间处理：
我们同动态数组的均摊复杂度分析 平均复杂度为O(1)
4. 哈希冲突的处理
前面我们讲到的链地址法，其实就是一个封闭地址法！
a.开放地址法( 每一个地址只存元素，如果冲突了就放到它的下一个地址中)
开放地址里面的线性探测法
线性探测法的性能比较低，消耗比较高，基于此有一些改进法，像平法探测法，先是直接+1，然后+4 +9，+16 等等
对于开发地址法，也有可能达到最大容积，此时也需要扩容，通常对于开放地址法有一个指标叫做负载率（存储总数/开放地址大小）对于开发地址法，只要负载率选择合适也是O(1)的时间复杂度。
使用TreeMap的数组来实现hashTable，代码如下：
public class HashTable<K, V> {
private final int[] capacity
={53,97,193,389,769,1543,3079,6151,12289,24593,
49157,98317,196613,393241,786433,1572869,3145739,
6291469,12582917,25165843,50331653,100663319,201326611,
402653189, 805306457, 1610612741};
private static final int upperTol = 10;
private static final int lowerTol = 2;
private int capacityIndex = 0;
private TreeMap<K, V>[] hashtable;
private int size;
private int M; // 长度
public HashTable(){
this.M = capacity[capacityIndex];
size = 0;
hashtable = new TreeMap[M];
for(int i = 0 ; i < M ; i ++)
hashtable[i] = new TreeMap<>();
}
// key可以是任意的类型，先转成整形
private int hash(K key){
return (key.hashCode() & 0x7fffffff) % M;
}
public void add(K key, V value){
TreeMap<K, V> map = hashtable[hash(key)];
// if(!hashtable[hash(key)].containsKey(key)){
if(!map.containsKey(key)){
map.put(key, value);
size ++;
// N/M >= upperTol 防止整形到浮点转化
if(size >= upperTol * M && capacityIndex + 1 < capacity.length)
capacityIndex ++;
resize(capacity[capacityIndex]);
}
}
public V remove(K key){
V ret = null;
TreeMap<K, V> map = hashtable[hash(key)];
if(map.containsKey(key)){
ret = map.remove(key);
size --;
// M > initCapacity 至少要多少
if(size <= lowerTol * M && capacityIndex - 1 >= 0)
capacityIndex --;
resize(capacity[capacityIndex]);
}
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){
//hashtable[hash(key)] 找到TreeMap
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<>();
// 将原先hashTable中放到新的hashTable中
int oloM = M;
this.M = newM;
for(int i = 0 ; i < oloM ; i ++)
for(K key: hashtable[i].keySet())
newHashTable[hash(key)].put(key, hashtable[i].get(key));
//this.M = newM;
this.hashtable = newHashTable;
}
}