java -- HashMap

java -- HashMap

 

 

特点

 

• HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
• HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
• HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

 

 

 

扩容

 

• 初始容量：哈希表在创建时的容量，默认是16
• 加载因子：哈希表在其容量自动增加之前可以达到多满的一种尺，默认是0.75

当哈希表的容量超过 初始容量 * 加载因子，就会触发扩容，扩容后的哈希表大概是原来的两倍。

 

 

如何选择初始容量和加载因子

 

    通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折中。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

 

 

 

 

HashMap的构造函数

 

// 默认构造函数。
HashMap()

// 指定“容量大小”的构造函数
HashMap(int capacity)

// 指定“容量大小”和“加载因子”的构造函数
HashMap(int capacity, float loadFactor)

// 包含“子Map”的构造函数
HashMap(Map<? extends K, ? extends V> map)

 

 

 

 

HashMap的API

 

void                 clear()
Object               clone()
boolean              containsKey(Object key)
boolean              containsValue(Object value)
Set<Entry<K, V>>     entrySet()
V                    get(Object key)
boolean              isEmpty()
Set<K>               keySet()
V                    put(K key, V value)
void                 putAll(Map<? extends K, ? extends V> map)
V                    remove(Object key)
int                  size()
Collection<V>        values()

 

 

 

 

数据结构

 

    说白了，HashMap就是数组和链表的结合，初始化时，会是一个数组，数组中每一个空间可以存一个Entry（HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对）。在遇到Hash冲突时（当put一个key-value进去的时候，发现key已经被用了），就会用链表向下伸展，向下伸展的是一个单项连边，指向的下一个元素也是Entry。

 

 

 

 

哈希冲突

 

    当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。

 

例如：

key = 1，value = 10，

key = 11，value = 20，

如果两个key进行hash后的是相同的，这样就会存在冲突，这样存储的值就有可能被覆盖。

 

 

解决方法

 

    数组 + 链表，Entry数组是根据key进行Hash后的值进行存放的，如果有hash冲突，就通过链表向下伸展，在查找元素时，是先在Entry数组中找，找到后，再向下遍历链表，找到key对应的Entry。

 

 

 

 

性能问题

 

      简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度依然为O(1)，因为最新的Entry会插入链表头部，急需要简单改变引用链即可，而对于查找操作来讲，此时就需要遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

 

    同时，在考虑性能时，也要考虑初始容量和加载因子，因为这会影响到扩容，也是影响性能的一部分。

 

 

 

 

HashMap下标计算

 

计算下标的流程大概如下：

 

1. 先调用hashCode()，拿到相应的hashCode

 

2. 通过hash()，获取一个h值

 

//这是一个神奇的函数，用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

 
 3. 然后通过对h执行indexFor()，得出最终下标

 

/**
     * 返回数组下标
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 

 

 

 

为何HashMap的数组长度一定是2的次幂？

 

      如果不是2的次幂，也就是低位不是全为1此时，要使得index=21，h的低位部分不再具有唯一性了，哈希冲突的几率会变的更大，同时，index对应的这个bit位无论如何不会等于1了，而对应的那些数组位置也就被白白浪费了。

 

简单点说，减少出现Hash冲突。

 

 

 

 

重写equals方法需同时重写hashCode方法

 

      各种资料上都会提到，“重写equals时也要同时覆盖hashcode”，我们举个小例子来看看，如果重写了equals而不重写hashcode会发生什么样的问题。

 

/**
 * Created by chengxiao on 2016/11/15.
 */
public class MyTest {
    private static class Person{
        int idCard;
        String name;

        public Person(int idCard, String name) {
            this.idCard = idCard;
            this.name = name;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()){
                return false;
            }
            Person person = (Person) o;
            //两个对象是否等值，通过idCard来确定
            return this.idCard == person.idCard;
        }

    }
    public static void main(String []args){
        HashMap<Person,String> map = new HashMap<Person, String>();
        Person person = new Person(1234,"乔峰");
        //put到hashmap中去
        map.put(person,"天龙八部");
        //get取出，从逻辑上讲应该能输出“天龙八部”
        System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
    }
}

 

输出结果：<结果：null>

 

      如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)-->hash-->indexFor-->最终索引位置 ，而通过key取出value的时候 key(hashcode1)-->hash-->indexFor-->最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）

 

      所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。

 

 

 

 

HashMap遍历方法

 

方法一

// 假设map是HashMap对象
// map中的key是String类型，value是Integer类型
Integer integ = null;
Iterator iter = map.entrySet().iterator();
while(iter.hasNext()) {
    Map.Entry entry = (Map.Entry)iter.next();
    // 获取key
    key = (String)entry.getKey();
        // 获取value
    integ = (Integer)entry.getValue();
}

 

方法二

// 假设map是HashMap对象
// map中的key是String类型，value是Integer类型
String key = null;
Integer integ = null;
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
        // 获取key
    key = (String)iter.next();
        // 根据key，获取value
    integ = (Integer)map.get(key);
}

 

方法三

// 假设map是HashMap对象
// map中的key是String类型，value是Integer类型
Integer value = null;
Collection c = map.values();
Iterator iter= c.iterator();
while (iter.hasNext()) {
    value = (Integer)iter.next();
}

 

 

 

 

相关面试题

 

1. HashMap的key能否为null？    能

 

 

2. HashMap的key重复的时候，会怎样？ 

 

     从方法上，会将新值赋值给旧值，然后返回旧值；从数据结构上，会在hash后数组中找到对应的位置，然后新值保存在一个新对象中，然后指针next指向就的对象。

 

 

3. HashMap什么时候扩容

 

• 初始容量 = 2的4次方 = 16
• put方法调用的时候，判断容量是否使用到0.75，如果是就进行扩容，如果不是就不扩容
• 容量会扩大为原来的2倍

 

4. HashMap的扩容是怎样的流程？

 

• 先将容量扩大为原来的2倍
• 然后遍历原来的key，通过Hash算法进行计算，看放在哪个位置
• 如果遇到Hash碰撞，就用链表来存起后面数据

 

5. HashMap的数据结构

 

    数组  + 链表

 

 

6. HashMap的不足之处

 

• 时间复杂度受Hash算法影响
• 性能问题会在扩容上体现出来，如果上千或几万条数据，可以确定容量的话，在new HashMap的时候设置好容量，这样减少扩容带来的负担，可能减少Hash算法的调用。