有关Map的一些总结

作者: DDDong丶 | 来源:发表于2019-06-20 18:51 被阅读3次

1.HashMap 的数据结构是什么样的？

我们知道在Java中最常用的两种结构是数组和模拟指针(引用)，几乎所有的数据结构都可以利用这两种来组合实现，HashMap也是如此。实际上HashMap是一个“链表散列”，如下是它数据结构：

image

从上图我们可以看出HashMap底层实现还是数组，只是数组的每一项都是一条链，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。

2.HashMap添加一个元素时是如何进行添加的（源码步骤是什么样的）？

我们在使用HashMap存储数据时会用到put(K,V)。我们都知道HashMap的K值是唯一的，其内部主要是通过哈希表管理所有元素保证唯一性。当我们调用put()时，HashMap会先调用K的HashCode方法获取哈希码，再通过哈希码快速找到某个存放位置，这个位置可以被称之为bucketIndex。

理论上，hashCode可能存在冲突的情况，有个专业名词叫碰撞，当碰撞发生时，计算出的bucketIndex也是相同的，这时会取到bucketIndex位置已存储的元素，最终通过equals来比较，equals方法就是哈希码碰撞时才会执行的方法，所以说HashMap很少会用到equals。HashMap通过hashCode和equals最终判断出K是否已存在，如果已存在，则使用新V值替换旧V值，并返回旧V值，如果不存在，则存放新的键值对到bucketIndex位置。整个put过程的流程图如下：

image

我们再根据源码分析一下存储原理：

// 在此映射中关联指定值与指定键。如果该映射以前包含了一个该键的映射关系，则旧值被替换
    public V put(K key, V value) {
        // 当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因 
        if (key == null)
            return putForNullKey(value);
        // 使用hash函数预处理hashCode，计算key的hash值  
        int hash = hash(key.hashCode());//-------（1）
        // 计算key hash 值在 table 数组中的位置 
        int i = indexFor(hash, table.length);//------(2)
        // 从i出开始迭代 e,找到 key 保存的位置
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 判断该条链上是否有hash值相同的(key相同) 
            // 若存在相同，则直接覆盖value，返回旧value 
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 旧值 = 新值  
                V oldValue = e.value;
                // 将要存储的value存进去
                e.value = value;
                e.recordAccess(this);
                // 返回旧的value
                return oldValue;
            }
        }
        // 修改次数增加1 
        modCount++;
        // 将key、value添加至i位置处 
        addEntry(hash, key, value, i);
        return null;
    }

通过源码我们可以清晰看到HashMap保存数据的过程为：

首先判断key是否为null，若为null，则直接调用putForNullKey方法。若不为空则先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table数组在该位置处有元素，则通过比较是否存在相同的key，若存在则覆盖原来key的value，否则将该元素保存在链头（最先保存的元素放在链尾）。若table在该处没有元素，则直接保存。

最后还有两点需要注意的：

一、链的产生：

这是一个非常优雅的设计。系统总是将新的Entry对象添加到bucketIndex处。如果bucketIndex处已经有了对象，那么新添加的Entry对象将指向原有的Entry对象，形成一条Entry链，但是若bucketIndex处没有Entry对象，也就是e==null,那么新添加的Entry对象指向null，也就不会产生Entry链了。

二、扩容问题：

随着HashMap中元素的数量越来越多，发生碰撞的概率就越来越大，所产生的链表长度就会越来越长，这样势必会影响HashMap的速度，为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理。该临界点在当HashMap中元素的数量等于table数组长度*加载因子。但是扩容是一个非常耗时的过程，因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

3.HashMap的loadFactory和threshold是什么？是如何进行扩容的？

size：

size表示HashMap中存放KV的数量（为链表和树中的KV的总和）。

capacity：

capacity译为容量。capacity就是指HashMap中底层tab数组的数量。默认值为16。一般第一次扩容时会扩容到64，之后好像是2倍。总之，容量都是2的幂。

loadFactor:

loadFactor译为装载因子。装载因子用来衡量HashMap满的程度。loadFactor的默认值为0.75f。计算HashMap的实时装载因子的方法为：size/capacity，而不是占用数组数量去除以capacity。

threshold:

threshold表示当HashMap的size大于threshold时会执行resize操作。 threshold=capacity*loadFactor

4.为什么HashMap是线程不安全的?

我们在平时一直都说HashMap是线程不安全的，但是一直却不知道他到底是怎么不安全的，而且HashMap的使用频率还要比线程安全的HashTable要高。

HashMap线程不安全的问题要从以下三种场景说起：

1.向HashMap中插入数据的时候：

假如有A、B两个线程都要同时进入addEntry，然后计算出了相同的hash值对应了相同的数组位置，此时数组该位置还没有数据，它们就同时对该数组位置调用了createEntry，两个线程会同时得到现在的头结点，A先写入新的头结点之后，B也写入了新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。

2.HashMap扩容的时候：

在对HashMap进行扩容操作的时候会新生成一个新的容量的数组，然后对原数组的所有键值对重新进行计算和写入新的数组，之后指向新生成的数组。这时候问题就出现了：当多个线程同时进入新数组时，检测到总数量超过门限值的时候就会同时调用resize操作，各自生成新的数组并rehash后赋值给该map底层的数组table，结果最终只有最后一个主线程生成的新数组被赋值给table变量，其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候，就会用已经被赋值的table作为原始数组，这样也会有问题。所以在扩容操作的时候也有可能会引起一些并发的问题。

3.删除HashMap中的数据的时候：

