容器深入研究（8）：散列与散列码（下）

朱雀 2023-07-24 14:48 146阅读 0赞

### 三、为速度而散列 ###

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：

<table> 
 <tbody> 
  <tr> 
   <td style="width:295px;">域类型</td> 
   <td style="width:568px;">计算</td> 
  </tr> 
  <tr> 
   <td style="width:295px;">boolean</td> 
   <td style="width:568px;">c = ( f? 0 : 1 )</td> 
  </tr> 
  <tr> 
   <td style="width:295px;">byte、char、short或int</td> 
   <td style="width:568px;">c = ( int ) f</td> 
  </tr> 
  <tr> 
   <td style="width:295px;">long</td> 
   <td style="width:568px;">c = ( int ) (f ^ ( f &gt;&gt;&gt; 32 ))</td> 
  </tr> 
  <tr> 
   <td style="width:295px;">float</td> 
   <td style="width:568px;">c = Float.floatToIntBits ( f )</td> 
  </tr> 
  <tr> 
   <td style="width:295px;">double</td> 
   <td style="width:568px;">long l = Double.doubleToLongBits( f );&nbsp; &nbsp; &nbsp; &nbsp;c = ( int ) ( l ^ ( l &gt;&gt;&gt; 32 ))</td> 
  </tr> 
  <tr> 
   <td style="width:295px;">Object，其equals()调用这个域的equals()</td> 
   <td style="width:568px;">c = f.hashCode()</td> 
  </tr> 
  <tr> 
   <td style="width:295px;">数组</td> 
   <td style="width:568px;">对每个元素应用上述规则</td> 
  </tr> 
 </tbody> 
</table>

（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排序，最后按照创建的顺序排序。

**如果本文对您有很大的帮助，还请点赞关注一下。**