HashMap原理（四）

阅读：260

目录介绍

01.HashMap线程问题
02.测试HashMap效率
03.HashMap性能分析

01.HashMap线程问题

HashMap是非线程安全的，那么测试一下，先看下测试代码

private HashMap map = new HashMap();
private void test(){
    Thread t1 = new Thread() {
        @Override
        public void run() {
            for (int i = 0; i < 100; i++) {
                map.put(new Integer(i), i);
            }
            LogUtils.d("-----执行结束----t1");
        }
    };

    Thread t2 = new Thread() {
        @Override
        public void run() {
            for (int i = 0; i < 100; i++) {
                map.put(new Integer(i), i);
            }
            LogUtils.d("-----执行结束----t2");
        }
    };

    Thread t3 = new Thread() {
        @Override
        public void run() {
            for (int i = 0; i < 100; i++) {
                map.put(new Integer(i), i);
            }
            LogUtils.d("-----执行结束----t2");
        }
    };

    Thread t4 = new Thread() {
        @Override
        public void run() {
            for (int i = 0; i < 100; i++) {
                map.get(new Integer(i));
            }
            LogUtils.d("-----执行结束----t2");
        }
    };

    Thread t5 = new Thread() {
        @Override
        public void run() {
            for (int i = 0; i < 100; i++) {
                map.get(new Integer(i));
            }
            LogUtils.d("-----执行结束----t2");
        }
    };

    Thread t6 = new Thread() {
        @Override
        public void run() {
            for (int i = 0; i < 100; i++) {
                map.get(new Integer(i));
            }
            LogUtils.d("-----执行结束----t2");
        }
    };


    t1.start();
    t2.start();
    t3.start();
    t4.start();
    t5.start();
    t6.start();
}

就是启了6个线程，不断的往一个非线程安全的HashMap中put/get内容，put的内容很简单，key和value都是从0自增的整数（这个put的内容做的并不好，以致于后来干扰了我分析问题的思路）。对HashMap做并发写操作，我原以为只不过会产生脏数据的情况，但反复运行这个程序，会出现线程t1、t2被卡住的情况，多数情况下是一个线程被卡住另一个成功结束，偶尔会6个线程都被卡住。
- 多线程下直接使用ConcurrentHashMap，解决了这个问题。
- CPU利用率过高一般是因为出现了出现了死循环，导致部分线程一直运行，占用cpu时间。问题原因就是HashMap是非线程安全的，多个线程put的时候造成了某个key值Entry key List的死循环，问题就这么产生了。
- 当另外一个线程get 这个Entry List 死循环的key的时候，这个get也会一直执行。最后结果是越来越多的线程死循环，最后导致卡住。我们一般认为HashMap重复插入某个值的时候，会覆盖之前的值，这个没错。但是对于多线程访问的时候，由于其内部实现机制(在多线程环境且未作同步的情况下，对同一个HashMap做put操作可能导致两个或以上线程同时做rehash动作，就可能导致循环键表出现，一旦出现线程将无法终止，持续占用CPU，导致CPU使用率居高不下)，就可能出现安全问题了。

02.测试HashMap效率

需求：测试下不同的初始化大小以及 key 值的 HashCode 值的分布情况的不同对 HashMap 效率的影响

测试初始化大小对 HashMap 的性能影响！！！

首先来定义作为 Key 的类，hashCode() 方法直接返回其包含的属性 value。

public class Key {

    private int value;

    public Key(int value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Key key = (Key) o;
        return value == key.value;
    }

    @Override
    public int hashCode() {
        return value;
    }
}

private static final int MAX_KEY = 20000;
private static final Key[] KEYS = new Key[MAX_KEY];

private void testHashMap(){
    for (int i = 0; i < MAX_KEY; i++) {
        KEYS[i] = new Key(i);
    }
    //测试
    for (int i = 20; i <= MAX_KEY; i *= 10) {
        test(i);
    }
}

private static void test(int size) {
    long startTime = System.currentTimeMillis();
    Map<Key, Integer> map = new HashMap<>(size);
    for (int i = 0; i < MAX_KEY; i++) {
        map.put(KEYS[i], i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("---初始化大小是：" + size + " , 所用时间：" + (endTime - startTime) + "毫秒");
}

初始化大小从 100 到 100000 之间以 10 倍的倍数递增，向 HashMap 存入同等数据量的数据，观察不同 HashMap 存入数据消耗的总时间。例子中，各个Key对象之间的哈希码值各不相同，所以键值对在哈希桶数组中的分布可以说是很均匀的了，此时主要影响性能的就是扩容机制了，由上图可以看出各个初始化大小对 HashMap 的性能影响还是很大的。

---初始化大小是：20 , 所用时间：20毫秒
---初始化大小是：200 , 所用时间：5毫秒
---初始化大小是：2000 , 所用时间：0毫秒

然后测试Key对象之间频繁发生哈希冲突时HashMap的性能
- 令 Key 类的 hashCode() 方法固定返回 100，则每个键值对在存入 HashMap 时，一定会发生哈希冲突。可以看到此时存入同等数据量的数据所用时间呈几何数增长了，此时主要影响性能的点就在于对哈希冲突的处理
```
---初始化大小是：20 , 所用时间：281毫秒
---初始化大小是：200 , 所用时间：246毫秒
---初始化大小是：2000 , 所用时间：213毫秒
```

03.HashMap性能分析

查找key的时候，时间复杂度是 O(1)，同时它也花费了更多的内存空间。
- 缺点:
- 自动装箱的存在意味着每一次插入都会有额外的对象创建。这跟垃圾回收机制一样也会影响到内存的利用。
- HashMap.Entry 对象本身是一层额外需要被创建以及被垃圾回收的对象。
- “桶” 在 HashMap 每次被压缩或扩容的时候都会被重新安排。这个操作会随着对象数量的增长而变得开销极大。
对于查找一个key时，HashMap会发生什么 ?
- 键的哈希值先被计算出来
- 在 mHashes[] 数组中二分查找此哈希值。这表明查找的时间复杂度增加到了 O(logN)。
- 一旦得到了哈希值所对应的索引 index，键值对中的键就存储在 mArray[2index] ，值存储在 mArray[2index+1]。
- 这里的时间复杂度从 O(1) 上升到 O(logN)，但是内存效率提升了。当我们在 100 左右的数据量范围内尝试时，没有耗时的问题，察觉不到时间上的差异，但我们应用的内存效率获得了提高。
Android中推荐使用ArrayMap或者SparseArray替代HashMap
- 在Android中，当涉及到快速响应的应用时，内存至关重要，因为持续地分发和释放内存会出发垃圾回收机制，这会拖慢应用运行。
- 垃圾回收时间段内，应用程序是不会运行的，最终应用使用上就显得卡顿。
- ArrayMap 使用2个数组。它的对象实例内部有用来存储对象的 Object[] mArray 和存储哈希值的 int[] mHashes。当插入一个键值对时：
  - 键/值被自动装箱。
  - 键对象被插入到 mArray[] 数组中的下一个空闲位置。
  - 值对象也会被插入到 mArray[] 数组中与键对象相邻的位置。
  - 键的哈希值会被计算出来并被插入到 mHashes[] 数组中的下一个空闲位置。

赞赏支持

课程目录

HashMap原理（四）

目录介绍

01.HashMap线程问题

02.测试HashMap效率

03.HashMap性能分析

赞赏支持