算法：哈希表HashTable-理论
哈希表，我们平时好像用到的不多，使用HashMap的时候，才间接的使用到了，在信息安全领域用到的比较多（文件效验、数字签名），下面我们先来看看哈希函数。
哈希函数：将任意长度的数据映射到有限长度的域上，就是对一串数据m进行杂糅，输出另一段固定长度的数据h，作为这段数据的特征。类似的MD5算法也是一种哈希函数。
例如String.hashCode
package java.lang.String;
private int hash; // Default to 0
private final char value[];/** The value is used for character storage. */
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}通过这个String的哈希函数，我们可以得到一个字符串的哈希值。
当我们建立一张表，通过哈希运算得到一个固定长度的值，把字符串和哈希值一一对应上，这张表就叫做哈希表。
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
例如下面这张图，哈希函数为：key=(字母ASCII码相加）取30的模。
我们设计的哈希函数太过于简单，那么通过哈希运算后得到的值等于20的还有很多（foes等等），类似的，当一个哈希值不唯一对于一个数据时，我们称发生了哈希碰撞。
解决哈希碰撞有几种方法，方法很多，下面只是列举常用的。
1.例如上图，在发生碰撞的位置建立链表，把数据分别存入链表中，这种方法叫做拉链法。
2. 开放寻址法：Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）为散列函数，m为散列表长，di为增量序列。
3.再散列法：建立多个不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。
Java中的hashtable是怎么实现的？
public Hashtable() { //构造函数
this(11, 0.75f);
}
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity]; //创建一个Entry数组，保存键值对。
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
private static class Entry<K,V> implements Map.Entry<K,V> { //主要保存的对象的地方
final int hash;
final K key;
V value;
Entry<K,V> next;
...//getKey、getValue、setValue、equals、hashCode、toString方法。
}
public synchronized V put(K key, V value) { //添加方法
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table; //初始化时，生成的对象
int hash = key.hashCode(); //获取key的哈希值
int index = (hash & 0x7FFFFFFF) % tab.length; //位运算，获取数组下标
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) { //判断当前下标数组是否为空，即哈希冲突
if ((entry.hash == hash) && entry.key.equals(key)) { //链接法，解决哈希冲突
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index); //没哈希冲突，调用
return null;
}
private void addEntry(int hash, K key, V value, int index) { //实际添加方法
modCount++;
Entry<?,?> tab[] = table;
if (count >= threshold) { //数组是否有空间
// Rehash the table if the threshold is exceeded
rehash(); //扩容
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index]; //下一个Entry先设置为空
tab[index] = new Entry<>(hash, key, value, e); //保存键值对数据到Enetry对象，并设置Next下一个为空。
count++;
}HashTable 的实现，先创建Entry数组，Entry对象负责保存数据。put方法，先检查保存前的必要检查工作，后面调用实际添加数据方法；如果检查到哈希冲突，则通过链接法解决哈希冲突；调用实际添加数据方法中需要检查数组是否有空间，是否需要扩容，以及保存数据生成Entry对象，讲生成的Entry对象保存进数组中。
腾讯云开发者
