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[] 数组中的下一个空闲位置。

赞赏支持


精彩留言

发表评论