----------------------数据结构之哈希表-------------
哈希函数：将一个字符转换为对应的索引，比如只处理小写字符与数组中索引的对应关系，可以写为f(ch) = ch - ‘a’
哈希函数：键转换为索引
哈希函数设计和哈希冲突如何解决以及hash后如何均匀分布？
设计原则：
HashMap本质就是一个TreeMap的数组
HashSet 本质就是一个TreeSet的数组
hash表的动态空间处理：
共N个元素，数组空间为M，当N/M >= upperTol：即平均冲突数大于等于容忍上线时进行扩容。 N/M < lowerTol时进行缩容。
哈希表提升了性能，牺牲了顺序性。
像二分搜索树和AVL树等都有很好的顺序
集合和映射可以分为：1）有序集合、有序映射；2）无序集合、无序映射
有序集合、有序映射（TreeMap、TreeSet）：底层通过平衡树实现
无序集合、无序映射(HashMap、HashSet)：底层通过HashTable哈希表实现
HashTable实现如下：
package hashTable;
import java.util.Map;
import java.util.TreeMap;
public class HashTable<K, V> {
private static final int upperTol = 10;
private static final int lowerTol = 2;
private static final int initCapacity = 7;
private TreeMap<K, V>[] hashtable;
private int size;
private int M;
public HashTable(int M){
this.M = M;
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 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 ++;
if(size >= upperTol * M)
resize(2 * M);
}
}
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 && M > initCapacity)
resize(M / 2);
}
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);
}
private void resize(int newM){
TreeMap<K, V>[] newHashTable = new TreeMap[newM];
for(int i = 0 ; i < newM ; i ++)
newHashTable[i] = new TreeMap<>();
for(int i = 0 ; i < M ; i ++)
for(K key: hashtable[i].keySet())
newHashTable[hash(key)].put(key, hashtable[i].get(key));
this.M = newM;
this.hashtable = newHashTable;
}
}
java8之前，hashTable中数组的每一个位置对应一个链表，而从java8开始，每一个位置开始是链表，当hash冲突达到一定程度时，每一个位置从链表转换为红黑树，但是转换为红黑树也是有条件的：
由于红黑树是有顺序的，要求存储的对象是可排序的，而链表是不要求存储的对象有顺序，那么当hash冲突达到一定成都时，会先进行判断，如果存储的对象是可比较的，才会由链表转换为红黑树；如果存储的对象不可比较，则每个位置仍然以链表的形式存在。
数据结构总结：
线性结构：动态数组、普通队列、栈、链表
树形结构：二分搜索树、AVL树、红黑树
其他二叉树：堆、线段树
多叉树：Trie、并查集
hash表也可归于线性结构中
抽象数据结构：
线性表：动态数组、链表
栈、队列：可以用动态数组、链表实现，以及优先队列可以用堆实现
集合、映射 又可以分为有序集合、有序映射、无序集合、无序映射
原文：https://www.cnblogs.com/xiao1572662/p/12131992.html