如果把我们的字典看成一个大线性表的话, 也没有任何问题, 不过随着字典的扩大, 我们会发现, 这和现实中为了寻找一个词语的解释, 一页一页翻字典没有任何区别.
也就是说, 我们的字典看上去叫字典, 也实现了字典的接口, 但是在内部, 没有实现一本字典应该有的索引功能.
因此, 我们会想, 如果有一个索引函数, 我把Key放进去, 运算出来的结果就是一个索引, 然后直接操作索引位置的对象就可以了, 这才是完备的字典.
这个想法确实是对的, 有这么一种函数, 就是散列函数. 当然, 也许工作的不想想象的那样完美, 但可以大大的提高查找效率.
散列表实现的字典
对于我们的字典, 散列函数的核心思想就是: 根据传入的对象, 计算得到对象在数组中的元素下标.
所以这个函数的本质, 就是将一组事物, 映射到一排整数上去.
如果每个事物都可以映射到不同的整数上去, 这个就叫做完美散列函数. 将一个事物通过散列函数计算得到的整数称为散列码.
完美散列函数的一大问题是, 如果这组事物很多, 则需要的散列表空间也非常大, 至少在编号方面非常大.
所以在很多时候, 可能还需要把散列码压缩到数据结构可实际使用的空间中去, 比如一个对象的散列码计算得到-10, 就不能直接用这个散列码来操作, 还需要为-10这个散列码寻找在数组中的对应位置.
此外, 在计算散列码的时候(或者说直到计算出最终下标)的过程中, 有些不同的对象映射到同一个下标, 这个叫做冲突.
这里先不讨论如何解决冲突, 而是肯定有一个冲突解决方案来做这个工作.
这样我们就初步整理出来了使用散列表的几个核心要素:
- 散列函数和散列码
- 散列码换算成下标
- 冲突解决方案
Java中的基类Object有一个方法叫做hashCode(), 就是散列函数, 计算得到一个int类型的整数, 就是散列码. 不过, 如果不覆盖这个方法, 默认的实现是返回这个对象所在的内存地址当做散列码.
默认的内存地址不实用, 因为当指针指向另外一个对象的时候, 内存地址相同, 但对象发生了变化, 因此很难通过散列码来判断对象的相等性.
Java对此有一些严格的规定, 即判断相等性equals()和hashCode()的方法, 在编写自己的类时候尤其要注意:
- 如果一个类重写了equals(),也必须重写hashCode()
- 如果两个对象equals()的结果是true, 则hashCode()的结果也必须相等
- 一个对象不管调用多少次hashCode(), 只要对象未改变, 结果都一样
散列函数
由上边分析可见, 散列函数非常重要, 好的散列函数可以大大减少之后压缩下标, 解决冲突的难度.
来看一下Java中是如何计算散列函数的.
字符串散列函数
字符串散列函数的Horner方法是, 反复乘再加, 不好说但是一看代码就明白. 根据这个方法, 可以选择一个常数, 来编写一个散列函数:
public static int hashString(String s) {
//所选择的常数
int A = 31;
//初始hash码
int hash = 0;
for (int i = 0; i < s.length(); i++) {
//每次用常数乘以hash码,再加上当前字符的unicode值
hash = hash * A + s.charAt(i);
}
return hash;
}
这里我们的例子选择了31, 这是因为Java的String类的hashCode()方法选择的就是31. 所以我们的散列函数计算出来的结果和Java是一样的. 不信可以试试.
基本类型的散列函数
对于长度不超过int的整数类型 byte short char int, 直接可以将其转换为int就得到散列码, 数字的唯一性保证了散列码的唯一性.
float类型很有意思, 由于其内部就是一个32位的二进制数表示, 因此可以直接将其转换成 32位 相同规格的int即可, 注意这和转换类型可不同.
需要使用Float.floatToRawIntBits(a)来将其转换成原样的二进制码对应的int, 这也保证了唯一性.
对于long和Double,我们马上就可以判定, 如果将散列码扩展到64位, 则可以用同样的方式保证唯一性.
不幸的是散列码是int类型,因此需要压缩一下, 采用的方法是将64位的前32位和后32位进行异或运算, 得到32位长度的散列码. 写成方法就是:
public static int hash64BitDate(long s) {
return (int) ((s >> 32) ^ s);
}
对于Double类型, 则要稍微做点变更,不能直接移位, 而要先转换成原始的二进制对应的long:
public static int hash64BitDate(double s) {
return hash64BitDate(Double.doubleToLongBits(s));
}
上边的这些函数, 手工计算结果和调用包装类的hashCode方法,结果是一样的.
对于普通对象的散列码, 则需要在编写对象的时候想一个方法来进行编写, 一般可以使用对象中各个数据域的散列码来进行计算.
还一个常见的操作是, 因为计算散列码需要时间, 因此可以设置一个布尔变量来表示散列码是否已经被计算出来, 如果对象的数据发生变化, 则重新计算散列码, 否则直接返回已经计算好的散列码即可.
下标压缩
散列码都是int类型的值, 给了我们一个启示, 就是可以将其压缩到一个数字序列中. 只要选定一个素数, 然后取散列码除以该素数的余数, 就可以将散列码映射到 0 – (素数-1) 范围内.
很容易想到, 如果选择其他数字或者偶数, 则出现重复下标的概率大大提高, 所以n要是奇数, 最好的选择就是某个素数了.
知道了散列码如何计算, 以及如何将散列码压缩至下标, 剩下就需要解决一个问题, 就是两个不同的散列码压缩到同一个下标的时候, 该如何处理. 所以就来研究如何解决冲突.
解决冲突
这里我们先跳过线性探查, 而是专注于拉链法 – 即需要改变字典的内部数据结构.
所谓改变结构, 也就是让线性表的每一个位置, 都可以来存入多个元素, 这只需要把线性表的每一个元素, 也改成一个存放Entry的数据结构.
这个数据结构可以是之前用过的数组, 线性表, 向量等等都可以, 只要支持查找和替换操作, 一般来说, 使用链表组成的线性表会比较方便, 因为不会占用额外空间.
所以实际上, 通过散列表, 有效的减少了操作一条长链的可能性, 将每个查找, 都对应到一条相比整个字典短的多的链条上, 这样查找效率就会大大提高.
这样, 散列表的内部结构, 就变成了一个线性表数组, 这是很有意思的. 看起来已经可以写一个散列表了.
装填因子
这里我们依然关心拉链法. 装填因子 load factor, 就是散列表中已经存储的总项数 / 散列表中的位置数.
对于拉链法来说, 散列表的位置数并不是指总的位置数, 因为链表是可伸缩的, 而是指将散列码要压缩到的范围. 所以对于拉链法来说, 可能存了100个数字, 但是依然每次只有0-16这17个下标,所以没有上限.
然而, 装填因子却影响着查找效率. 拉链法下, 很显然, 设装填因子=A, 则实际上A是线性表数组每一项里边的线性表中的平均元素个数.
根据我们的算法, 对象会被一个常数级别的运算计算出散列码, 然后被常数级别的运算计算出下标. 之后影响性能的就是在A个元素中的查找能力. 先看第一个情况:
查找不成功
查找不成功意味着最后没有找到任何一个键和给出的键对应. 很显然, 在两个常数操作之后, 面对的平均情形就是一个长度为A的链表, 只有检查完全部节点之后, 才能得出查找不成功的结论, 所以查找不成功的次数是A.
查找成功
查找成功到确定下标之前, 也是常数操作, 之后面临和查找不成功一样的境地, 即一个长度为A的链表, 很显然, 要么第一个就查到, 即花费1, 要么最后一个才查到, 因此平均时间是1 + A/2.
这样, 在给定的线性表大小和放入元素的个数之后(也就是装填因子), 就可以计算出来查找所需的时间的粗略关系.
经过计算, 从A=0.1开始, 随着不断增大装填因子, (也就是线性表装的东西越来越多), 不成功查找所需的时间的增加量会大于成功查找的增加量. 一般将装填因子维持在1以内比较好, 如果超过, 则应该将线性表数组扩展到下一个素数.
有了这些理论, 就可以来写出一个散列表了. 当然, 散列函数可能还是需要我们自行设计. 但是这里可以先以最常见的字符串散列表为例.
拉链法实现散列表
根据上边的需求, 自己先来编写一个简单的拉链法字典, 先搭建一个基础设施:
public class ZipDictionary<K, V> implements Dictionary<K, V> {
private MyLinkedList<Entry<K, V>>[] dictionary;
private static int DEFAULT_CAPACITY = 17;
private int numberOfEntries;
@SuppressWarnings("unchecked")
public ZipDictionary() {
dictionary = new MyLinkedList[DEFAULT_CAPACITY];
}
private class Entry<K, V> {
K key;
V value;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return "Entry{" +
"key=" + key +
", value=" + value +
'}';
}
@Override
@SuppressWarnings("unchecked")
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Entry<?, ?> entry = (Entry<?, ?>) o;
return key.equals(entry.key);
}
@Override
public int hashCode() {
return key.hashCode();
}
}
}
基础设施包括了一个数组, 每一个元素都是一个链表实现的线性表. 还有老朋友Entry. 下边一个一个来编写各个方法.
首先是核心的add()方法.
@Override
public void add(K key, V value) {
if (key == null || value == null) {
throw new RuntimeException("不允许添加null.");
}
Entry<K, V> newEntry = new Entry<>(key, value);
//关键步骤, 根据键的散列码压缩下标
int index = Math.abs(newEntry.hashCode() % dictionary.length);
//如果为空就先创建线性表, 然后添加
if (dictionary[index] == null) {
dictionary[index] = new MyLinkedList<>();
dictionary[index].add(newEntry);
} else {
//如果不为空, 需要先探查有没有这个东西
int result = dictionary[index].getPosition(newEntry);
//如果没找到, 就直接添加, 可以考虑添加在头部, 这样下一次查找会比较快
if (result == -1) {
dictionary[index].add(0, newEntry);
} else {
//如果找到了, 就替换指定位置的元素
dictionary[index].replace(result, newEntry);
}
}
}
接下来是remove()方法. 逻辑依然是先计算散列码再查找:
@Override
@SuppressWarnings("unchecked")
public V remove(K key) {
int index = Math.abs(key.hashCode() % dictionary.length);
System.out.println("键的散列码是: " + index);
Entry<K, V> target = new Entry<>(key, (V) new Object());
if (dictionary[index] == null) {
return null;
} else {
int result = dictionary[index].getPosition(target);
System.out.println("具体链表的索引是: " + result);
if (result == -1) {
return null;
} else {
V value = dictionary[index].getEntry(result).value;
dictionary[index].remove(result);
return value;
}
}
}
然后是通过键获取值, 如出一辙:
@Override
@SuppressWarnings("unchecked")
public V getValue(K key) {
int index = Math.abs(key.hashCode() % dictionary.length);
Entry<K, V> target = new Entry<>(key, (V) new Object());
if (dictionary[index] == null) {
return null;
} else {
int result = dictionary[index].getPosition(target);
if (result == -1) {
return null;
} else {
return dictionary[index].getEntry(result).value;
}
}
}
之后是contains(), 还是一样的操作:
@Override
@SuppressWarnings("unchecked")
public boolean contains(K key) {
int index = Math.abs(key.hashCode() % dictionary.length);
Entry<K, V> target = new Entry<>(key, (V) new Object());
if (dictionary[index] == null) {
return false;
} else {
return dictionary[index].getPosition(target) != -1;
}
}
最后是几个辅助函数, 编写都依赖于每个链表:
@Override
public boolean isEmpty() {
int sum = 0;
for (MyLinkedList<Entry<K, V>> entries : dictionary) {
if (entries != null) {
sum = sum + entries.getLength();
}
}
return sum == 0;
}
@Override
public int getSize() {
int sum = 0;
for (MyLinkedList<Entry<K, V>> entries : dictionary) {
if (entries != null) {
sum = sum + entries.getLength();
}
}
return sum;
}
@Override
public void clear() {
Arrays.fill(dictionary, null);
}
现在只剩下迭代器了. 迭代器我能想到的一个方法就是遍历一遍然后组装一个数组, 让迭代器去使用. 单独控制一个数量i也可以, 但是每次要一个一个往前走, 似乎写起来非常麻烦. 这里我就组装了一个数组然后返回一个迭代器对象, 先看键迭代器:
@Override
public Iterator<K> getKeyIterator() {
return new KeyIterator();
}
private class KeyIterator implements Iterator<K>{
private K[] array;
private int index;
private int number;
@SuppressWarnings("unchecked")
KeyIterator() {
this.index = 0;
this.number = getSize();
array = (K[]) new Object[number];
int i = 0;
//这里实际上把当前所有Key都装进了新创建的数组, 然后实际上是在这个数组中迭代
for (MyLinkedList<Entry<K, V>> list : dictionary) {
if (list != null) {
for (Entry<K, V> entry : list) {
array[i] = entry.key;
i++;
}
}
}
}
@Override
public boolean hasNext() {
return index != number;
}
@Override
public K next() {
K result = array[index];
index++;
return result;
}
}
会编写键的迭代器了, 值的也一样:
@Override
public Iterator<V> getValueIterator() {
return new ValueIterator();
}
private class ValueIterator implements Iterator<V>{
private V[] array;
private int index;
private int number;
@SuppressWarnings("unchecked")
ValueIterator() {
this.index = 0;
this.number = getSize();
array = (V[]) new Object[number];
int i = 0;
for (MyLinkedList<Entry<K, V>> list : dictionary) {
if (list != null) {
for (Entry<K, V> entry : list) {
array[i] = entry.value;
i++;
}
}
}
}
@Override
public boolean hasNext() {
return index != number;
}
@Override
public V next() {
V result = array[index];
index++;
return result;
}
}
这样一个固定长度的字典基本上就写好了. 不过这里没有编写长度发生改变的方法.
添加长度变更功能
长度发生改变的话, 就需要在每次add方法之前, 判断装填因子是不是超过一定的数量, 也就是用getSize()/dictionary.length, 如果大于一个数字, 就要扩充到下一个素数的位置,
还会需要一些辅助的素数行列来控制大小和上限, 这里对原来的类进行一些修改, 在add方法添加元素之前, 增加一个扩大数组的方法.
这里需要修改一下整个类的一些设施, 将原来的那个静态变量DEFAULT_CAPACITY去掉, 记录当前数组的长度(其实这个变量也可以省略, 不过为了简明, 就写出来),然后就可以来编写辅助域和方法, 用于在add()添加元素之前扩大数组长度:
public class ZipDictionary<K, V> implements Dictionary<K, V> {
private int capacity = 17;
private static int[] primeNumbers = new int[]{37, 79, 151, 307, 617, 1237, 2477, 4957, 10007};
@Override
public void add(K key, V value) {
if (key == null || value == null) {
throw new RuntimeException("不允许添加null.");
}
checkSize();
Entry<K, V> newEntry = new Entry<>(key, value);
int index = Math.abs(newEntry.hashCode() % dictionary.length);
if (dictionary[index] == null) {
dictionary[index] = new MyLinkedList<>();
dictionary[index].add(newEntry);
} else {
int result = dictionary[index].getPosition(newEntry);
if (result == -1) {
dictionary[index].add(0, newEntry);
} else {
dictionary[index].replace(result, newEntry);
}
}
}
@SuppressWarnings("unchecked")
private void checkSize() {
double loadFactor = (double) getSize() / dictionary.length;
System.out.println("当前的装填因子是: " + loadFactor);
if (loadFactor > 0.7) {
for (int primeNumber : primeNumbers) {
if (primeNumber > capacity) {
capacity = primeNumber;
System.out.println("将容量增大到: " + capacity);
//用一个临时引用保存原来的内部数据结构
MyLinkedList<Entry<K, V>>[] temp = dictionary;
//然后创建一个长度扩大的数组作为新字典的内部数据结构
dictionary = new MyLinkedList[capacity];
//由于是散列, 不能直接复制, 所以只好一个一个把原来的散列表的内容装载到新的散列表中.
loadDataToNewDictionary(temp);
break;
}
}
}
}
private void loadDataToNewDictionary(MyLinkedList<Entry<K, V>>[] array) {
for (MyLinkedList<Entry<K, V>> list : array) {
if (list != null) {
for (Entry<K, V> entry : list) {
add(entry.key, entry.value);
}
}
}
}
}
checkSize()方法检测当前的装填因子是不是已经大于0.7, 只要大于, 就在素数表中搜索下一个大于capactiy的素数, 并将capacity设置成这个素数.
然后创建一个引用指向原来的内部链表数组, 将dictionary的引用替换成新的capacity大小的空白数组, 然后使用一个辅助方法, 将原来链表数组中的所有元素, 重新添加到新的散列表中.
这里可不能像之前线性表一样重新复制, 因为散列表压缩之后的下标会变化. 这个要特别注意. 上限就是10007, 即数组最大也就扩大到10007长度, 之后便不再扩大散列表了.
经过了一下午, 终于完整的写出了拉链法还能够扩大的散列表了, 在扩大散列表的时候, 是一个O(n)的操作. 在正常取散列表的时候, 假设装填因子是0.7, 说明平均每个位置只有0.7个元素, 由于散列过程可以看做是常数, 所以散列表的性能相比线性表,可就非常快了.
所以最后来写一个小实验, 比一下究竟两者性能差多少.
public static void main(String[] args) {
Random random = new Random();
ZipDictionary<String, String> dictionary1 = new ZipDictionary<>();
for (int i = 0; i < 10000; i++) {
dictionary1.add(String.valueOf(i), String.valueOf(i * 3));
}
LinearDictionary<String, String> dictionary2 = new LinearDictionary<>();
for (int i = 0; i < 10000; i++) {
dictionary2.add(String.valueOf(i), String.valueOf(i * 3));
}
String[] indexNumbers = new String[1024*1024];
for (int i = 0; i < indexNumbers.length; i++) {
indexNumbers[i] = String.valueOf(random.nextInt(10000));
}
long start = System.currentTimeMillis();
for (int i = 0; i < indexNumbers.length; i++) {
dictionary1.getValue(indexNumbers[i]);
}
long end = System.currentTimeMillis();
System.out.println("拉链法字典查找时间是: " + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < indexNumbers.length; i++) {
dictionary2.getValue(indexNumbers[i]);
}
end = System.currentTimeMillis();
System.out.println("线性表字典查找时间是: " + (end - start));
}
测试首先给长度10000的拉链法字典和线性表字典各装入10000个键值对, 键就是0-9999的字符串, 值是键乘以3的字符串.
然后准备了长度为1M的键数组, 放了所有随机生成的键.
之后让两个程序挨个搜索键数组, 比较完成这1M次数的时间.
运行了几次如下:
拉链法字典查找时间是: 82 线性表字典查找时间是: 28842 拉链法字典查找时间是: 80 线性表字典查找时间是: 28567 拉链法字典查找时间是: 86 线性表字典查找时间是: 29866
可以看到, 性能差距在350倍左右. 这确实是一个巨大的进步.
