Java中的HashMap类实现简介
博客专区 > NealFeng 的博客 > 博客详情
Java中的HashMap类实现简介
NealFeng 发表于4年前
Java中的HashMap类实现简介
  • 发表于 4年前
  • 阅读 181
  • 收藏 3
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

1 数据查询问题

  HashMap的出现主要来着与对查询操作速度的要求。实际中,假如有一个表,通常需要快速查询到某个数值是否包含在该表中。

1.1 一个实际问题,整数数组

  如何快速的在一个数据集合A中查询是否包含某个数据a
  例如:一个int[100]数组A,包含了100个数据,如何查找这100个数据中包含“98”这个数。
  • 方法一:使用for循环,将98依次与数组中的每个数进行比较
  • 方法二:将数组进行升序排列,然后使用二分法查找。
  但不论逐个比较还是二分法,都需要多次比较才能查询到结果,假如每次比较需要的时间相同,那这就意味这每次查询都需要不同的查询时间,有时短,有时需要很长,从时间复杂度的角度考虑,逐个比较的时间复杂度是O(n),二分法的时间复杂度是O(lgn)。
  可以想象,理想状态应该是每次查询花费的时间相同,有个最大值,这样就可以自信的向人介绍自己的查询算法:比如我的算法每次查询用时不超过1ms。
如何实现
  一种方法是,简单的牺牲空间换取时间:
  假设数组中都为正数,Java中32位的int,可表示的正数范围是0到2147483647,共2147483648个数值。
  1、建立一个新数组int[] Ints[2147483648],包含2147483648个位置,所有数据都初始化为-1。
 
  2、将之前100个数值的数组里的数据依次按照以下规则保存在新数组中:
  如果数据为i,则将其保存到新数组的Ints [i]位置,98放到Ints [98]
 
  3、现在如果查询98是否在数组中,那么只需要比较int[98]中的数据是-1还是98即可。
  这样就可以保证每次查询只需要进行1次比较,查询速度快。但这个方法的缺点很明显:
  占用了太多空间,2147483648个位置的32位int类型数组,要占居大约8GB的存储空间,对目前只有几G内存的计算机显然是不现实的。


1.2 另一个实际问题,号码簿

  如果有一个手机号码簿,如果快速查询某个号码是否已经在号码簿中
  假如手机号码都为11位,号码簿中共有10个号码,且后4位各不相同:
{ 
   286 3545 1285
   250 4592 8502
   239 2085 1032
   230 1932 0543
   259 1937 1408
   251 8592 1459
   252 2309 7934
   249 2942 9285
   289 0103 8482
   279 0094 1342
}

  如何快速查询号码251 8592 1459是否在号码簿中。
  根据上一个示例,由于手机号码数值太大无法用int类型表示,只能采用long类型表示。那可以定义一个包含1000 0000 0000个数值的long[]数组,但这明显不现实。不过不论根据日常经验还是前面的假设,号码簿中手机号码的后4位通常是不同的,那就可以有定义一个包含1 0000个数值的long[]数组L,以手机后4位为索引值,将电话号码保存在数组中:
  比如251 8592 1459就可以保存在L[1459]中
  这样查询号码251 8592 1459是否在号码簿中,只需要查询L[1459]的数值是否等于251 8592 1459即可。这样既节省了空间也加快的查询速度。

1.2.1 冲突(collisions)

  从上面得例子可以看出为了节省空间,只取了手机号后4位,如果两个手机号的后4位相同,那么就会产生冲突,这是为了节省空间带来的必然结果。为解决冲突情况,可以这样:
long[]数组L中不再直接保存手机号码,而是保存一个地址,这个地址指向一个链表,链表中保存着电话号码和指向下个电话号码的地址,当两个手机号后4位相同时,只需要将其链接到相应链表中即可,比如下图:
 

1.2.2 空间利用率

  号码簿的例子中,创建了1 0000个元素的数组,只存放了10个数据,那么空间利用率只有0.001。可以想象随着号码增多,空间利用率提高,但出现冲突的概率越大,查询操作的耗时越长。

2  HashMap<K,V>的字面解释

2.1  Hash,有道词典中的解释

中文:
n. 剁碎的食物;混杂,拼凑;重新表述
vt. 搞糟,把…弄乱;切细;推敲
英文:
n.
1. chopped meat mixed with potatoes and browned
2. purified resinous extract of the hemp plant; used as a hallucinogen
v.
chop up



  在计算机科学中,通常指直接或者间接使用了Hash Function来实现功能的实体。
  Hash Function,中文通常翻译为哈希函数或者散列函数
  字面理解哈希函数就是将一个变量“切碎”后变成另一个变量的函数。


2.2  Map有道词典中的解释

