谈一谈HashMap类

一、Java中的hashCode()和equals()
　　1、 hashCode()的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode()是用来在散列存储结构中确定对象的存储地址的；
　　2、如果两个对象相同，就是指对象调用equals()方法返回true，那么这两个对象的hashCode()方法的返回值一定要相同；
　　3、如果对象的equals()方法被重写，那么对象的hashCode()方法也尽量重写，并且hashCode()方法使用的对象的变量信息，一定要和equals方法中使用的一致，否则就会违反上面提到的第2点；
　　4、两个对象的hashCode()相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里“。

　　再归纳一下就是hashCode()是用于查找使用的，而equals()是用于比较两个对象是否相等的。

二、HashMap类的实现原理

　　1、HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

　　2、在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

　　3、HashMap的存取：

　　　　1）利用key的hashCode重新hash计算出当前对象的元素在数组中的下标（索引计算公式：（length-1）& hash）；
　　　　2）存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中
　　　　3）获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
　　　　4）理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

三、HashMap的扩容机制

　　当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过即使是1000，hashmap也自动会将其设置为1024。但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。

/**
　* jdk版本：1.8.0_111。

  * 使用HashMap的空参构造创建一个HashMap集合，初始容量为16；负载因子loadFactor为0.75；

  *  当集合的元素个数超过16*0.75=12时集合容量扩大一倍。*/

public class Demo01 {

    public static void main(String[] args) throws Exception {

        HashMap<String, Object> map = new HashMap<String, Object>();

        System.out.println(map.size()); //

        System.out.println(getCapacity(map)); //

        map.put("abc0", 1);

        map.put("abc16", 1);

        map.put("abc27", 1);

        map.put("abc49", 1);

        System.out.println(map.size()); //

        System.out.println(getCapacity(map)); //

        String key = null;

        for (int i = 0; i < 8; i++) {

            key = "a" + i;

            map.put(key, key);

        }

        System.out.println(map.size()); //

        System.out.println(getCapacity(map)); //

        Object obj = map;

        map.put("a8", "a8");

        System.out.println(map.size()); //

        System.out.println(getCapacity(map)); //

        System.out.println(obj == map); // true,扩容后引用地址没变

    }

    public static Integer getCapacity(Map<?, ?> map) throws Exception {

        Method method;

        method = map.getClass().getDeclaredMethod("capacity");

        method.setAccessible(true);

        return (int) method.invoke(map);

    }

}

　　再看下面的一个例子：

/**
 * jdk版本：jdk1.7.0_60。

 * 创建一个HashMap集合，初始容量为4，加载因子loadFactor为0.75；

 * 我们理应认为：当集合的元素个数超过4*0.75=3时集合容量扩大一倍。

 * 但是当使用jdk1.7.0_60时，结果并非如此。

 */

public class Demo2 {

    public static void main(String[] args) throws Exception {

        HashMap<Integer, Object> map = new HashMap<>(4, 0.75f);

        System.out.println(map.size()); //

        System.out.println(getCapacity(map)); //

        map.put(0, 1);

        map.put(4, 1);

        map.put(8, 1);

        System.out.println(map.size()); //

        System.out.println(getCapacity(map)); //

        map.put(1, 1);

        System.out.println(map.size()); //

        System.out.println(getCapacity(map)); //

        map.put(2, 1);

        System.out.println(map.size()); //

        System.out.println(getCapacity(map)); //

        map.put(3, 1);

        System.out.println(map.size()); //

        System.out.println(getCapacity(map)); //

        map.put(5, 1);

        System.out.println(map.size()); //

        System.out.println(getCapacity(map)); //

    }

    public static Integer getCapacity(Map<?, ?> map) throws Exception {

        Method method;

        method = map.getClass().getDeclaredMethod("capacity");

        method.setAccessible(true);

        return (int) method.invoke(map);

    }

}

　　查看jdk1.7.0_60HashMap源码：问题的关键在于标红的代码。

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);

}

四、为什么HashMap容量为2的次幂?

　　看了一些资料，以下是自己的理解：

　　HashMap底层实现为数组+单链表，元素的存取是根据数组索引来操作的。那么HashMap是如何计算元素在数组中的索引呢？

　　首先，HashMap的元素是包含key、value的键值对，HashMap是根据key值，加上一些算法计算得到该元素在数组中的索引。具体算法如下：

// 传入key，得到对应的hash值

static final int hash(Object key) {

    int h;

    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

/**

 * @param key 键值对的key

 * @param capicity HashMap集合的容量

 * @return

 */

static int getIndex(Object key, int capicity) {

    int hash = hash(key); // 传入key，得到对应的hash值

    int index = (capicity - 1) & hash; // 得到元素在数组中的索引

    return index;

}

　　综上可知，HashMap集合是根据 (capicity - 1) & key的hash值来计算元素在数组中的索引。

　　假设HashMap集合的容量capacity=15，则元素在数组中的索引 index = (capacity-1) & hash = 14 & hash = 0b1110 & hash，则index只有8种结果：0、2、4、6、8、10、12、14，意思就是数组的某些位置不能存值，浪费空间，也加大了hash冲突的可能。

　　如果HashMap集合的容量capacity=2的n次方，则元素在数组中的索引 index = (2ⁿ-1) & hash = 0b11...11(n个1) & hash，则index有2ⁿ种结果，即是0、1、2 ... 2ⁿ-1，所以数组的每个位置都会存值，基本上均匀地分布，有效利用空间，也减少了hash冲突，提高HashMap集合的性能。

　　事实上，只有当HashMap集合的容量capacity=2ⁿ时，(capacity-1) & hash 与 hash % capacity 的结果是等效的。

　　写个小案例体会一下：

public class Demo1 {

    public static void main(String[] args) {

        String key = null;

        int capicity = 15; // 容量

        int[] array = new int[capicity];

        for (int i = 0; i < 10000; i++) {

            key = "abc1" + i;

            int index = getIndex(key, capicity);

            if (index < capicity) {

                array[index] += 1;

            }

        }

        //capicity=16: [642, 643, 600, 590, 556, 538, 572, 554, 609, 607, 655, 665, 692, 711, 674, 692]

        //capicity=8: [1251, 1250, 1255, 1255, 1248, 1249, 1246, 1246]

        //capicity=4: [2499, 2499, 2501, 2501]

        //capicity=15: [1285, 0, 1190, 0, 1094, 0, 1126, 0, 1216, 0, 1320, 0, 1403, 0, 1366]

        //capicity=14: [1242, 1233, 0, 0, 1128, 1092, 0, 0, 1264, 1272, 0, 0, 1366, 1403]

        System.out.println(Arrays.toString(array));

    }

    // 传入key，得到对应的hash值

    static final int hash(Object key) {

        int h;

        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

    }

    /**

     * 得到元素在数组中的索引

     * @param key 键值对的key

     * @param capicity HashMap集合的容量

     * @return

     */

    static int getIndex(Object key, int capicity) {

        int hash = hash(key); // 传入key，得到对应的hash值

        int index = (capicity - 1) & hash; // 得到元素在数组中的索引

        return index;

    }

}

参考资料：

　　1、Java中HashMap的实现原理

　　2、HashMap中的为什么hash的长度为2的幂而&位必须为奇数

　　3、Hashmap为什么容量是2的幂次，什么是负载因子

　　4、HashMap容量为2次幂的原因(碰撞冲突拉链法解决)

　　5、HashMap：为什么容量总是为2的次幂（推荐）

巴特西

谈一谈HashMap类

最新文章

热门文章