哈希表
哈希表中，每一个元素都和一个索引对应。
比如在leetcode中，的387号问题;
相关解决方案:
class Solution {
public int firstUniqChar(String s) {
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 ++)
if(freq[s.charAt(i) - 'a'] == 1)
return i;
return -1;
}
}
其中的每一个字符对应一个索引。每一个类型转化为索引的函数称为哈希函数（上例中就是`ch - ‘a’）。然后在哈希表上进行相应操作。
在建立哈希表时很难保证每一个“键”通过哈希函数的转换对应不同的“索引”，这样会造成哈希冲突。所以关键在于如何解决哈希冲突。哈希表使用空间换时间，是时间和空间之间的平衡。
设计哈希函数
哈希函数设计时，“键”通过哈希函数得到的“索引”分布越均匀越好。对于一些特殊的领域，有特殊的哈希函数设计方式。
哈希函数的设计遵循三个原则:
- 一致性：如果a==b,则hash(a) == hash(b)
- 高效性：计算高效简便
- 均匀性：哈希值均匀分布
基本类型
- 整型 对于整型，小范围正整数可以直接使用
小范围的负整数进行偏移相应的能够转化为索引的函数称为哈希函数。
对于大整数，比如身份证号可以采用取模的方法（比如可以取模后四位、后6位）。但是后6位中，有两位是表示日期的，日期最多是1-31，那么就会产生分布不均匀的情况。所以要根据具体问题具体分析，很难有一个通用的解决方法。
在取模时，模一个素数是一个通常的解决方案。
- 浮点型
基本数据类型在计算机中都是32位或者64位的二进制表示，只不过计算机根据一定的法则给解析成了浮点数。在处理时，可以吧浮点数的32位或者64位空间转化为整型进行处理。
- 字符串
字符串也可以转为整型进行处理。
比如: 166 = 1 * 10^2 + 6 * 10^1 + 6 * 10 ^0 code = c * 26^3 + o * 26^2 + d * 26^1 + e * 26^0 (看成26进制的整型) code = c * B^3 + o * B^2 + d * B^1 + e * B^0 (看成B进制的整型) hash(code) = ( c * B^3 + o * B^2 + d * B^1 + e * B^0 ) % M (M为取模时选取的素数) 也等价于 hash(code) = ( ( ( ( c * B ) + o ) * B + d ) * B + e ) % M
为了避免整型的溢出，也可以先取模在继续进行下一步： hash(code) = ( ( ( ( c % M) * B + o ) % M * B + d ) % M * B + e ) % M
int hash = 0;
for(int i = 0 ; i < s.length() ; i ++)
hash = (hash * B + s.charAt(i)) % M
- 符合类型
优先考虑方法也是转化为整型处理。 例如 Date: year,month,day
hash(date) = (((date.year % M ) * B + date.month) % M * B) + date.day) % M
java中的hashCode
java中给我们提供了很多现有的hashCode方法。 Object对象有hashCode()方法，调用此方法可以返回这个对象的hash值。 java中的hashCode()方法返回的hash值都是整型的，如果有需要，用户可以进一步处理。
public class Main {
public static void main(String[] args){
int a = 2;
System.out.println(((Integer)a).hashCode());
int b = -2;
System.out.println(((Integer)b).hashCode());
double c = 3.1415926;
System.out.println(((Double)c).hashCode());
String d = "hashCode";
System.out.println(d.hashCode());
}
}
2
-2
219937201
147696667
如果用户想对于自定义的类也能转换为相对应的哈希函数，则只需在类中覆盖来自于Object父类的hashCode方法。
public class Student {
int grade;
int cls;
String name;
Student(int grade,int clas,String name){
this.grade = grade;
this.cls = cls;
this.name = name;
}
@Override
public int hashCode(){
int B = 31;//将此类的看成有三个作用域的复合类型，直接把三部分看成三个数字，符合类型看成由这三个部分组成的B进制的数，进制数可以自己定义；
int hash = 0;
hash = hash * B + grade;
hash = hash * B + cls;
hash = hash * B + name.hashCode();
//如果出现整型溢出，计算机会做处理，这样不满足数学上的规范，不过对于计算机仍然是有效的
return hash;
}
}
Student student = new Student(100,20,"homxu");
System.out.println(student.hashCode());
99557671
当一个类能够获得其hash值之后，便能够使用java提供的对于hash的操作。如java.util.HashSet和java.util.HashMap
HashSet<Student> set = new HashSet<>();
set.add(student);
HashMap<Student,Integer> scores = new HashMap<>();
scores.put(student,100);
当然，如果一个类没有自定义其hashCode方法，那么会使用默认的方法，默认方法是将对象的地址映射成一个整型值。所以，当new出来两个数值相同的对象时，他们的hashCode值也是不同的。
在自定义hashCode方法的时候，如果传过去的值相等，那么可能会产生hash冲突，所以一般还要在重写一个Object的equals()方法。以上面的Student类为例。
@Override
public boolean equals(Object o){ //注意这里的参数是object类型
if(this == o)
return true; //如果是同一个引用，则直接返回true
if(o == null)
return false;
if(getClass() != o.getClass())
return false; //如果类不同，返回false
Student another = (Student)o;
return this.grade == another.grade &&
this.cls == another.cls &&
this.name.equals(another.name);
}
这样，如果产生了hash冲突，即使是一样的hash值，也可以区分两个类对象的不同。
链地址法(Seperate Chaining)
链地址法是哈希冲突的一种处理方法。 由之前的内容可知道，在处理哈希值的存储的时候，其实就是将对应的整数取模后，这个值就对应它在数组中的索引。对于会产生负号的值，则进行取绝对值或者(hashCode(value) & 0x7fffffff) % M(按位与进行取负号，效果和取绝对值一样)。
假设产生了哈希冲突，本来索引为1的位置已经存在了元素v1,后来新元素v2也和v1的索引一致，那么这时候扔把v2放在v1的位置，也就是索引处存放的是一个链表，每个索引位置存的都是一个链表，所以Seperate Chaining也由此得名。 当然，每一个位置的本质其实是存放的一个查找表，查找表不一定非要用链表，也可以用平衡树结构来实现这个查找表，所以每个位置也可以是一个查找表的结构。在产生哈希冲突时，找到对应的索引位置，然后插入到所以位置对应的TreeMap就可以了。HashMap本质就是一个TreeMap数组。HashSet就是一个TreeSet数组。
在Java8之前，每一个索引位置对应的就是一个链表。 Java8开始，当哈希冲突达到一定的程度时，每个位置从链表转为红黑树(即TreeMap，因为Java8的TreeMap底层实现就是红黑树)。
实现一个哈希表
实现一个简单的哈希表，包括增删改查等
import java.util.TreeMap;
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;//将key值转变为当前哈希表中的索引
}
public int getSize(){
return size;
}
//哈希表的添加操作
public void add(K key,V value){
TreeMap<K,V> map = hashtable[hash(key)]; //先用map暂存当前的hashtable索引对应的TreeMap
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);
}
}
当然，对于这个简单实现的哈希表，其M值是开始已经确定好的。选取合适的M值将对哈希表的性能有很大的影响。
时间复杂度和动态空间处理
在前面的介绍中，假设哈希表有M个地址，如果向其中放入N个元素，那么每个地址平均有N/M个元素。如果每个地址是链表，那么时间复杂度为O(N/M)。如果每个地址是一个平衡树，那么时间复杂度为O(log(N/M))。
哈希表的目的是为了让时间复杂度为或者接近O(1).如果N趋于无穷大的话，那么对于一个静态的数组，它总会产生哈希冲突。所以一个解决办法就是使用动态存储，使其进行自适应。所以和静态数组一样，固定的地址空间是不合理的，所以需要resize操作。但是哈希表的动态操作又和静态数组不同，哈希表的每个索引位置存放的是一个链表或者一个树，如果是链表，那么它是不存在这个位置被“填满”的概念的。所以这里需要考虑的是，平均每个地址承载的元素多过一定的程度，即进行扩容，可以将容忍度定义为upperTol,当N/M >= upperTol时，进行扩容。同理，平均每个地址承载的元素少过一定程度就进行缩容：N / M < lowerTol.
import java.util.TreeMap;
public class HashTable<K,V> {
private static final int upperTol = 10; //定义upperTol
private static final int lowerTol = 2; //定义lowerTol
private static final int initCapacity = 7; //定义初始的大小
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(initCapacity);
}
private int hash(K key){
return (key.hashCode() & 0x7fffffff) % M;//将key值转变为当前哈希表中的索引
}
public int getSize(){
return size;
}
//哈希表的添加操作
public void add(K key,V value){
TreeMap<K,V> map = hashtable[hash(key)]; //先用map暂存当前的hashtable索引对应的TreeMap
if(map.containsKey(key))//如果对应的索引处包含了当前的元素
map.put(key,value);
else{
map.put(key,value);
size ++;
if(size >= upperTol * M) //平均每个地址承载的元素多过一定的程度,即N / M >= upperTol
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) //平均每个地址承载的元素少过一定的程度,即N / M <= lowerTol；并且缩容时的空间至少为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; //暂存一下之前的M,在循环时作为循环边界
this.M = newM; // 注意hash(key)是对之前的M进行取模，这里要让M变为newM，对现在的M进行取模
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)
对于哈希表，元素数从N增加到upperTol * N ，地址空间翻倍。平均复杂度O(1).每个操作在O(lowerTol) ~ O(upperTol) → O(1)。 缩容同理
在扩容时有一个问题，对于素数M，如果进行扩容，那么扩容后2*M不是素数。其中一个解决方案是，按照素数表中的数字进行扩容，而不是简单的二倍关系。
当然哈希表的均摊复杂度虽然为O(1)，但是它与平衡树结构相比丢失了数据的顺序性。
这样回顾集合和映射的底层实现，如果想实现有序集合和有序映射，那么底层可使用平衡树；如果实现无序集合和无序映射，则使用哈希表。
import java.util.TreeMap;
public class HashTable<K,V> {
private 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; //定义upperTol
private static final int lowerTol = 2; //定义lowerTol
private int capacityIndex = 0; //定义capacity数组初始的索引
private TreeMap<K,V>[] hashtable;
private int M;
private int size;
public HashTable(){
this.M = capacity[capacityIndex];
size = 0;
hashtable = new TreeMap[M];
for(int i = 0 ; i < M ; i ++)
hashtable[i] = new TreeMap<>();
}
private int hash(K key){
return (key.hashCode() & 0x7fffffff) % M;//将key值转变为当前哈希表中的索引
}
public int getSize(){
return size;
}
//哈希表的添加操作
public void add(K key,V value){
TreeMap<K,V> map = hashtable[hash(key)]; //先用map暂存当前的hashtable索引对应的TreeMap
if(map.containsKey(key))//如果对应的索引处包含了当前的元素
map.put(key,value);
else{
map.put(key,value);
size ++;
if(size >= upperTol * M && capacityIndex + 1 < capacity.length){ //平均每个地址承载的元素多过一定的程度,即N / M >= upperTol,并且判断边界不会越界
capacityIndex ++;
resize(capacity[capacityIndex]);
}
}
}
//哈希表的删除操作
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 && capacityIndex - 1 >= 0) {//平均每个地址承载的元素少过一定的程度,即N / M <= lowerTol；并且缩容时不会越界
capacityIndex --;
resize(capacity[capacityIndex]);
}
}
return ret;
}
//哈希表的修改操作
//同原来的函数
//哈希表的查询操作
//同原来的函数
private void resize(int newM){
//同原来的函数
}
}
彩蛋
上述的代码实现中，HashTable的K值是不要求可比较的(Comparable)，但是在使用TreeMap定义hashtable数组时，TreeMap的K是要求可比较的，所以这是一个小bug。
前面提到 在Java8之前，每一个索引位置对应的就是一个链表。 Java8开始，当哈希冲突达到一定的程度时，每个位置从链表转为红黑树(即TreeMap，因为Java8的TreeMap底层实现就是红黑树)，当然，这种情况要求HashTable的K值是可比较的，不然它的每个索引仍然对应一个链表。