理想中的hash table仅仅是包含元素的固定大小的数组，有用来查询的key和数据字段value，我们假设表的大小为TableSize。
每一个key被映射到0到TableSize-1区间，并替换数组适当的单元格。这种映射方法叫hash函数，我们希望这个映射方法应该简单，并且能够让不同的key获得不同的hash值，然而由于我们有有限的单元格，但却需要支持无尽的key，显然是不可能的，因此我们需要找到一种hash函数，能够将key映射均匀的在这些单元格中。最后，当不同的key映射到相同的值时（通常称之为冲突），我们如何处理？
Hash Function
假如key是整型数值时，没有特殊情况的话，直接返回key mod TableSize即可。比如如果大小为10，但key又都是以0结尾的，那么这种方式显然不合理了。为了防止这种情况发生，我们通常设置TableSize为一个素数。
当key为字符串时，就需要多多考虑这个函数应该如何设计了。一种方式是将每一个字符的ASCII码相加:
public class Hashing {
public static int hash(String key, int tableSize) {
int hashVal = 0;
for(int i = 0; i<key.length(); i++) {
hashVal += key.charAt(i);
}
return hashVal % tableSize;
}
}
这种方式简单快捷，但是当TableSize很大的时候，这个方法无法均匀的分布key。例如当大小为10007（素数）。假设key的长度为8或者更小，由于ASCII最大只有127因此key最多分布在1到1016之间。
另一种方式如下：
public static int hash(String key, int tableSize) {
return (key.charAt(0) + key.charAt(1) * 27 +key.charAt(2) * 729) % tableSize;
}
假设key至少有三个字符，27代表英文的字母和一个空格，729是27的平方。这个方法仅仅考虑key的前3个字符，如上所述，虽然263=17576,但英文单词并不是完全随机的，通过字典可以查到常用的单词也就2851个，即使这些完全没有碰撞，但只有28%的区间被映射到，因此这个方法也是不太适合的。
那么我们可以将所有的字符都考虑进来，并生成一个和质数相关的多项式，同时也要考虑可能存在溢出的情况：
public static int hash(String key, int tableSize) {
int hashVal = 0;
for( int i = 0; i<key.length(); i++) {
hashVal = 37 * hashVal + key.charAt(i);
}
hashVal = hashVal % tableSize;
if( hashVal < 0) {
hashVal += tableSize;
}
return hashVal;
}
当然这种方式也不一定是最优的，并且如果key特别长的话将会耗费大量的时间，我们可以看到JDK中字符串的hashcode的实现方式是:
public static int hashCode(byte[] value) {
int h = 0;
int length = value.length >> 1;
for(int i = 0; i < length; ++i) {
h = 31 * h + getChar(value, i);
}
return h;
}
剩下的就是需要解决冲突问题了，当两个key有相同的hash结果时，将会发生冲突。有很多种方法来解决这个问题，最主要的两种是独立链表和开放式寻址。
独立链表
第一种方式是独立链表（separate chaining），将所有相同hash值存放在一个链表中。通过使用hash函数来决定在哪个链表中进行遍历，来实现查找。当插入值时，我们hash函数计算后，如果已经有值，就在该值得头部插入，因为通常最近插入的使用会更频繁。
import java.util.LinkedList;
import java.util.List;
/**
* @author dalu
* @create 2020-04-12 22:01
*/
public class SeparateChainingHashTable <AnyType> {
public SeparateChainingHashTable() {
this(DEFAULT_TABLE_SIZE);
}
public SeparateChainingHashTable(int size) {
theLists = new LinkedList[nextPrime(size)];
for(int i = 0; i < theLists.length; i++) {
theLists[i] = new LinkedList<>();
}
}
public void insert(AnyType x) {
List<AnyType> whichList = theLists[myhash(x)];
if( !whichList.contains(x)) {
whichList.add(x);
if(++currentSize > theLists.length) {
rehash();
}
}
}
public void remove(AnyType x) {
List<AnyType> whichList = theLists[myhash(x)];
if(whichList.contains(x)) {
whichList.remove(x);
currentSize--;
}
}
public boolean contains(AnyType x) {
List<AnyType> whichList = theLists[myhash(x)];
return whichList.contains(x);
}
public void makeEmpty() {
for(int i = 0; i < theLists.length; i++) {
theLists[i].clear();
}
currentSize = 0;
}
private static final int DEFAULT_TABLE_SIZE = 101;
private List<AnyType> [] theLists;
private int currentSize;
private void rehash() {
List<AnyType> [] oldLists = theLists;
theLists = new List[nextPrime(2 * theLists.length)];
for(int j = 0; j < theLists.length; j++) {
theLists[j] = new LinkedList<>();
}
currentSize = 0;
for(int i = 0; i < oldLists.length; i++) {
for(AnyType item : oldLists[i]) {
insert(item);
}
}
}
private int myhash(AnyType x) {
int hashVal = x.hashCode();
hashVal %= theLists.length;
if(hashVal < 0) {
hashVal += theLists.length;
}
return hashVal;
}
private static int nextPrime(int n) {
if(n % 2 == 0) {
n++;
}
for(; !isPrime(n); n += 2) {
}
return n;
}
private static boolean isPrime(int n) {
if(n == 2 || n == 3) {
return true;
}
if(n == 1 || n % 2 == 0) {
return false;
}
for(int i = 3; i * i <= n; i += 2) {
if(n % i == 0) {
return false;
}
}
return true;
}
}
