容器深入研究(8):散列与散列码(下) 朱雀 2023-07-24 14:48 100阅读 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 >>> 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 ); c = ( int ) ( l ^ ( l >>> 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排序,最后按照创建的顺序排序。 **如果本文对您有很大的帮助,还请点赞关注一下。**
还没有评论,来说两句吧...