哈希表,我们平时好像用到的不多,使用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.再散列法:建立多个不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。
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对象保存进数组中。