你真的了解散列吗?以散列码的角度再分析HashMap-阿里云开发者社区

开发者社区> 云计算> 正文

你真的了解散列吗?以散列码的角度再分析HashMap

简介: 众所周知,使用Java的HashMap数据结构时,要求正确实现hashCode(),但是为什么呢?hashCode产生的散列码到底代表什么,其在HashMap中到底有何作用?本文将为您详细道来。

众所周知,使用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;
  }
} 

该代码需要有一下几点说明:

  1. 以散列码为下标的数组被称为散列表,散列表的中位置被称为桶位(bucket),桶排序也和桶位有关,故此得名;
  2. 原来认为,理论上散列表的大小最好为质数(原因来自于模素数的限域 mod P,这是一种完备的等价划分,其结果会分布均匀),但是现在经过大量的测试发现,散列表取2的整数次方的效果更好,因为HashMap中get方法使用的频率最高,而get方法中涉及到对于散列表大小的除法和取余数,虽然一般数字对于这些操作很慢,但是2的整数次幂可以使用掩码(mask)代替除法提高效率,低效除法对于性能的影响。

3 如何覆盖hashCode()方法

在实现hashCode()的时候,有以下几点设计原则需要注意:

  1. 同一个对象无论何时调用hashCode方法都应该生成同样的散列码,因此不能依赖对象中易变数据生成散列码。
  2. hashCode方法也尽量不能完全依赖具有唯一性的信息,比如默认this值,默认hashCode方法就是返回对象存储地址,这样做虽然保证了每个对象都是不同的散列码,但是该散列码没有意义,两个逻辑上相同的对象(比如内容相同String类对象)也会生成不同的散列码,所以生成散列码需要依赖对象的有意义的信息
  3. hashCode方法和equal方法等价,也就是说调用equal方法相等的两个对象,其散列值也应该是相同的,反之也成立。
  4. hashCode方法运算过程不能太复杂,因为散列码是为了追求速度而设计的,所有不能在生成散列码的过程中过度浪费时间;
  5. 散列码应该尽量均匀分布,以减少在线性查询过程的平均时间;

《Effective Java》给出了一种实现hashCode的指导方法:

  1. 对于int变量result = 某个非0的变量,比如17;
  2. 为对象内每个有意义的域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()
数组 对于每个元素都应用以上规则
  1. 依次迭代计算散列码:
    result = 37* result + c ;
  2. 返回result
  3. 确定相等的实例具有相同散列码,反之也要成立。

下面是《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;
}

根据注解中标识依次进行解释:

  1. 由于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位,这里便不再展开讨论。

  1. 当确定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

二次散列的位移

  1. 获得散列码之后,使用散列码确定该值其在散列表中的位置:
/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

上文已经提过,对于2的幂次的取余数可以通过位与(&)掩码来实现,length-1便是length的掩码,这一步实际上就是高效地实现了取余。

  1. 确定元素在散列表中位置后,就开始查找外部链表中是否包含该key,请注意key是否存在的条件
e.hash == hash && ((k = e.key) == key || key.equals(k))

这里不光使用了散列码,还调用了equal方法,所以要使用HashMap的类必须要同时正确覆盖hashCode和equal两个方法

  1. 如果没有找到该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实现的内容远比介绍的内容要多,这里只是讲解了和散列码最为密切相关的部分,欢迎大家留言讨论指正。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章