vt. 映射;计划;绘制地图;确定基因在染色体中的位置
n. 地图;示意图;染色体图
vi. 基因被安置
n.
1. a diagrammatic representation of the earth's surface (or part of it)
2. a function such that for every element of one set there is a unique element of another set
v. 
6. to establish a mapping (of mathematical elements or sets)

  可以看出HashMap中的map这里取的是数学中的概念,将一个值“映射”到另一个值
  HashMap<K,V>中K代表key,V代表Value,中文通常翻译为键(key)、值(value)
  综上,HashMap<K,V>就是一个用来存储<键、值>数据对的机制,其中键key“映射”到保存值(value)的存储地址,映射过程使用了哈希函数。也就是键(key)经过哈希函数运算后可以得到值(value)的地址。
  对上面电话号码簿的例子,电话号码簿体现为HashMap<K,V>的一个实例,键key为手机号,值(value)也为手机号。键(手机号)经过哈希函数运算(取手机号后4位)后可以得到值(手机号)的地址。

3  一个更复杂的例子——花名册

  假如有一个花名册,如何快速查询某个人比如“张三”是否在花名册中。
  这个问题与前2个问题的区别是,要查询的数据不是单个数字,这就很难利用前2个示例中的方法构建一个易于查询的花名册。但是可以试想,假如可以通过某种运算将名字变成一个0到10000之间的一个数字,而且名字不同时,产生的数字不同,那么就可以利用上述的方法构建一个易于查询的花名册。
  该运算在下文“如何设计合适的哈希函数”一节中有介绍。

4  哈希函数(Hash Function)的定义

  上例中某种运算(将名字变成一个0到10000之间的一个数字)就可以被称作是哈希函数。
  哈希函数更专业的定义是:哈希函数是任意一种算法,它可以将任意长度的原数据映射为固定长度的结果数据。
  因为哈希函数通常将可变长度的原数据,“切碎(hash)”成固定长度数据,对各部分处理后形成一个固定长度的数据,所以被形象的称为哈希函数。
  号码簿问题中,取电话号码中的后4位这个运算,就是将一个长数据映射为了一个短数据,所以也可以称为哈希函数。
  由于产生的数据长度固定,所以结果数据就可以用来作为数组的索引值,在相应位置保存原数据,就可以加快查询。
  • 从十进制角度看,如果产生的数据在0-10000之间,也就是4位十进制数时,就可以创建一个10000个数据的数组,用哈希函数的结果做为索引值。
  • 从二进制角度看,如果产生的数据在0-0x7F之间,也就是8位二进制数时,就可以创建一个128个数据的数组,用哈希函数的结果做为索引值。

5  如何设计合适的哈希函数

  可以想象为了减少冲突,加快查询,不同原数据经过哈希运算后产生的数值应该最大可能的不同。所以一个优秀的哈希函数必然具有这样的性质。
   注意:以下内容的叙述从数学理论的角度并不完全严密与准确,且缺少证明。更严谨的学习应该查看相关著作或者参加专门课程。
质数与求模运算正好具有这样的性质:
  假如有一个质数Z,其远大于数S,那么对于运算:
     ( n * Z ) % S
  其中n代表从1到无穷的任意整数,*为乘法运算,%为求模运算
  对应任意n,运算的结果均匀的分布在0到S之间。
  比如对于质数211和数8:
(1*211) % 8 = 3     (67*211) % 8 = 1
(2*211) % 8 = 6     (68*211) % 8 = 4
(3*211) % 8 = 1     (69*211) % 8 = 7
(4*211) % 8 = 4     (70*211) % 8 = 2
(5*211) % 8 = 7     (71*211) % 8 = 5
(6*211) % 8 = 2     (72*211) % 8 = 0
(7*211) % 8 = 5     (73*211) % 8 = 3
(8*211) % 8 = 0     (74*211) % 8 = 6



  所以对于上面花名册的例子,如果可以将名字经过哈希运算得到0到10000之间的数值,就可以实现快速查询。由于字符在电脑中通常用Unicode代码表示,查出名字的Unicode代码,“张”的Unicode十进制代码为24352,“三”的Unicode十进制代码为19977,选取质数9656717,进行以下运算:((24352 + 19977) * 9656717) % 10000 = 5168。这样就得到了0到10000之间的数值,参照之前的例子,就可以构造一个数组来加快查询。
  Unicode代码查询网址:
  http://www.unicode.org/charts/unihan.html
  质数表,Table of Primes from 1 to 1 000 000 000 000:
  http://www.walter-fendt.de/m14e/primes.htm


5.1  java.lang.String类中字符串的哈希函数

  在Oracle公司的Java API实现中,String类的hashcode()函数计算了字符串的哈希值,源代码如下。从注释和程序中可以看出,计算公式为hashall = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1],是将字符串各个字符的UTF-16代码乘以31的ni次方后相加得到的。31为质数,31^(ni)虽然不是质数,但是性质接近质数。但并没有发现显式的求模运算%,这是由int类型数据算术运算后得到的,如果值超过了int类型的最大值时,高位被自动抛弃,这就相当于对2147483648(十六进制0x7FFF)求模,所以结果在0到2147483648之间。
