哈希函数设计
- O(1)的复杂度
- 哈希函数的设计是很重要的，重点解决哈希冲突
- 哈希表充分体现了算法设计领域的经典思想：空间换时间
- 哈希表是时间和空间之间的平衡
- “键”通过哈希函数得到的“索引分布越均匀越好”
- 对于一些特殊领域，有特殊领域的哈希函数设计方式，甚至有专门的论文
这里介绍的主要是一般的哈希函数的设计原则：
-
大整数
模一个素数 -- 数论中的理论,模一个质数会大大减少hash冲突，一般创建的hashTable储存链表或者红黑树的数组的长度就是这个质数的大小(根据key获得hashCode之后按照这个质数取模)，而这个模的大小也直接影响了HashTable的性能，如果太小，哈希冲突就会更多，如果太大就太浪费空间。
-
浮点数
利用底层储存原理转换为整型（只占32位或者64位空间）
-
字符串
转成整型处理
- 复合类型
注意：转成整型的处理，并不是唯一的方法！
哈希函数设计的原则:
- 一致性：如果a==b，则hash(a) == hash(b)
- 高效性：计算高效简便
- 均匀性：哈希值均匀分布
Java中hashCode方法
Object中定义的hashCode是根据创建的对象的地址值映射成一个整型进行设计的;
由于Object类中定义了hashCode方法，所以java中的任何对象都可以进行hash运算。
覆盖Object中的hashCode方法
覆盖Object中的equals方法(判断两个类是否相同)
@Override
public int hashCode() {
// 生成hashCode的逻辑
return 0;
}
@Override
public boolean equals(Object o) {
if(this == o)
return true;
if(o == null)
return false;
if(getClass() != o.getClass())
return false;
return "自定义的业务逻辑".equals("");
}
链地址法 Separate Chaining
哈希冲突的处理：链地址法
补充：去符号的方法；位与运算number & 0x7fffffff
注意：这种方式并不等于Math.abs(number)
Java中TreeMap是一颗红黑树
Java中的HashMap与HashSet
哈希表链地址法 时间复杂度分析
假设有M个地址，如果放入哈希表的元素为N，由于hash函数的设计就是为了满足hash值非常平均，如果每个地址是链表，那么平均复杂度
O(N/M);,如果每个地址是平衡树，那么平均复杂度为O(lon(N/M)),但是，在信息安全领域，有一种，哈希碰撞攻击 （了解了哈希值的计算方法之后，精心的设计一套数据，从而产生极端的hash冲突。）
如何将时间复杂度改为O(1)呢？
数组应该是动态改变的
平均每个地址承载的元素多个一定的程度，就进行扩容
N/M >= upperTol平均每个地址承载的元素烧过一定的程度，就进行缩容
N/M < lowerTOl
注意：在计算的时候最好转换成乘法，因为是整型的计算
哈希表更复杂的动态空间处理方法
哈希表的均摊复杂度分析
更复杂的动态空间处理方法
之前的扩容方式为
M -> 2 * M,很显然这样扩容之后数组的长度不是一个素数，这会让hash分布不均匀.
解决方案：
补充：1610612741是素数中逼近int类型数组可以承载的极限值！相邻的两个数也基本保持的两倍的关系！
详见代码
import java.util.TreeMap;
public class HashTable<K extends Comparable<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];
this.size = 0;
this.hashtable = new TreeMap[M];
for (int i = 0; i < this.M; i++) {
// 每一个元素对应一个TreeMap,不可能为null
hashtable[i] = new TreeMap<>();
}
}
private int hash(K key) {
// 获取Java提供的计算hashCode的值
// 并取出负值，然后取模得到数组对应的索引
return (key.hashCode() & 0x7fffffff) % M;
}
public int getSize() {
return this.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 && 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 --;
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 exit!");
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 = this.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;
}
}
哈希表的均摊复杂度为O(1)，非常有性能优势，但是，牺牲了什么呢？答案就是失去了顺序性！
基于这些特性，集合和映射可分为
- 有序集合，有序映射 --- >平衡树实现
- 无序集合，无序映射 ---> 哈希表
!!我们的哈希表的bug:-!!
我们hash表内部是使用TreeMap，必须要求Comparable,但是hash表的原则是无序的，不需要可比较！
更多哈希冲突的处理办法
-
开放地址法
所有地址对所有元素开放
哈希冲突的处理方式：- 线性探测：遇到哈希冲突就 + 1
- 平方探测：遇到哈希冲突就 +1 +4 +9 +16等等
- 二次哈希法：遇到哈希冲突， + hash2(key)
再哈希法
Coalesced Hashing
比较复杂，综合了Seperate Chaining 和 Open Addressing的特点