删除这一块可能会出现两种线程安全问题，第一种是一个线程判断得到了指定的数组位置i并进入了循环，此时，另一个线程也在同样的位置已经删掉了i位置的那个数据了，然后第一个线程那边就没了。但是删除的话，没了倒问题不大。

再看另一种情况，当多个线程同时操作同一个数组位置的时候，也都会先取得现在状态下该位置存储的头结点，然后各自去进行计算操作，之后再把结果写会到该数组位置去，其实写回的时候可能其他的线程已经就把这个位置给修改过了，就会覆盖其他线程的修改。

最后：

其他地方还有很多可能会出现线程安全的问题，我也只查到了这些，总之HashMap是非线程安全的，在高并发的场合使用的话，要用Collections.synchronizeMap进行包装一下。

5.如何获取一个线程安全的HashMap?

1.使用synchronize：

就像HashTable使用一个synchronize来保证线程的安全，比如get和put方法：

public synchronized V get(Object key) {
       // 省略实现
    }
public synchronized V put(K key, V value) {
    // 省略实现
    }

当一个线程访问 HashTable 的同步方法时，其他线程如果也要访问同步方法，会被阻塞住。举个例子，当一个线程使用 put 方法时，另一个线程不但不可以使用 put 方法，连 get 方法都不可以。但是效率较低，所以基本不会选择这个方法。

2.ConcurrentHashMap

ConcurrentHashMap(简称CHM)是在Java 1.5作为Hashtable的替代选择新引入的，是concurrent包的重要成员。CHM不但是线程安全的，而且比HashTable和synchronizedMap的性能要好。相对于HashTable和synchronizedMap锁住了整个Map，CHM只锁住部分Map。CHM允许并发的读操作，同时通过同步锁在写操作时保持数据完整性。

3.SynchronizedMap

我们使用SynchronizedMap调用它的synchronizedMap() 方法后会返回一个 SynchronizedMap 类的对象，而在 SynchronizedMap 类中使用了 synchronized 同步关键字来保证对 Map 的操作是线程安全的。

6.HashMap使用迭代器遍历的时候如何删除一个元素？

for (Iterator<Map.Entry<String, Integer>> it = myHashMap.entrySet().iterator(); it.hasNext();){
    Map.Entry<String, Integer> item = it.next();
    //... todo with item
    it.remove();
}

7.Android 中 SparseArray VS HashMap

SparseArray是android的系统API，是专门为移动设备而定制的。用于在一定情况下取代HashMap而达到节省内存的目的。

1.空间上对比：

与HashMap相比，去掉了Hash值的存储空间，没有next的指针占用，还有其他一些小的内存占用，看着节省了不少。

2.时间上对比：

SparseArray避免了装箱的环节，不要小看装箱过程，还是很费时的。所以从源码上来看，效率谁快，就看数据量大小了。

3.插入性能时间对比：

数据量小的时候，差异并不大（当然了，数据量小，时间基准小，内容太多,就不贴数据表了，确实差异不大），当数据量大于5000左右，SparseArray，最快，HashMap最慢。但是这是顺序插入的，也就是SparseArray的理想状态。

4.查询性能时间对比：

在HashMap没有提前装箱的情况下，SparseArray 要比HashMap查询快。

总结：

在数据量小的时候一般认为1000以下，当你的key为int的时候，使用SparseArray确实是一个很不错的选择，内存大概能节省30%，相比用HashMap，因为它key值不需要装箱，所以时间性能平均来看也优于HashMap。

8.ArrayMap VS HashMap

ArrayMap相对于SparseArray，特点就是key值类型不受限，任何情况下都可以取代HashMap,但是通过研究和测试发现，ArrayMap的内存节省并不明显，也就在10%左右，但是时间性能确是最差的，当然了，1000以内的数据量也无所谓了，加上它只有在API>=19才可以使用，不建议使用。

9.SparseBooleanArray , SparseIntArray ,SparseLongArray

SparseBooleanArray，SparseIntArray，SparseLongArray，其实看名字也知道，它们跟SparseArray极其类似，只是存储类型加以限制了。SparseBooleanArray只能存储boolean类型的值，SparseIntArray只能存储int类型的值，SparseLongArray只能存储long类型的值。它们也同样实现了Cloneable接口，可以直接调用clone方法，也同样是以二分法为依据。而其他的主要方法也是一样的。

10.HashMap 和 HashTable 区别

HashMap 不是线程安全的

HashMap 是 map 接口的实现类，是将键映射到值的对象，其中键和值都是对象，并且不能包含重复键，但可以包含重复值。HashMap 允许 null key 和 null value，而 HashTable 不允许。

HashTable 是线程安全 Collection。

HashMap 是 HashTable 的轻量级实现，他们都完成了Map 接口，主要区别在于 HashMap 允许 null key 和 null value,由于非线程安全，效率上可能高于 Hashtable。

区别如下：

HashMap允许将 null 作为一个 entry 的 key 或者 value，而 Hashtable 不允许。
HashMap 把 Hashtable 的 contains 方法去掉了，改成 containsValue 和 containsKey。因为 contains 方法容易让人引起误解。
HashTable 继承自 Dictionary 类，而 HashMap 是 Java1.2 引进的 Map interface 的一个实现。
HashTable 的方法是 Synchronize 的，而 HashMap 不是，在多个线程访问 Hashtable 时，不需要自己为它的方法实现同步，而 HashMap 就必须为之提供外同步。
Hashtable 和 HashMap 采用的 hash/rehash 算法都大概一样，所以性能不会有很大的差异