/**
     * Returns a hash code for this string. The hash code for a
     * <code>String</code> object is computed as
     * <blockquote><pre>
     * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
     * </pre></blockquote>
     * using <code>int</code> arithmetic, where <code>s[i]</code> is the
     * <i>i</i>th character of the string, <code>n</code> is the length of
     * the string, and <code>^</code> indicates exponentiation.
     * (The hash value of the empty string is zero.)
     *
     * @return  a hash code value for this object.
     */
    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;


            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

6  Java API中的HashMap类实现简介

6.1  HashMap类中哈希值的计算方法

  通过查看其源代码,可以看出HashMap类中哈希值的计算方法。
  类中的哈希值是通过final int hash(Object k)函数实现的,首先根据键(key)对象的hashcode函数计算键对象的hash值:k.hashCode(),然后内部再进行相应的移位和求异或运算,得到内部使用的hash值。可以看出hash值由int类型表示,则其值在0到Interger.MAX_VALUE之间。但实际内部存储用的数组长度由HashMap的容量决定,所以根据hash值得到对象在数组中的索引值,还需要近一步计算,下段中进行了说明。
/**
     * Retrieve object hash code and applies a supplemental hash function to the
     * result hash, which defends against poor quality hash functions.  This is
     * critical because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {//由于没看完整的源代码,此处目的没看明白,根据字面理解可能是其它基于此类的之类,如果不满意默认的哈希函数算法,可以使用此算法代替。
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }


        h ^= k.hashCode();//计算键对象的hash值,之后与0求异或运算


        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4); //移位异或运算等,使hash值更分散降低冲突可能
    }


6.2  根据键(key)对象查询值(value)对象

  根据键对象查询<K,V>对象的方法,涉及到的源代码如下。
  首先public V get(Object key)函数中,调用getEntry(key)函数,由键对象获得相应值的Entry<K,V>的地址entry。
  从Entry<K,V>源代码(这里没有粘贴过来)可以看出,Entry<K,V>是类中定义的新类,继承至Map.Entry<K,V>。该对象中保存了键(key)对象和相应的值(value)对象,并包含有指向下个Entry<K,V>地址的变量,这样可以实现链表功能,用于解决冲突。如果冲突产生时(不同键对象的hash值相同),将hash值相同的对象其依次放在此链表中。
  getEntry(key)函数中首先由hash(key)计算键对象的hash值。
  然后由indexFor(hash, table.length)函数根据hash值获得Entry<K,V>[]数组的索引值,该函数中h & (length-1)运算将hash值由原来的0到Interger.MAX_VALUE之间映射到0到(length-1)之间,这样就可以当作该数组的索引值。
  然后Entry<K,V> e = table[indexFor(hash, table.length)]根据索引值,将需要的数据找到。
  table是Entry<K,V>[]类型的数组,其中保存了指向相应Entry<K,V>的地址。
  for程序段中,如果有冲突,则依次遍历此链表,找到与指定键对象对应的值对象。将Entry<K,V>对象返回get(Object key)函数。
  最后get(Object key)函数调用entry.getValue()获得相应的值对象。


/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);


        return null == entry ? null : entry.getValue();
    }


    /**
     * Returns the entry associated with the specified key in the
     * HashMap.  Returns null if the HashMap contains no mapping
     * for the key.
     */
    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;
    }


    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

6.3  HashMap类的容量

  从之前的例子中,可以知道查询速度的改进是由于用空间换取了时间,所以HashMap类的容量越大,效率越高,但是空间占用约多。
  经过权衡,类中定义了填充率(loadFactor),默认为0.75;容量(capacity),默认值为16。源代码如下:
