众所周知，使用Java的HashMap数据结构时，要求正确实现hashCode()，但是为什么呢？hashCode产生的散列码到底代表什么，其在HashMap中到底有何作用？本文将为您详细道来。
散列表
1 为什么要用散列值？
我们已经知道如果不能正确覆盖hashCode和equal方法，就不能正确使用散列数据结构（HashSet，HashMap, LinkedMashSet, LinkedMashMap）。
使用Map这种数据结构，最重要的应用场景就是维系“Key-Value”关系，通过key值能找到对应的value。要实现Map的功能并不难，以下是《Thinking in Java》中利用两个List实现Map的例子，
public class SlowMap<K,V> extends AbstractMap<K,V> {
private List<K> keys = new ArrayList<K>();
private List<V> values = new ArrayList<V>();
public V put(K key, V value) {
V oldValue = get(key); // The old value or null
if(!keys.contains(key)) {
keys.add(key);
values.add(value);
} else
values.set(keys.indexOf(key), value);
return oldValue;
}
public V get(Object key) { // key is type Object, not K
if(!keys.contains(key))
return null;
return values.get(keys.indexOf(key));
}
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
Iterator<K> ki = keys.iterator();
Iterator<V> vi = values.iterator();
while(ki.hasNext())
set.add(new MapEntry<K,V>(ki.next(), vi.next()));
return set;
}
public static void main(String[] args) {
SlowMap<String,String> m= new SlowMap<String,String>();
m.putAll(Countries.capitals(15));
System.out.println(m);
System.out.println(m.get("BULGARIA"));
System.out.println(m.entrySet());
}
}
这个SlowMap是线性存储，key没有按照任何特定的顺序保存，而是简单粗暴的直接按存储顺序存储，这种作的结果就是要查询key就必须线性查询，但是线性查询是最慢的查询方式。
为了让查询key的效率更高，有一种方法就是保持key值的排序状态，然后使用Collection.binarySearch方法来进行查找，但是这个样还不够满足所有使用情况，需要更进一步的突破。
2 为速度而生的散列码：
想一想，什么样的数据结构获取其中元素的速度最快？没错就是数组（时间复杂度为O(1)），但是数组的最大问题在于其容量是固定的，面对可能是不固定数量的数据该怎么办呢？想ArrayList那样扩容，如果扩容太频繁，数据结构维护的代价就太大了。
为了解决这个矛盾，数组中并不直接保存key值，而是保存由key生成的标识，这个标识可以在一定程度上代表key的信息，这就是散列码，以散列码为数组的下标。由key值生成散列码的过程被称为散列函数。
散列函数在设计时要求所产生的散列码尽量要分布均匀，以充分利用存储数组的空间，但是即使分布再均匀，数组的容量都是有限的，如果数据的数量超过数组容量的时候，就不可避免地要面临两个key值有相同散列码而共享一个数组的下标，这就是所谓的散列冲突。
为了解决散列冲突，Java在实现HashMap时用的是外部链接的方法：数组中保存的并不是Value值，而是一个链式的对象，这个链式对象中线性保存着所有散列码为当前数组下标key的键值对。
外部链接
当进行查询操作时，先通过散列码定位到对应的链表中，然后在链表中线性查找满足条件的元素，而不是对于所有的数据进行线性查找，这边便是HashMap查找效率高的原因。如果存储数组的大小和散列函数设计得当，发生散列冲突的次数越少，每个链表中的数据越少，HashMap的效率就越高。
以下是《Thinking in Java》中给出的HashMap简单的实现，以便大家了解散列码的工作原理，其中链表是用list实现的：
public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
// Choose a prime number for the hash table
// size, to achieve a uniform distribution:
static final int SIZE = 997;
// You can't have a physical array of generics,
// but you can upcast to one:
@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];
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();
if(iPair.getKey().equals(key)) {
oldValue = iPair.getValue();
it.set(pair); // Replace old with new
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;
}
public Set<Map.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;
}
}
该代码需要有一下几点说明：
- 以散列码为下标的数组被称为散列表，散列表的中位置被称为桶位（bucket）,桶排序也和桶位有关，故此得名；
- 原来认为，理论上散列表的大小最好为质数（原因来自于模素数的限域 mod P，这是一种完备的等价划分，其结果会分布均匀），但是现在经过大量的测试发现，散列表取2的整数次方的效果更好，因为HashMap中get方法使用的频率最高，而get方法中涉及到对于散列表大小的除法和取余数，虽然一般数字对于这些操作很慢，但是2的整数次幂可以使用掩码（mask）代替除法提高效率，低效除法对于性能的影响。
3 如何覆盖hashCode()方法
在实现hashCode()的时候，有以下几点设计原则需要注意：
- 同一个对象无论何时调用hashCode方法都应该生成同样的散列码，因此不能依赖对象中易变数据生成散列码。
- hashCode方法也尽量不能完全依赖具有唯一性的信息，比如默认this值，默认hashCode方法就是返回对象存储地址，这样做虽然保证了每个对象都是不同的散列码，但是该散列码没有意义，两个逻辑上相同的对象（比如内容相同String类对象）也会生成不同的散列码，所以生成散列码需要依赖对象的有意义的信息；
- hashCode方法和equal方法等价，也就是说调用equal方法相等的两个对象，其散列值也应该是相同的，反之也成立。
- hashCode方法运算过程不能太复杂，因为散列码是为了追求速度而设计的，所有不能在生成散列码的过程中过度浪费时间；
- 散列码应该尽量均匀分布，以减少在线性查询过程的平均时间；
《Effective Java》给出了一种实现hashCode的指导方法：
- 对于int变量result = 某个非0的变量，比如17；
- 为对象内每个有意义的域f（也就是在执行equal方法时需要对比的域），计算出一个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型，再计算 |
| Object对象 | c = f.hashCode() |
| 数组 | 对于每个元素都应用以上规则 |
- 依次迭代计算散列码：
result = 37* result + c ; - 返回result；
- 确定相等的实例具有相同散列码，反之也要成立。
下面是《Thinking in Java》中给出的依照上面的类实现的CounterString，其散列码是依据String类内容和id生成的：
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);
// id is the total number of instances
// of this string in use by CountedString:
for(String s2 : created)
if(s2.equals(s))
id++;
}
public String toString() {
return "String: " + s + " id: " + id +
" hashCode(): " + hashCode();
}
public int hashCode() {
// The very simple approach:
// return s.hashCode() * id;
// Using Joshua Bloch's recipe:
int result = 17;
result = 37 * result + s.hashCode();
result = 37 * result + id;
return result;
}
public boolean equals(Object o) {
return o instanceof CountedString &&
s.equals(((CountedString)o).s) &&
id == ((CountedString)o).id;
}
}
4 HashMap源码分析
说了这么多，相信大家对于散列和散列码已经有了一定的了解，基于散列码的角度，让我们再来看看真实情况下HashMap的源码（Java 1.7）
4.1 HashMap基础
首先，为了效率考虑，HashMap中散列表为Entry类型的数组：
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table;
散列表大小默认为16，在需要的情况下，散列表的大小可以重置，就像ArrayList那样，但是大小必须是2的整数幂。
那什么时候散列表的大小要重置？ HashMap为散列表设置了loadFactor负载因子这个属性，当散列表中的Entry数量达到阈值时（threshold = capacity * load factor），散列表的大小就会扩展为原来的2倍。
/**
* The next size value at which to resize (capacity * load factor).
* @serial
*/
int threshold;
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
散列表中的元素Entry是HashMap类中的静态内部类，为Map.Entry<K,V>接口的实现，表示一个键值对条目：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
.......
}
注意Entry中包含域Entry<K,V> next，说明这一种链式结构，以此实现上一节提到的外部链接来解决散列碰撞。
4.2 put方法
下面看一下如何向散列表中添加键值对：
public V put(K key, V value) {
//1. 如果键为null,则进入key为null的流程
if (key == null)
return putForNullKey(value);
//2. 获取key的散列值，二次散列
int hash = hash(key);
//3. 根据散列码确定在散列表中的位置
int i = indexFor(hash, table.length);
//4. 如果能在散列表中找到对应的键值对，则更新
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
//5. 没能找到键值对，则创建加入该键值对
modCount++;
addEntry(hash, key, value, i);
return null;
}
根据注解中标识依次进行解释：
- 由于HashMap允许key为空，所以当发现key==null时，调用方法putForNullKey：
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
该方法内容和put方法类似，只不过把key改为null，插入位置默认为0位，这里便不再展开讨论。
- 当确定key不为空后，就开始计算key的散列码：
//2. 获取key的散列值，二次散列
int hash = hash(key);
这里是HashMap一次经典代码，其中使用了二次散列：
final int hash(Object k) {
//散列码初始值
int h = 0;
//1. 是否启动改进散列值模式；
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//2. 获得第一次散列码；
h ^= k.hashCode();
//3. 防止因散列表大小为2的幂次而造成的散列碰撞；
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
- 因为Sun公司提供了增强的计算散列码的方法，如果当前配置环境支持这种选择，就可以启动增强模式。该模式下，String类型的散列码已经直接可以得到；而对于其他类型，也挺通过了一个散列种子hashSeed来帮助减少散列碰撞的发生。
- 第一次散列，是通过Key本身的散列函数完成；
- 第二次散列是为了减少因散列表大小为2的幂次而造成的散列碰撞。
当散列表大小capacity是2的指数，如果两个对象的hashCode值的低位相同，很有可能导致hashCode/capacity的值相同，就会出现冲突。
0101 0000 0000 1111 = 20495
0111 0000 0000 1111 = 28687
假如hashmap的capacity是16，那么20495%16 = 15,28687%16=15，散列码冲突。
注释3处的位移操作就是让高位的数值也参与到散列值的计算中，具体分析请见http://www.iteye.com/topic/709945二次散列的位移
- 获得散列码之后，使用散列码确定该值其在散列表中的位置：
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
上文已经提过，对于2的幂次的取余数可以通过位与（&）掩码来实现，length-1便是length的掩码，这一步实际上就是高效地实现了取余。
- 确定元素在散列表中位置后，就开始查找外部链表中是否包含该key，请注意key是否存在的条件
e.hash == hash && ((k = e.key) == key || key.equals(k))
这里不光使用了散列码，还调用了equal方法，所以要使用HashMap的类必须要同时正确覆盖hashCode和equal两个方法。
- 如果没有找到该Key，就会添加一个键值对条目。在添加新条目之前，会执行modCount++。modCount的定义如下：
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
由于HashMap不是线程安全的，以牺牲进程同步的开销，来换取效率。退而求其次，HashMap使用了快速失败（Fail-Fast）机制（也就是发现多线程数据不同步，就抛出异常）来处理这个问题。
例如使用HashMap的Iterator：开始时会将modCount的赋值给expectedModCount；在迭代过程中，通过每次比较两者是否相等来判断HashMap是否在内部或被其它线程修改，如果modCount和expectedModCount值不一样，证明有其他线程在修改HashMap的结构，会抛出异常。
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
所以HashMap的put、remove等操作都有modCount++的计算，以确保没有多线程数据不同的问题。
更新modCount数值之后，开始正式添加键值对：
void addEntry(int hash, K key, V value, int bucketIndex) {
// 如果散列表的数量已经阈值就开始扩容散列表
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容2倍
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//创建新条目
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//新条目成为该桶位的第一个节点，原有链表被放在其后面；
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
4.3 containsKey方法
判断是否含有key，也是HashMap一个常用的功能：
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
有了put方法的知识的基础，以上代码并不难理解，还是先利用两次散列获得散列码，利用散列码快速定位带散列表上的桶位，在桶位处的链表上线性查找是否含有key，其判断条件要求hashCode和equal方法都相等。
9.4.4 get方法
get操作时HashMap中使用频率最高的，其实现和containsKey方法一样都是基于getEntry方法：
public V get(Object key) {
//1. 如果key为空，则尝试获取NullKey位置的条目
if (key == null)
return getForNullKey();
//2. 根据key获得条目
Entry<K,V> entry = getEntry(key);
//3. 返回条目；
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
//空key的桶位默认为0
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
需要注意的是，由于put时NullKey对应的桶位为0，所以在取出NullKey对应的Value时也只直接去0位查找。
关于散列码和HashMap的内容暂时为大家介绍这些，当然HashMap实现的内容远比介绍的内容要多，这里只是讲解了和散列码最为密切相关的部分，欢迎大家留言讨论指正。
网友评论