性能优化01 数据结构优化

本次代码基于sdk 24
为什么数组访问速度非常快a[i]
因为是连续的内存

ArrayList get速度很快
但是如果add 或remove 靠近表头的元素 就耗性能
因为这些操作会执行System.arrayCopy

LinkedList 是双向链表 有prev 和next
插入和删除节点快 只需要改变prev和next
get->里面的Node不是一块连续的内存 需要通过轮询的方式查找 比较耗时

HashMap 轮询和增加删除都比较快
1.7之前 24之前 arrayList+链表
1.8之后 24之后 数组 + 链表 + 红黑树
HashMapEntry<K, V> table

put 根据key拿到hashCode ->装箱
table[] 大小length
hashCode % length == hashCode & length ->得到在table里面的下标
位运算更加契合CPU的运算规则 所以速度更快

image.png

hashCode & length 是求模 有可能多个hashCode求模之后得到的值是同一个
这个就是hash碰撞/hash冲突

怎么解决？
在table相同下标的位置形成链表
查找的时候 先查找table的这个下标，拿到链表后轮询
见HashMap的get方法：

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
        for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

put 如果key相同，值覆盖，需要修改value

for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

扩容：
加载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认hashMap 16
阈值 0.75 * 16 = 12
表示容量大于12的时候 会进行扩容

hashMap的大小必须是2的多少次幂（原因是-1之后每位都是1。如果有位是0，&操作之后就是0，会更容易导致hash冲突）
hashMap什么情况下效率最低 ->所有元素都hash冲突，那就是一个单链表了
扩容

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

扩容后 hashMapEntry要重新new一个
然后transfer
见resize(int newCapacity)方法
所以扩容耗性能
所以创建HashMap的时候最好先评估一下数据大小 给一个合适的初始值

table真正初始化在put方法里面

HashMap 内存浪费，25%，空间换时间
扩容的时候 2倍
Android的优化SparseArray
SparseArray：双数组 一边存key 一边存value
速度：二分查找
越用越快：因为remove的时候，把元素标记为del，不需要arraycopy, 下次put还可以复用
Key只能是int

ArrayMap 任意类型的key
Hash冲突的解决，追加，如果冲突了，往后加1个位置