容器深入研究（8）：散列与散列码（下）
三、为速度而散列
SlowMap.java说明了创建一种新的Map并不困难。但是正如它的名称SlowMap所示，它不会很快，所以如果有更好的选择，就应该放弃它。它的问题在于对键的查询，键没有按照任何特定的顺序保存，所以只能使用简单的线性查询，而线性查询是最慢的查询方式。
散列的价值在于速度：散列使得查询得以快速进行。由于瓶颈位于键的查询速度，因此解决方案之一就是保持键的排序状态，然后使用Collections.binarySearch()进行查询。
散列则更进一步，它将键保存在某处，以便能够很快找到。存储一组元素最快的数据结构是数组，所以使用它来表示键的信息（请小心留意，我是说键的信息，而不是键本身）。但是因为数组不能调整容量，因此就有一个问题：我们希望在Map中保存数量不确定的值，但是如果键的数量被数组容量限制了，该怎么办？
答案就是：数组并不保存键本身。而是通过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码，由定义Object中的、且可能由你的类覆盖的hashCode()方法（在计算机科学的术语中称为散列函数）生成。
为解决数组容量被固定的问题，不同的键可以产生相同的下标。也就是说，可能会有冲突。因此，数组多大就不重要了，任何键总能在数组中找到它的位置。
于是查询一个值的过程首先就是计算散列码，然后使用散列码查询数组。如果能够保证没有冲突（如果值的数量是固定的，那么就有可能），那可就有了一个完美的散列函数，但是这种情况只是特例。通常，冲突由外部链接处理：数组并不直接保存值，而是保存值的list。然后对list中的值使用equals()方法进行线性查询。这部分的查询自然会比较慢，但是如果散列函数好的话，数组的每个位置只有较少的值。因此，不是查询整个list，而是快速地跳转到数组的某个位置，只对很少的元素进行比较。这便是HashMap会如此快的原因。
理解了散列的原因，我们就能够实现一个简单的散列Map了：
import java.util.AbstractMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
import com.buba.util.Countries;
public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
static final int SIZE = 997;
@SuppressWarnings("unchecked")
LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];
public V put(K key, V value) {
V oldValue = null;
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets[index] == null) {
buckets[index] = new LinkedList<MapEntry<K, V>>();
}
// 获取到该数组上的链表
LinkedList<MapEntry<K, V>> bucket = buckets[index];
// 把key value添加到MapEntry中
MapEntry<K, V> pair = new MapEntry<K, V>(key, value);
// 是否找到标识
boolean found = false;
ListIterator<MapEntry<K, V>> it = bucket.listIterator();
while (it.hasNext()) {
MapEntry<K, V> iPair = it.next();
// 如果添加的key存在
if (iPair.getKey().equals(key)) {
oldValue = iPair.getValue();
// 把旧值替换掉
it.set(pair);
found = true;
break;
}
}
// 如果链表中不存在则直接添加到链表中
if (!found)
buckets[index].add(pair);
return oldValue;
}
public V get(Object key) {
int index = Math.abs(key.hashCode()) % SIZE;
if (buckets[index] == null) {
return null;
}
for (MapEntry<K, V> iPair : buckets[index]) {
if (iPair.getKey().equals(key)) {
return iPair.getValue();
}
}
return null;
}
@Override
public Set<Entry<K, V>> entrySet() {
Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K, V>>();
for (LinkedList<MapEntry<K, V>> bucket : buckets) {
if (bucket == null) {
continue;
}
for (MapEntry<K, V> mpair : bucket) {
set.add(mpair);
}
}
return set;
}
public static void main(String[] args) {
SimpleHashMap<String, String> m = new SimpleHashMap<>();
m.putAll(Countries.capitals(25));
System.out.println(m);
System.out.println(m.get("中国"));
System.out.println(m.entrySet());
}
}由于散列表中的“槽位”（slot）通常称为桶位（bucket），因此我们将表示实际散列表的数组命名为bucket。为使散列分布均匀，桶的数量通常使用质数。注意，为了能够自动处理冲突，使用了一个LinkedList的数组；每一个新的元素只是直接添加到list末尾的某个特定桶位中。即使java不允许你创建泛型数组，那你也可以创建指向这种数组的引用。这里，向上转型为这种数组是很方便的，这样可以防止在后面的代码中进行额外的转型。
对于put()方法，hashCode()将针对键而被调用，并且其结果被强制转换为正数。为了使产生的数字适合bucket数组的大小，取模操作符将按照该数组的尺寸取模。如果数组的某个位置是null，这表示还没有元素被散列至此，所以，为了保存刚散列到该定位的对象，需要创建一个新的LinkedList。一般的过程是，查看当前位置的list是否有相同的元素，如果有，则将旧的赋给oldValue，然后用新的值取代旧的值。标记found用来跟踪是否找到（相同的）旧的键值对，如果没有，则将新的键值对添加到list的末尾。
get()方法按照与put()方法相同的方式计算在buckets数组中的索引（这很重要，因为这样可以保证两个方法可以计算出相同的位置）如果此位置有LinkedList存在，就对其进行查询。
注意，这个实现并不意味着对性能进行了调优；它只是想要展示散列映射表执行的各种操作。如果你浏览一下java.util.HashMap的源代码，你就会看到一个调过优的实现。同样，为了简单，SimpleHashMap使用了与SlowMap相同的方式来实现entrySet()，这个方法有些过于简单，不能用于通用的Map。
四、覆盖hashCode()
在明白了如何散列之后，编写自己的hashCode()就更有意义了。
首先，你无法控制bucket数组的下标值的产生。这个值依赖于具体的HashMap对象的容量，而容量的改变与容器的充满程度和负载因子（本章稍后会介绍这个术语）有关。hashCode()生成的结果，经过处理后成为桶位的下标（在SimpleHashMap中，只是对其取模，模数为bucket数组的大小）。
设计hashCode()时最重要的因素就是：无论何时，对同一个对象调用hashCode()都应该生成同样的值。如果在将一个对象用put()添加进HashMap时产生一个hashCode()值，而用get()取出时却产生了另一个hashCode()值，那么就无法重新取得该对象了。所以，如果你的hashCode()方法依赖于对象中易变的数据，用户就要当心了，因为此数据发生变化时，hashCode()就会生成一个不同的散列码，相当于产生了一个不同的键。
此外，也不应该使hashCode()依赖于具有唯一性的对象信息，尤其是使用this的值，这只能产生很糟糕的hashCode()。因为这样做无法生成一个新的键，使之与put()中原始的键值对中的键相同。这正是SpringDetector.java的问题所在，因为它默认的hashCode()使用的是对象的地址。所以，应该使用对象内有意义的识别信息。
下面以String类为例。String有个特点：如果程序中有多个String对象，都包含相同的字符串序列，那么这些String对象都映射到同一块内存区域。所以new String("hello")生成两个实例，虽然是互相独立的，但是对它们使用hashCode()应该生成同样的结果。通过下面的程序可以看到这种情况：
public class StringHashCode {
public static void main(String[] args) {
String[] hellos = "Hello Hello".split(" ");
System.out.println(hellos[0].hashCode());
System.out.println(hellos[1].hashCode());
}
}对于String而言，hashCode()明显是基于String的内容的。
因此，要想使hashCode()实用，它必须速度快，并且必须具有意义。也就是说，它必须基于对象的内容生成散列码。记得吗，散列码不必是独一无二的（应该更关注生成速度，而不是唯一性），但是通过hashCode()和equals()，必须能够完全确定对象的身份。
因为在生成桶的下标前，hashCode()还需要做进一步的处理，所以散列码的生成范围并不重要，只要是int即可。
还有一个影响因素：好的hashCode()应该产生分布均匀的散列码。如果散列码都集中在一块，那么HashMap或者HashSet在某些区域的负载会很严重，这样就不如分布均匀的散列函数快。
写出一个像样的hashCode()的基本步骤：
（1）给int变量result赋予某个非零值常数，例如1。
（2）为对象内每个有意义的域f（即每个可以做equals()操作的域）计算出一个int散列码c：
| 域类型 | 计算 |
| boolean | c = ( f? 0 : 1 ) |
| byte、char、short或int | c = ( int ) f |
| long | c = ( int ) (f ^ ( f >>> 32 )) |
| float | c = Float.floatToIntBits ( f ) |
| double | long l = Double.doubleToLongBits( f ); c = ( int ) ( l ^ ( l >>> 32 )) |
| Object，其equals()调用这个域的equals() | c = f.hashCode() |
| 数组 | 对每个元素应用上述规则 |
（3）合并计算得到的散列码：result = 31 * result + c;
（4）返回result。
（5）检查hashCode()最后生成的结果，确保相同的对象有相同的散列码。
下面便是遵循这些指导的一个例子：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class CountedString {
private static List<String> created = new ArrayList<String>();
private String s;
private int id = 0;
public CountedString(String str) {
s = str;
created.add(s);
for (String string : created) {
if (string.equals(s)) {
id++;
}
}
}
public String toString() {
return "String: " + s + " id: " + id + " hashCode(): " + hashCode();
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + id;
result = prime * result + ((s == null) ? 0 : s.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
CountedString other = (CountedString) obj;
if (id != other.id)
return false;
if (s == null) {
if (other.s != null)
return false;
} else if (!s.equals(other.s))
return false;
return true;
}
public static void main(String[] args) {
Map<CountedString, Integer> map = new HashMap<>();
CountedString[] cs = new CountedString[5];
for (int i = 0; i < cs.length; i++) {
cs[i] = new CountedString("hi");
map.put(cs[i], i);
}
System.out.println(map);
for (CountedString countedString : cs) {
System.out.println("Looking up " + countedString);
System.out.println(map.get(countedString));
}
}
}CountedString由一个String和一个id组成，此id代表包含相同String的CountedString对象的编号。所有的String都被存储在static ArrayList中，在构造器中通过迭代遍历此ArrayList完成对id的计算。
hashCode()和equals()都基于CountedString的这两个域来生成结果：如果它们只基于String或者只基于id，不同的对象就可能产生相同的值。
在main()中，使用相同的String创建了多个CountedString对象。这说明，虽然String相同，但是由于id不同，所以使得它们的散列码并不相同。在程序中，HashMap被打印了出来，因此可以看到它内部是如何存储元素的，然后单独查询每一个键，以此证明查询机制工作正常。
作为第二个示例，请考虑Individual类，它被用作类型信息章中定义的Pet类库的基类。Individual类在那一章中就用到了，而它的定义则放到了本章，因此你可以正确的理解其实现：
public class Individual implements Comparable<Individual> {
private static long counter = 0;
private final long id = counter++;
private String name;
public Individual(String name) {
this.name = name;
}
public Individual() {
}
public String toString() {
return getClass().getSimpleName() + (name == null ? "" : "" + name);
}
public long id() {
return id;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + (int) (id ^ (id >>> 32));
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Individual other = (Individual) obj;
if (id != other.id)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
@Override
public int compareTo(Individual arg) {
String first = getClass().getSimpleName();
String argFirst = arg.getClass().getSimpleName();
int firstCompare = first.compareTo(argFirst);
if (firstCompare != 0)
return firstCompare;
if (name != null && arg.name != null) {
int secondCompare = name.compareTo(arg.name);
if (secondCompare != 0)
return secondCompare;
}
return (arg.id < id ? -1 : (arg.id == id ? 0 : 1));
}
}compareTo()方法有一个比较结构，因此它会产生一个排序序列，排序的规则首先按照实际类型排序，然后如果有名字的话，按照name排序，最后按照创建的顺序排序。
如果本文对您有很大的帮助，还请点赞关注一下。
上一篇： 关于Java中String类的hashCode方法
下一篇： LeetCode第 18 场双周赛