/**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;


    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;


    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }



  类始终保持类中保存的数据量小于门限(threshold) = 容量(capacity)* 填充率(loadFactor)。每次添加的新的数据时,都检测数据量(size)是否超过门限(threshold)。如果超限则调用resize(2 * table.length)函数,将类的容量增大。源代码如下:
/**
     * Adds a new entry with the specified key, value and hash code to
     * the specified bucket.  It is the responsibility of this
     * method to resize the table if appropriate.
     *
     * Subclass overrides this to alter the behavior of put method.
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }


        createEntry(hash, key, value, bucketIndex);
    }

6.4  调整HashMap类的容量对性能的影响

  调整HashMap类的容量的函数resize(int newCapacity)源代码如下,重新调整大小,需要新建一个Entry[]数组,然后调用transfer(newTable, rehash)函数将之前数组中的值调整到新数组中。
  transfer(newTable, rehash)函数中调用hash(e.key)函数重新计算了键对象的哈希值,根据哈希值将旧Entry[]数组中数据放到新Entry[]数组中。
  所以调整HashMap类的容量造成了以下影响:
  • 新建一个Entry[]数组,需要格外的空间
  • 重新计算了键对象的哈希值,需要格外的运行时间
  • 由于Entry[]数组长度变化,各元素在HashMap中的内部位置发生了改变
  综上,要根据时间情况,设计HashMap类的容量和填充率,尽少调整容量的次数。


/**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     *
     * If current capacity is MAXIMUM_CAPACITY, this method does not
     * resize the map, but sets threshold to Integer.MAX_VALUE.
     * This has the effect of preventing future calls.
     *
     * @param newCapacity the new capacity, MUST be a power of two;
     *        must be greater than current capacity unless current
     *        capacity is MAXIMUM_CAPACITY (in which case value
     *        is irrelevant).
     */
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }


        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }


    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }



6.5  最后一个例子,电话簿PhoneBook 

  之前示例中的电话簿中没有人名,这里添加人名。PhoneBook 扩展了HashMap类。这样可以直接使用其函数。电话簿中的每条内容由<String 人名, String 号码>组成。将人名作为键,号码作为值,所以可以根据人名获得他/她的电话号码。
  由于使用了字符串作为键,所以可以利用其已经实现的hashcode()函数实现hash值的计算。
  由于HashMap要求键值各不相同,所以此电话簿,不能有重名,还需要进一步改进。


import java.util.HashMap;


// PhoneBook 扩展了HashMap类。这样可以直接使用其函数。
// 电话簿中的每条内容由<String 人名, String 号码>组成。
// 将人名作为键,号码作为值,所以可以根据人名获得他/她的电话号码
public class PhoneBook extends HashMap<String,String> {
    PhoneBook(){
        super();
    }
    //测试
    public static void main(String[] args) {
        PhoneBook pb = new PhoneBook();
        String[][] intial = new String[][]{
                { "张三","286 3545 1285" },
                { "李四","250 4592 8502" },
                { "王五","239 2085 1032" },
                { "赵六","230 1932 0543" },
                { "王二麻子","259 1937 1408" },
                { "段誉","251 8592 1459" },
                { "王语嫣","252 2309 7934" },
                { "虚竹","249 2942 9285" },
                { "梦姑","289 0103 8482" },
                { "乔峰","279 0094 1342" }
        };
        //将电话保存在电话簿中
        for(int i = 0; i < intial.length; i++) {
            pb.put(intial[i][0], intial[i][1]);
        }
        //测试
        System.out.println("电话簿中共保存了" + pb.size() + "个电话号码。" );
        
        String name = new String("乔峰");
        Boolean bl = pb.containsKey(name);//查询是否包含该人名
        System.out.println("电话簿中" + ( bl ? "查到" : "未查到" ) + name 
                + "的电话号码。" 
                + ( bl ? ("电话号码是" + pb.get(name) + "。") : ""));
        //测试
        name = new String("王语嫣");
        bl = pb.containsKey(name);
        System.out.println("电话簿中" + ( bl ? "查到" : "未查到" ) + name 
                + "的电话号码。" 
                + ( bl ? ("电话号码是" + pb.get(name) + "。") : ""));
        //测试
        name = new String("星秀老仙");
        bl = pb.containsKey(name);
        System.out.println("电话簿中" + ( bl ? "查到" : "未查到" ) + name 
                + "的电话号码。" 
                + ( bl ? ("电话号码是" + pb.get(name) + "。") : ""));


    
}



  运行程序后,根据输出可以看出电话簿正常工作:
电话簿中共保存了10个电话号码。
电话簿中查到乔峰的电话号码。电话号码是279 0094 1342。
电话簿中查到王语嫣的电话号码。电话号码是252 2309 7934。
电话簿中未查到星秀老仙的电话号码。




7  参考资料

[1] Hash function
http://en.wikipedia.org/wiki/Hash_function


[2] 麻省理工学院公开课:算法导论> 哈希表
http://v.163.com/movie/2010/12/R/E/M6UTT5U0I_M6V2TG4RE.html


[3] Java官方API(Oracle Java SE7)源代码,下载安装JDK后,源代码位于安装根目录的src.zip文件中 
http://www.oracle.com/technetwork/java/javase/downloads/jdk7-downloads-1880260.html


[4] OpenJDK源代码下载(包括了HotSpot虚拟机、各个系统下API的源代码,其中API源代码位于openjdk\jdk\src\share\classes文件夹下): 
https://jdk7.java.net/source.html




标签: Java HashMap 哈希
共有 人打赏支持
粉丝 26
博文 53
码字总数 36482
×
NealFeng
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: