Ricky.L的随笔
0%

发表于 更新于 分类于 Disqus：

ArrayDeque特点

基于数组的双端队列。

分别用两个索引指针指示头尾元素位置，循环访问数组元素，访问头尾元素时间复杂度为O(1)

容量不够时扩容，容量增加一倍。

也可以当栈使用。

有了LinkedList实现双端队列，为什么还要用ArrayDeque？

数组在内存中是连续存储的，CPU访问内存数据具有空间局部性特点，数组对CPU缓存很友好，可以大大提升访问速度。

链表每个节点存储位置是分散不连续的，CPU缓存命中率低，CPU访问主存次数增加，速度慢。

所以需要栈和队列时，优先选择用ArrayDeque。

ArrayDeque缺点

  1. ArrayDeque较于链表的方式的缺点就是容量不够时需要扩容，耗费O(n)的时间
  2. 删除元素后不会缩容，所以不适合数据量变化大且长期处于少数据状态的情况，会浪费空间

参考

发表于 更新于 分类于 Disqus：

ArrayList存在什么问题？

ArrayList是线程不安全的。

可以用Collections.synchronizedList()加全局独占锁保证线程安全，但在读多写少的情况下，多线程读之间互斥降低了系统吞吐量。

如果读与读之间不互斥，写与写、写与读才互斥，这样可以保证最大的吞吐量，这就是CopyOnWriteArrayList。

CopyOnWriteArrayList保证线程安全的原理？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}


public E get(int index) {
    return get(getArray(), index);
}

如果用读写锁保证并发，可以保证读读之间没有阻塞等待，但有线程写数据时，读线程必须阻塞等待，这保证了每次都都可以读到最新修改的值。

CopyOnWriteArrayList牺牲了读的实时性，读操作不上锁，只在写数据时使用ReentrantLock上锁，写数据时会把原数组拷贝到新的数组中，写数据的同时再有线程读数据，读到的是之前数组的值，不保证数据实时性，只保证最终结果一致性，牺牲了数据实时性，换取了读操作没有阻塞等待。

对数据实时性要求很高的需求，不要使用CopyOnWriteArrayList。

线程1在add数据时，线程2随后get数据，不一定能获取到线程1刚add的的元素，因为线程1可能还没执行完。

CopyOnWriteArrayList存在什么问题？

  1. 读数据不是实时的，读的时候可能正在写数据，读不到最新的值，也不会阻塞等待，适合读多写少的场景
  2. 每次写数据都要复制整个数组，如果写操作频繁，会频繁触发垃圾回收，垃圾回收又会导致线程停顿，造成APP卡顿变多

CopyOnWriteArrayList适用场景？

  1. 高并发
  2. 读多写少
  3. 对读数据实时性要求不高

为什么没有扩容?

因为每次add元素都要拷贝数组，这个时间消耗是必须的，所以也没必要扩容了，拷贝数据到一个恰好比原数组多一个位置的新数组。

Vector有什么问题?

  1. Vector是线程安全的列表，底层实现也是数组，但是几乎每一个方法都加上了synchonized，多线程读操作之间会互斥，读多写少的情况下，吞吐量不高
  2. Vector扩容，容量是翻倍，指数增长，ArrayList只增长为原来的1.5倍，更节约空间。

发表于 更新于 分类于 Disqus：

问题背景

当新业务模块引入JetPack体系后，数据获取变成单一数据源，要求底层数据库查询支持监听表变化，Room天然支持返回LiveData或Flow来实现单一数据源变化响应。

但是对于老代码，有的数据来源还是内存缓存，或者GreenDao存储的，在新的业务模块也需要读取一部分老的数据，这就需要让老的数据源也支持LiveData或Flow的返回模式。

内存缓存的方式很好实现LiveData机制，只要内存缓存有监听机制，转换为LiveData即可。

GreenDao由于官方就不支持数据表监听，没办法支持，所以只能自己实现。

阅读全文 »

发表于 更新于 分类于 Disqus：

ArrayList如何扩容的？

无参构造函数中初始化一个空数组

调用add，往数组末尾添加元素前，会调用ensureCapacityInternal(size+1)，第一次会创建DEFAULT_CAPACITY（值为10）长度的数组，再会调用grow()，新的数组长度为之前长度的1.5倍，接着调用Arrays.copyOf()将旧的数组元素复制到新数组中，底层实现是System.arraycopy()。

以上是自动扩容，也可以调用ensureCapacity(minCapacity)来手动扩容，需要手动扩容因为，如果提前知道数据量很大，就可以直接扩容到指定容量，自动扩容每次都会扩容原来的1.5倍，避免频繁拷贝数组的开销。

remove和clear后没有缩容，只会把数组中不需要的元素对应的位置设置为null，以便垃圾回收。

ArrayList查询元素的时间复杂度是多少？

数组访问任意位置元素的时间复杂度为O(1)

ArrayList插入元素的时间复杂度是多少？

插入末尾时间复杂度为O(1)，因为有指针记录末尾的位置，有新元素直接填充末尾的空位，当末尾没有空位时，需要扩容，扩容为原来长度的1.5倍，扩容需要拷贝旧数组的数据到新数组，时间复杂度是O(n），所以插入元素到末尾的均摊时间复杂度是O(1)。

插入元素到中间位置的时间复杂度较高，因为要把插入位置后面所有元素后移一位，设数组长度为n，插入第1、2、3、… 、n-1、n个位置，分别需要移动元素的个数是n、n-1、n-2、… 、2、1，由等差数列求和公式得结果为n(n+1)/2，除以n得平均移动(n+1)/2个，所以插入到中间位置的平均时间复杂度是O(n)。

ArrayList删除元素的时间复杂度是多少？

与插入元素的情况一样，删除末尾元素时间复杂度为O(1)，删除中间位置的元素要把该位置后面的元素都前移一位，平均时间复杂度为O(n)

ArrayList与LinkedList有何区别？

  1. ArrayList基于数组实现，容量不够时会动态扩容；LinkedList基于链表实现，实际是是一个双向链表，同时可以作为队列、栈使用
  2. ArrayList适合随机访问数据，时间复杂度O(1)；LinkedList不适合随机访问数据，因为这会遍历链表，最坏情况下访问最后一个元素，要遍历整个链表，时间复杂度O(n)
  3. LinkedList适合插入和删除首尾元素，时间复杂度O(1)；ArrayList插入和删除尾元素，其实是在数组的末尾填充元素，时间复杂度O(1)，插入尾元素可能会触发扩容，扩容时会拷贝数组，时间复杂度会达到O(n)，ArrayList插入和删除非末尾元素，需要移动操作，时间复杂度O(n)
  4. LinkedList需要占用更多的内存，因为每个结点除了存储元素数据外，还有额外的链表指针，ArrayList底层是数组，存储的直接是元素数据
  5. ArrayList对于CPU缓存命中率友好，因为存储空间连续，符合数据访问的空间局部性特点

如何求两个ArrayList的交集、并集、差集？

并集：addAll

交集：retainAll

差集：removeAll

ArrayList序列化有什么注意事项？

底层的elementData数组，可能没有填充满，所以不能直接序列化，会浪费空间，序列化时要先写入数组元素真实个数，再写入数组中实际存储的元素

Arrays.asList(T… a)有什么坑

  1. 传递一个原始数据类型的数组，例如int[]，会只被当做一个元素，只能使用对象类型的数组
  2. 得到的list无法add、remove、clear，会抛出异常

ArrayList有什么坑？

List.remove()有两个。

一个public E remove(int index)

一个是public boolean remove(Object o)

容易调用不是预期的重载方法。

ArrayList单线程遍历然后删除元素会有什么问题？

索引错位。

用Iterartor的next迭代列表的时候，通过ArrayList的remove方法移除元素会抛出ConcurrentModificationException，因为迭代器迭代的时候，内部也是用一个int类型指针记录位置的，要是外面删除了元素，位置就错位了，迭代就不准了。

参考

发表于 更新于 分类于 Disqus：

LinkedHashMap特点

作用：记录HashMap插入元素的顺序或访问元素的顺序

原理：双向链表和哈希表的结合

使用场景：适用于实现缓存，用空间换时间，如LRU

继承HashMap，大部分操作和HashMap实现一致

元素的顺序在访问时是怎样体现的？

构造函数可以指定accessOrder：

  • true表示记录元素访问顺序。
  • false表示记录元素插入的顺序，默认为false。

创建一个记录元素访问顺序的LinkedHashMap：
new LinkedHashMap(16, 0.75f, true)

  • 记录元素插入顺序时，通过迭代器遍历时，先插入的元素会先访问到。
  • 记录元素访问顺序时，刚访问过的元素会调整到链表末尾，通过迭代器遍历时，先遍历到的是最久没有被访问过的元素。

为什么最新插入和最后访问的要放在末尾？

插入新元素默认就是在链表尾部插入，是符合常规逻辑的，最新访问的放在末尾也就是统一这个规则了。

LinkedHashMap实现原理？

双向链表的结点类继承HashMap桶中链表的结点类，增加了前后指针，实际效果如下：

LinkedHashMap有什么应用？

LRU缓存。

用LinkedHashMap手撕 LeetCode.146. LRU 缓存机制（难度：中等）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class LRUCache(private val capacity: Int) {
    private val map = LinkedHashMap<Int, Int>(16, 0.75f, true)

    fun get(key: Int): Int {
        return map[key] ?: -1
    }

    fun put(key: Int, value: Int) {
        if (map.size == capacity && !map.containsKey(key)) {
            val oldest = map.iterator().next()
            map.remove(oldest.key)
        }
        map[key] = value
    }
}

发表于 更新于 分类于 Disqus：

ArrayMap、SparseArray、HashMap的区别？

  • 数据结构

    • ArrayMap和SparseArray采用的都是两个数组，Android专门针对内存优化而设计的
    • HashMap采用的是数据+链表+红黑树

  • 内存优化

    • ArrayMap比HashMap更节省内存，综合性能方面在数据量不大的情况下，推荐使用ArrayMap；
    • Hash需要创建一个额外对象来保存每一个放入map的entry，且容量的利用率比ArrayMap低，整体更消耗内存
    • SparseArray比ArrayMap节省1/3的内存，但SparseArray只能用于key为int类型的Map，所以int类型的Map数据推荐使用SparseArray；

  • 性能方面：

    • ArrayMap查找时间复杂度O(logN)；ArrayMap增加、删除操作需要移动成员，速度相比较慢，对于个数小于1000的情况下，性能基本没有明显差异
    • HashMap查找、修改的时间复杂度为O(1)；
    • SparseArray适合频繁删除和插入来回执行的场景，性能比较好

  • 缓存机制

    • ArrayMap针对容量为4和8的对象进行缓存，可避免频繁创建对象而分配内存与GC操作，这两个缓存池大小的上限为10个，防止缓存池无限增大；
    • HashMap没有缓存机制
    • SparseArray有延迟回收机制，提供删除效率，同时减少数组成员来回拷贝的次数

  • 扩容机制

    • ArrayMap是在容量满的时机触发容量扩大至原来的1.5倍，在容量不足1/3时触发内存收缩至原来的0.5倍，更节省的内存扩容机制
    • HashMap是在容量的0.75倍时触发容量扩大至原来的2倍，且没有内存收缩机制。HashMap扩容过程有hash重建，相对耗时。所以能大致知道数据量，可指定创建指定容量的对象，能减少性能浪费。

  • 并发问题

    • ArrayMap是非线程安全的类，大量方法中通过对mSize判断是否发生并发，来决定抛出异常。但没有覆盖到所有并发场景，比如大小没有改变而成员内容改变的情况就没有覆盖
    • HashMap是在每次增加、删除、清空操作的过程将modCount加1，在关键方法内进入时记录当前mCount，执行完核心逻辑后，再检测mCount是否被其他线程修改，来决定抛出异常。这一点的处理比ArrayMap更有全面。

总结：

  • HashMap的查找和插入时间复杂度为O(1)的代价是牺牲大量的内存来实现的。
  • 而SparseArray和ArrayMap性能略逊于HashMap，但更节省内存。
  • SparseArray的key是int类型，ArrayMap的key是任意类型。
  • SparseArray删除元素是延迟删除，减少数组拷贝的频次。
  • ArrayMap有对容量4和8的缓存机制，避免频繁的内存分配和垃圾回收。

Android中的小数据量的哈希表，Google推荐数据量小于1000使用ArrayMap，大于1000使用HashMap。

为什么ArrayMap数据量大了性能不如HashMap？数据量小了性能比HashMap好？

ArrayMap中的 mHashs 数组以升序的方式保存了所有的 hash code，在查找数据时则通过二分查找 hash code 所对应的 index。这也是它的 get() 比 HashMap 慢的根据原因所在。

插入、删除需要移动数组的元素，数据多了的话，速度也相对较慢，数据少了影响较小。

ArrayMap底层存储结构是怎样的？

  • mHashes是一个记录所有key的hashcode值组成的数组，是从小到大的排序方式；
  • mArray是一个记录着key-value键值对所组成的数组，是mHashes大小的2倍；

为什么mArray的大小是mHahses的2倍？

因为mArray存储了key和value，所以需要2倍于mHashes的容量。

mHashes 在 index 处存储了 key 的 hash code，而 mArray 则在 hash code 的 index<<1 处存储 key，在 index<<1 + 1 处存储 value。简单点说就是偶数处存储 key，相邻奇数处存储 value。

多个key的hashCode发生冲突时是怎么存储数据的？

HashMap用的是拉链法把同一个hashCode元素放在一个桶中

ArrayMap用的是开放定址法之线性探测法

相同的hashCode存储在mHashes数组中相邻的位置，把原来数组中该位置之后的元素全部后移一位

例子：

index == 0 时 和 index == 1时的 hash code 是一样的，说明 key1 与 key2 的 hash code 是一样的，也就是存在 hash 冲突了。那么，如上，这里的解决办法就是 hash code 存储了 2 份，而 key-value 分别存储一份。

ArrayMap.indexOf(key, hash)原理?

源码的注释已经说的很明白

  1. 在mHashes中二分查找hash的索引
  2. 如果mHashes中没找到hash，说明不存在这个元素，返回二分查找得出的应该插入的位置，以保障mHashes存储的hash保持升序
  3. 如果mHashes中找到了hash，有两种情况：找到元素了 或 存在哈希冲突，这一点通过mArray存储的key和方法传入的key是否相等来判断，如果相等说明找到元素了，不相等则没有找到，没有找到要返回待插入的位置
  4. 由于相同的hash在mHashes中存储在相邻的位置，如果mHashes中找到了hash，但是mArray中存储的key不相等，则往右往左分别寻找相同hash对应的mArray中的key是否相等

ArrayMap.put(key, value)原理?

  1. 求key的hashCode
  2. 通过indexOf(key, hash)计算新的hash应该插入mHashes数组中什么位置
  3. 如果index > 0 说明之前这个key已经存了值，替换为新的value就结束put流程
  4. index < 0 说明mHashes里不存在这个hash，index为待插入的位置
  5. 如果容量不够了，就申请新的数组，容量为之前的1.5倍，把旧数组的值全部拷贝到新的数组
  6. index后面的元素全部后移一位，给index的位置腾出空间
  7. 存储hash到mHashes[index]，存储key、value到mArray的index * 2和index * 2 + 1的位置

为什么通过key求得index后要左移1位？

因为这个index是mHashes的索引，mHashes数组长度是mArray数组长度的一半，索引乘以2，就是作为mArray的索引

ArrayMap.remove()原理？

一般情况下删除一个数据，只需要将 index 后面的数据都往 index 方向移一位，然后删除末位数即可。

如果再满足缩容的条件就进行缩容，条件是mHashs长度大于 2 * BASE_SIZE 且 实际元素个数小于mHashs长度的1/3，就把容量压缩为实际元素大小的1.5倍

为什么是1.5倍，这样保证不会频繁的创建数组，也不会浪费太多的空间，平衡了性能

mHashes里存的hashcode为什么要升序？

因为要二分查找获取插入位置。

为什么mHashes中查找元素要二分查找？不能用HashMap的索引定位法吗？

HashMap是怎么计算索引位置的？

HashMap是直接用数组大小与key的hashCode做与操作得到数组索引。

为什么ArrayMap不按照HashMap计算索引的方式来做呢？

因为扩容后会重新hash，让元素分布的更均匀以较少哈希冲突，重新hash过程比较耗时，实现起来也比较复杂。

数据量小的情况下，用二分查找足够应付。

ArrayMap为什么要设计一个缓存机制？

很多场景可能起初都是数据很少，为了减少频繁地创建和回收数组，特意设计了两个缓存池，分别缓存大小为4和8的ArrayMap对象，这两个长度的Map根据统计信息应该用的很多。

ArrayMap缓存机制实现原理？

freeArrays(hashes, array, size) 会把hashes数组和array数组用链表的形式存储下来，头结点用mBaseCache、mTwiceBaseCache存储，分别表示数组长度为4和8的缓存

freeArrays()触发时机:

  • 当执行removeAt()移除最后一个元素的情况
  • 当执行clear()清理的情况
  • 当执行ensureCapacity()在当前容量小于预期容量的情况下, 先执行allocArrays,再执行freeArrays
  • 当执行put()在容量满的情况下, 先执行allocArrays, 再执行freeArrays

当allocArrays分配内存时，如果所需要分配的大小等于4或者8，且相对应的缓冲池不为空，则会从相应缓存池中取出缓存的mArray和mHashes。

这里需要注意的是只有大小为4或者8的内存分配才有可能从缓存池取数据，因为freeArrays过程放入缓存池的大小只有4或8，对于其他大小的内存分配则需要创建新的数组。

优化小技巧，对于分配数据不超过8的对象的情况下，一定要创建4或者8大小，否则浪费了缓存机制。比如ArrayMap[7]就是不友好的写法，建议写成ArrayMap[8]。

两个缓存池大小上限为10个。

扩容的条件？

mSize是实际存储的元素的个数

当mSize大于或等于mHashes数组长度时需要扩容，新容量的规则如下：

  • 当map个数满足条件 osize<4时，则扩容后的大小为4；
  • 当map个数满足条件 4<= osize < 8时，则扩容后的大小为8；
  • 当map个数满足条件 osize>=8时，则扩容后的大小为原来的1.5倍；

缩容的条件？

当数组内存的大小大于8，且已存储数据的个数mSize小于数组空间大小的1/3的情况下，需要收紧数据的内容容量，分配新的数组，老的内存靠虚拟机自动回收。

  • 如果mSize<=8，则设置新大小为8；
  • 如果mSize> 8，则设置新大小为mSize的1.5倍。

也就是说在数据较大的情况下，当内存使用量不足1/3的情况下，内存数组会收紧50%

参考资料

发表于 更新于 分类于 Disqus：

稀疏表是什么？

key为整数的哈希表

稀疏表特点

  • Key为int类型的哈希表，避免了Integer自动装箱。
  • 底层用数组存储元素，一个数组存储key，一个数组存储value，key是有序的，通过二分查找来定位元素。
  • 插入元素会移动数组，remove的时候只设置了一个removed标记位，避免频繁移动数组元素。
  • 数据量大的时候，复制数组时间就长了，查找时间也长了。
  • 好处是不需要额外的结构体，比较节约空间，数据量较小情况下访问想效率比较高。

SparseArray相比HashMap解决了什么？

优点：

  1. 避免了基本数据类型的装箱操作
  2. 不需要额外的结构体，单个元素的存储成本更低
  3. 数据量小的情况下，随机访问的效率更高，因为不需要额外复杂操作、删除元素也是延迟的

缺点：

  1. 插入操作需要复制数组，增删效率降低
  2. 数据量巨大时，复制数组成本巨大，gc()成本也巨大
  3. 数据量巨大时，查询效率也会明显下降，因为需要二分查找，而不是直接哈希命中

参考：

SparseArray适用场景？

原则：

  1. 数据量不大（千这个数量级以内）。
  2. 空间比时间重要，例如移动端对内存使用量敏感。
  3. 需要使用Map，且key为int类型。

例如：
如果有一个ViewPager的每个页面都有一个图表，并且图表的点有上千个，而ViewPager会缓存左右两页，至少要开3个图表，用HashMap明显占用内存更多，容易引发内存溢出，而且自动装箱的消耗更多，用SparseArray肯定更快，内存占用更小。

SparseArray.put(int key, E value)原理？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Adds a mapping from the specified key to the specified value,
 * replacing the previous mapping from the specified key if there
 * was one.
 */
public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;

        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        if (mGarbage && mSize >= mKeys.length) {
            gc();

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

上面这段代码是一次插入数据的操作，单看的话有些难懂，因为插入跟删除之间有一定的关系，所以要看懂这段代码，还必须搞懂删除的逻辑。在看删除之前，还是先大体梳理一下插入的几个特点：

  • 存放key的数组是有序的（二分查找的前提条件）
  • 如果冲突，新值直接覆盖原值，并且不会返回原值（HashMap会返回原值）
  • 如果当前要插入的 key 的索引上的值为DELETE，直接覆盖
  • 前几步都失败了，检查是否需要gc()并且在该索引上插入数据

参考：

GrowingArrayUtils.insert()的原理？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Inserts an element into the array at the specified index, growing the array if there is no
 * more room.
 *
 * @param array The array to which to append the element. Must NOT be null.
 * @param currentSize The number of elements in the array. Must be less than or equal to
 *                    array.length.
 * @param element The element to insert.
 * @return the array to which the element was appended. This may be different than the given
 *         array.
 */
@SuppressWarnings("unchecked")
public static <T> T[] insert(T[] array, int currentSize, int index, T element) {
    if (currentSize + 1 <= array.length) {
        System.arraycopy(array, index, array, index + 1, currentSize - index);
        array[index] = element;
        return array;
    }

    T[] newArray = (T[]) Array.newInstance(array.getClass().getComponentType(),
            growSize(currentSize));
    System.arraycopy(array, 0, newArray, 0, index);
    newArray[index] = element;
    System.arraycopy(array, index, newArray, index + 1, array.length - index);
    return newArray;
}

如果当前数据个数并不超过数组长度，直接把待插入位置后面的元素全部后移一位，腾出空间给新元素。

如果数据总个数超过了数组容纳的长度，需要扩容，扩容大小为growSize(currentSize)求得，为原大小的两倍。

1
2
3
4
5
6
7
8
9

/**
 * Given the current size of an array, returns an ideal size to which the array should grow.
 * This is typically double the given size, but should not be relied upon to do so in the
 * future.
 */
public static int growSize(int currentSize) {
    return currentSize <= 4 ? 8 : currentSize * 2;
}

然后根据新大小创建新的数组，然后：

  1. 把原数组中待插入位置前面的元素都复制到新数组的前面
  2. 新数组中指定位置插入新元素
  3. 把原数组中待插入位置后面的元素都复制到新数组中插入元素的后面

SparseArray.remove(int key)原理?

通过key二分查找到index，然后讲DELETED赋值给mValues[index]，标记这个位置会删除

为什么删除标记位DELETED？而不是直接删除元素？

直接删除元素会复制数组，如果删除比较频繁，就会降低性能，这里是为了避免频繁进行数组拷贝调整

什么时候会清理掉DELETED的元素？

SparseArray.gc()里会清理

SparseArray.gc()的原理？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private void gc() {
    // Log.e("SparseArray", "gc start with " + mSize);

    int n = mSize;
    int o = 0;
    int[] keys = mKeys;
    Object[] values = mValues;

    for (int i = 0; i < n; i++) {
        Object val = values[i];

        if (val != DELETED) {
            if (i != o) {
                keys[o] = keys[i];
                values[o] = val;
                values[i] = null;
            }

            o++;
        }
    }

    mGarbage = false;
    mSize = o;

    // Log.e("SparseArray", "gc end with " + mSize);
}

mValues里如果没有DELETED，那么i和o应该是相等的，但是如果有DELETED，o就会小于i，然后就可以把元素全部前移到数组头部，把空位留在数组尾部，相当于碎片整理了一下，留下了尾部整块的空闲空间。

什么时候触发GC()？

以下方法会调用gc()：

put的时候如果发现数组大小不够，就清理。

size()求大小需要求得正确的大小。

SparseArray使用过程有什么坑？

indexOfValue比较的是value的指针，而并没有调用equals方法。

如果value是String就有问题。

如果是Integer，在Integer的缓存范围内也有问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * Returns an index for which {@link #valueAt} would return the
 * specified value, or a negative number if no keys map to the
 * specified value.
 * <p>Beware that this is a linear search, unlike lookups by key,
 * and that multiple keys can map to the same value and this will
 * find only one of them.
 * <p>Note also that unlike most collections' {@code indexOf} methods,
 * this method compares values using {@code ==} rather than {@code equals}.
 */
public int indexOfValue(E value) {
    if (mGarbage) {
        gc();
    }

    for (int i = 0; i < mSize; i++) {
        if (mValues[i] == value) {
            return i;
        }
    }

    return -1;
}

参考资料

发表于 更新于 分类于 Disqus：

TreeMap作用

  • 元素可以按key保持顺序。
  • 因为有序，提供了很多范围查询的方法，非常方便。

TreeMap的实现

TreeMap实现了NavigableMap接口，该接口又继承SortedMap接口，两个提供了很多范围查询的方法，非常方便。

用红黑树实现，插入、删除、查询的平均时间复杂度都是log(n)。

TreeMap也是非线程安全的，为什么不提供ConcurrentTreeMap?

  1. 因为红黑树的结构调整可能涉及整个树的结点，这样并发下就要锁住很多结点，使用跳表会更局部一点，只锁住局部的几个结点，并发性能更高。
  2. 红黑树加锁实现起来比较复杂，跳表是链表加锁比较容易实现

可以用过Collections.synchronizedSortedMap()保证线程安全，也可以改用ConcurrentSkipListMap并发性能更好。

TreeMap为什么用红黑树不用AVL树？

跟HashMap中的问题一样。

红黑树的3结点可以吸收变化，在多次使用中可以减少调整数据结构的次数，从而提升性能。

ConcurrentSkipListMap是什么？

跳表：链表+多级索引（多层链表）。

  • 给有序链表再增加若干层额外的指针索引，用空间换时间。
  • 每一层都是一个有序链表。
  • 实际效果类似于平衡二叉搜索树。
  • 插入、删除、查询的平均时间复杂度都是log(n)。
  • 支持按key排序所有元素，也支持快速查找。

跳表的数据结构存在什么问题？

按照理想的生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到O(log n)。

但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。

skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中。

跳表与红黑树区别？

  1. 红黑树为了保持平衡有可能会调整很多结点甚至整个树，而跳表只要修改相邻结点更加的局部，跳表调整次数少性能也就高，同时并发加锁时，锁住的结点更少，可以减少竞争
  2. 跳表的区间查询更高效，因为找到链表头结点顺序遍历就行了，红黑树需要中序遍历相对比较复杂
  3. 跳表占用空间更少，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。

ConcurrentSkipListMap存在什么问题？

size方法求得链表长度要遍历整个链表，并且没有加锁，多线程高并发下这个方法返回值并不准确，高并发下使用size的意义不大。

参考资料

发表于 更新于 分类于 Disqus：

特点

高性能且线程安全的哈希表。

线程安全是怎么实现的？

Java7中ConcurrentHashMap将哈希表分割成为多个段（Segment），每一个段继承ReentrantLock，对每一段进行加锁。每个Segment里类似又有一个小的HashMap，等于是双重哈希表。

Java8中采用了自旋CAS和synchronzied保证线程安全，锁的粒度调整为对table数组中每个元素进行加锁；put元素时，定位到桶位置后，通过synchronzied给桶中链表首节点或红黑树根节点加锁。这样多线程竞争哈希表同一个桶位置的几率又降低了。

java8的ConcurrentHashMap的数据结构参考java8的HashMap，采用数组+链表+红黑树。

  • put方法里，是一个无限循环，即自旋，修改table数组都是通过cas操作，自旋锁的机制避免了阻塞和恢复线程的上下文切换开销。

  • 只要当前桶位置没有元素，就先自旋CAS进行更新。

  • 存在hash冲突或修改已有的值时，需要进入桶内部的链表或红黑树进行操作时，才开始用synchronized真正加锁。

get是不加锁的，所以与CopyOnWriteArrayList一样，不保证读数据的实时性，数据是弱一致性。

size的求法和LongAdder里的思路一样，将大小数据分段累加，避免多线程竞争，用自旋cas保证数据更新的原子性。

不能解决什么问题？

因为数据是弱一致性的，get时并不加锁，所以对读数据实时性要求高的需求不能满足。

例如线程1在某一时刻执行了put(key, value)，先线程2随后立即get(key)不一定能读取到线程1刚put的，因为put可能正在进行中还没结束。

扩容机制是怎样的？

本来一个线程扩容时，其他线程应该都阻塞等待这个线程扩容完成后才能对哈希表进行读写，这就成了并发的瓶颈。

ConcurrentHashMap具体实现是，反正你闲着也是闲着，不如一起来扩容。

扩容时nextTable会指向扩容后的数组，扩容方法transfer里通过自旋进行。

多个线程通过sizeCtl判断当前所处状态，再通过transferIndex协调各线程应该操作哪一些桶。

参考：

跟同样是线程安全的Hashtable有何区别？

Hashtable的线程安全是对整个哈希表上锁（在多数方法上加上sychronized），其中一个线程访问哈希表时，其他线程只能等待，很多没有必要上锁的场景也上锁，因此在多线程竞争激烈的情况下整体访问速度会变慢。

ConcurrentHashMap把哈希表分割成若干个段，修改每一段时仅针对访问的段上锁，不同的线程访问不同的段时互不干扰，减少了多个线程争抢同一把锁的几率，减少了线程等待的时间，所以提高了性能。

分段锁是怎么实现的？

get方法不加锁，结点类里的value设置了volatile保证了value在多线程下的可见性，保证get到value最新的修改值。

总结：

  1. 循环+CAS实现自旋锁，减少线程阻塞恢复的上下文切换消耗
  2. size更新采用LongAdder分段锁思想，减少竞争
  3. LongAdder机制中的字节填充解决伪共享
  4. 多线程协同分组扩容。

与Collections.synchronizedMap()的区别？

Collections.synchronizedMap()对HashMap做了一层装饰，用synchronized锁住整个哈希表，以保证各操作的线程安全，锁的粒度比较大。
性能比ConcurrentHashMap更差，但可以保证读的实时性。

参考资料

发表于 更新于 分类于 Disqus：

HashMap源码

JDK 1.7：

JDK 1.8：

HashMap特点

  1. 非线程安全，所以存取速度快
  2. 可以接受null的键和值
  3. 不保证key有序
  4. key的顺序会随时间变化（动态调整大小后会变化）

散列过程

  1. 通过散列函数，用元素的key计算出元素在数组中的索引位置
  2. 解决散列冲突，即相同散列值（数组索引位置）元素如何存取

散列函数的选取标准

  1. 易于计算
  2. 均匀分布所有键

拉链法查找一个元素的最少、最坏、平均次数分别是多少？

设哈希表大小为m，已存储的元素个数为n

如果散列函数把所有元素散列到一个位置，链表的长度就是n，最坏情况下就是查找链表中最后一个元素，查找次数是n

如果散列函数散列到哈希表每个位置的概率相同，此时元素分布最均匀，拉链法相当于把n个元素分为m组，那么每组（链表）长度最多为n/m，最坏情况下查找链表最后一个元素，需要n/m次

桶（bucket）是什么意思？

HashMap内部的哈希表由数组实现，数组的每一个位置称为桶，存储一个链表的头结点，或红黑树的根节点，一个桶下所有元素key的hashCode都相同，元素存储在哪一个桶是根据元素key计算出数组索引位置而定的

什么情况下会要求哈希表的大小要是质数？

简述：

  • 关注哈希表的大小是因为求得元素在哈希表中存储存储位置是通过 key的hashCode % 哈希表大小 得到，如果散列函数计算结果不均匀，容易产生散列冲突，提高了查找次数。
  • 质数不容易被整除，故而可以让计算出的索引分布的比较均匀。合数有公因子，计算出的索引位置容易聚集在公因数的位置，产生较多的散列冲突。

key与哈希表大小互质，这样取模的结果就分散的比较均匀。

如果key可以整除哈希表大小，如果key容易在公因数的位置产生聚集，就会产生较多的散列冲突。

使用质数作为容量，可以使元素更分散，减少冲突；

如果用合数作为容量，会使元素聚集，增加冲突，增加查找次数。

一般是通过除留取余法确定元素在数组中存储索引位置，即：

元素在数组中的存储位置 = key的hashCode % 哈希表长度

假如关键字是随机分布的，那么无所谓一定要模质数。但在实际中往往关键字有某种规律，例如大量的等差数列，那么公差和模数不互质的时候发生碰撞的概率会变大，而用质数就可以很大程度上回避这个问题。

例如2 4 6 8 10 12这6个数，如果对 6 取余 得到 2 4 0 2 4 0 只会得到3种HASH值，冲突会很多，并且呈现以合数的因子为间隔增长；如果对 7取余 得到 2 4 6 1 3 5 得到6种HASH值，没有冲突。

用质数作为数组容量使得任何数想整除它是不可能的，因此探测序列最终会检查到所有单元，冲突较少。

当散列函数计算结果的均匀性较差时，最好使用质数作为哈希表大小可以在除留取余时使得计算出的索引位置分布的更均匀。

但是库一般都会提供散列比较均匀的散列函数，只要散列函数设计的均匀，什么数做桶的大小都行，有时为了方便支持桶的动态扩容或者避免使用除法，桶的大小使用2的幂。

参考资料：

为什么桶容量要是2的次方？

散列表用数组实现时，要计算元素应当存储在数组的哪个位置（索引），应当将元素key的hashCode对散列表大小取模，取模结果就是元素要存放在数组的索引位置。

如果key的hashCode函数不能把key散列的均匀，就需要用质数作为哈希表大小，在除留取余的求数组索引时能够让元素分布的比较均匀。

如果key的hashCode能够散列的比较均匀，那么其实用什么数作为哈希表大小都可以。

桶容量为2的幂时取模的好处：
1.可以用位运算取模，计算速度更快，位运算也很方便。
2.可以让元素分布的均匀，减少散列冲突。
3.方便扩容计算，扩容也只需要乘以2，容量左移一位。

为什么2的幂的容量可以让元素分布更均匀？

位运算对2的幂取模过程：一个二进制数乘以2的n次方相当于将该数左移n位，一个二进制数除以2的n次方相当于将该数右移n位，右移出界的部分就是余数，其实也就是原数低n位，取低n位的数，只需要将原数跟低位是n个1的二进制数做与操作就可以得到，低位是n个1的二进制数可以由2的n次方再减1得到。

如果对不是2的幂的数进行位运算取模，假设这个数是x，x-1的二进制数一定不是全部都是1，而是含有0，此时x-1与原数做与操作后，那些有0的位置都会用不到，造成空间浪费，也增大了散列冲突。如果x-1全部是1的话，只要key的hashCode的二进制中的1在低n位分布均匀，就可以保证计算index的过程是分布均匀的，要求x-1的二进制全部是1，那么x就是2的幂。

通过构造函数传入不是2的幂的容量值会怎样？

会找一个最接近传入容量的2的幂作为实际桶的容量。

哈希表容量是2的幂会有什么问题？

key的hash取余求索引时，会截断hash的高位，如果多个key的hash的低位比较固定，高位变化较大，那么最后计算的散列冲突就很多了。

所以需要扰动函数处理一下key的hash，把高位的变化信息传递到低位。

扰动函数是什么，起到什么作用？

存储一个元素时，需要决定该元素应该存储在table（桶）中哪一个位置，需要用元素的key的hashCode对桶容量做取模运算来获得要存储的数组索引位置。

如果桶容量较小，取模操作会仅对key.hashCode()的低位做运算，如果多个元素的key的hashCode()低位相同，只是高位不同，那么冲突就较多，所以需要将高位和低位结合起来取模，减少冲突，避免散列分布不均。

所以在对hashCode做取模运算之前，还需要让hashCode经过扰动函数扰动一下。

jdk1.8中对key的hashCode的扰动函数做了优化：

1
2
3
4
static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

即将key.hashCode()的低16位和高16位做异或运算。

仅仅异或一下做扰动，权衡了速度、性能、质量，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。

为什么是右移16位？

推测：因为java中int是32位的，高16位和低16位异或已经算是顾全到了数字的二进制的每一位。

实际：权衡了速度、性能、质量

参考资料：

扰动函数为什么是异或运算？

  1. 实现简单，运算快捷
  2. 对参与运算的两方的二进制的每一位都各自有50%的概率影响结果输出

参考资料：

桶的最大容量为什么是2的30次方，不是2的31次方？

java中int是32位，理论上1可以最多左移31位，因为1不移动就占了1位，所以可以移动的位数是32-1=31位；而虚拟机规定int类型最高位是符号位，符号位不参与移动，可移动位数就是31-1=30位

两个key对象的hashCode相同，如何获取value对象?

在遍历该桶的链表，链表中每个节点保存了键值对信息，将目标key与每个节点的key调用equals方法比较，相等的则为想要找到的节点，取其value对象。

什么对象适合做为HashMap的key?

使用String，Integer等系统类比较好，因为他们的hashCode方法实现是比较均匀的，可以减少散列冲突。

其次这些类一旦创建都是不可变的，一来可以缓存hashCode，二来保证唯一性，三来线程安全。

自定义对象实现hashCode()方法有什么注意事项？

原则：
一个对象的hashCode应该认为有均等的机会得到2的32次方中的任意一个32位整数值。

《算法4》节选

一个优秀的散列方法需要满足三个条件：

  • 一致性 - 等价的键必然产生相等的散列值
  • 高效性 - 计算简便
  • 均匀性 - 均匀地散列所有的键

保证均匀性的最好办法也许是保证键的每一位都在散列值的计算中起到了相同的作用，实现散列函数最常见的错误是忽略了高位的键。

可以参考String的hashCode设计，kotlin的data class自动生成的hashCode以及集合类的hashCode算法都很相似。

需要使用不可变的属性实现hashCode()方法，因为：

  1. 可以在计算一次哈希值后缓存起来，提高哈希表的读取速度。
  2. 如果key在放入哈希表时和取出哈希表时hashCode()发生变化，则会取不到之前存放的对象。
  3. 不可变的属性是线程安全的。

装载因子是什么？

哈希表中已存储元素个数与哈希表总大小比值，即已存储元素个数与桶个数比值。

装载因子越大，说明填充率高，空间利用率高，但是散列冲突可能性增大。

装载因子越小，说明填充率低，浪费很多空间，但是散列冲突可能性减小。

冲突越多，查找元素的时间越长，所以必须在时间和空间上进行权衡。

装载因子有什么作用？

装载因子 = 已存储的元素个数 / 桶大小

HashMap构造时可以传入一个装载因子，不传入的话会使用默认的装载因子0.75，构造时规定这个装载因子意思是装载因子的最大值。

随着哈希表中存储元素的个数增多，填充率越高，实际的装载因子会逐渐增大，当 实际装载因子 大于 预设装载因子 时，为了避免大量的散列冲突，要增大桶的数量，HashMap会将通大小调整为原来的两倍，因为桶大小要求是2的幂，所以就扩大2倍。

桶容量是如何动态扩展的？

当 已存储元素个数 超过 哈希表大小 * 装载因子，会扩容至原大小的两倍，并对部分元素重新散列。

当put元素时，发现已存储元素个数超过threshold时，会触发扩容。

threshold的首次赋值由构造HashMap时传入的初始容量和装载因子决定。

threshold = 初始容量 * 装载因子

每次扩容桶（table）大小会变为原来两倍，threshold也会变为原来的两倍。

构造函数传入不是2的幂的初始容量会怎样？

不管传什么初始容量，都会经由tableSizeFor()计算得到大于等于传入的初始容量的最小的2的幂作为桶的实际容量大小

在put()时触发resize()，threshold也会被重新赋值为桶容量乘以装载因子。

tableSizeFor()算法过程是怎样的？

1
2
3
4
5
6
7
8
9
10
11
12
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
	int n = cap - 1;
	n |= n >>> 1;
	n |= n >>> 2;
	n |= n >>> 4;
	n |= n >>> 8;
	n |= n >>> 16;
	return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

分三种情况

  1. cap小于0，返回1
  2. cap经过位运算后大于等于MAXIMUM_CAPACITY，返回MAXIMUM_CAPACITY
  3. cap经过位运算后返回n+1

先考虑正常的情况，对于一个给定的cap，分为两种情况，cap可能是2的幂或非2的幂。

  1. 当cap不是2的幂，例如10，二进制为1010，cap - 1 = 1001，几个右移操作实际的结果就是从cap - 1的二进制的1的最高位开始到最低位全部变成1，最后返回n + 1就是2的幂了
  2. 当cap是2的幂，例如16，二进制为10000，cap-1 = 1111，右移操作后n还是为1111，n+1就还是16

所以正常情况下tableSizeFor()得出的就是大于等于cap的数

如果cap一开始不减1，当cap是2的幂时，最后计算得出的就会是cap的2倍

cap小于0，没有实际的意义，不能表示桶容量，故而返回最小正整数1

cap大于等于MAXIMUM_CAPACITY时，MAXIMUM_CAPACITY是2的30次方，此时cap的二进制最高位1是在第31位，逻辑右移再加1会得到32个1，int中最高位（第32位）是符号位，最高位1表示负数了，没有意义，故而将最大值限定在2的30次方，2的30次方减1的二进制是从第1位到第30位全都是1

参考资料：

为什么要调整桶大小？

为了减少散列冲突，减少元素查找次数

为什么桶初始容量是16？

这个问题不好解答可以考虑边界情况，桶容量过大、过小会导致什么

桶容量过大会导致大量空间浪费

桶容量过小会导致频繁扩容，扩容一次是耗时的

16应当是一个权衡评估后得出的值

默认装载因子为什么是0.75？

可以先考虑装载因子过大和过小分别会有什么问题

装载因子过大，表明哈希表填充率高，但是散列冲突的可能性大，查找元素的次数多

装载因子过小，表明哈希表的空闲空间大，空间利用率低，但冲突较少，查找元素次数少

0.75乘以2的幂是整数，不需要再做四舍五入，计算方便

根据HashMap注释

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost(reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

参考资料

resize()的大致过程

根据resize()方法的注释所言，resize()会将桶容量扩充两倍，由于容量是2的幂，原来桶中的元素位置要么是原封不动，要么是再移动2的幂个位置。

求元素的在table中的索引依然是 元素key的hashCode & (桶容量-1)

例如原来容量是16，二进制为10000，求元素索引时是 hashCode & 1111

扩容两倍后容量是32，二进制位100000，求元素索引的计算变成了 hashCode & 11111，比之前多了一个1，如果元素key的hashCode在该位也是1，等同于元素的索引位置增加了2的幂。

桶中是链表时，会将链表划分为两个链表，一个留在原桶，一个放入移动了2的幂的桶中。

为什么要这样调整？原封不动不行吗？

因为这样做是为了保证散列均匀，减少冲突。

参考资料：

为什么在解决hash冲突的时候，不直接用红黑树？而选择先用链表，再转红黑树？

因为节点数过少时，红黑树的插入、删除的成本比链表要高很多。

在散列均匀的情况下，冲突较少，每个桶中链表的平均长度比较短，性能可接受。

为什么链表的长度为8时变成红黑树？

根据jdk1.8的HashMap中的注释所言，假设散列分布均匀，在负载因子为0.75的条件下，某一个桶中元素出现的频率满足λ为0.5的泊松分布。从概率来看，之所以链表长度超过 8 以后要变成红黑树，因为在散列分布均匀的情况下出现这种情况的概率小到忽略不计，一旦出现，几乎可以认为是散列函数设计有问题导致的，即散列不均匀。

所以红黑树是专门应对元素key糟糕的（分布不均匀）的散列函数而准备的。

二项分布：n次重复独立伯努利试验，一次伯努利实验只有两种对立的结果。

泊松分布：当二项分布的n很大，p很小时，可以近似为泊松分布。

算法第四版465页：

散列均匀时，每个桶的链表的平均长度为 实际元素总数 / 哈希表大小，这个就是装载因子λ

现在的问题就是，将N个元素随机放入M个桶，每个桶的元素平均个数为λ（N/M），求每个桶元素个数为k的概率。

对于某一个桶而言，一个元素放入桶中是一个二元结果，要么放入，要么不放入，散列均匀的情况下，不管有多少个桶，每个元素出现在同一个桶的概率是相同，每个桶中平均有λ个元素时，那么一个元素出现在同一个桶的概率就是λ/N，就是桶元素数量占元素总数的比值，理解很直观。

参考资料：

为何红黑树节点数在小于等于6时又变成链表？为什么不是小于等于8时变回链表？

是为了防止频繁插入和删除元素时不停的在树和链表之间互相转换、降低性能，红黑树和链表之间的转换是有成本的。

MIN_TREEIFY_CAPACITY是做什么的？

桶中元素超过TREEIFY_THRESHOLD个（8个）后，还要保证哈希表数组table的大小大于等于MIN_TREEIFY_CAPACITY才会把链表转红黑树，容量过小时使用红黑树性价比不高，用扩容来解决桶元素堆积的问题更适合。

这个值为什么要是4 * TREEIFY_THRESHOLD，是为了避免在resize和树化之间产生冲突，比如初始容量是16，装载因子0.75，存储元素有16*0.75=12个时就应该扩容，但是此时如果是4个元素在一个桶，8个元素在另外一个桶，是要先树化的，树化后再等resize扩容了，可能又要将红黑树链表化，这样反复来回影响性能。

平衡二叉搜索树中为何选用红黑树？用AVL树会有什么问题？红黑树和AVL树有何区别？

单次的插入和删除操作：

单次插入数据，红黑树和AVL树平均都只需要几次旋转即可完成。

单次删除元素，红黑树大多数只需要几次旋转调整，AVL树需要调整查找路径上所有结点。

大量的插入和删除操作：

红黑树由于是基于2-3树，3结点的存在可以吸纳一部分不平衡性，不用做频繁的旋转调整。

AVL树需要始终保持平衡，在大量插入或删除元素后，AVL树的调整的次数多于红黑树。

在大量数据的统计意义上，红黑树的插入和删除次数相对于AVL树较少，适合插入和删除频繁的场景。

AVL树由于是高度平衡的，红黑树不是高度平衡，AVL树的查找次数比红黑树更少，适合对查询效率非常敏感，插入和删除不频繁的场景。

红黑树的查询跟AVL树仍然是同一个数量级，所以综合查询、插入、删除的性能，红黑树表现较好。

参考

put方法大致过程

  1. 获取key的hashCode()并扰动
  2. table数组为null则通过resize()初始化table，创建HashMap对象不会立刻初始化table数组
  3. 利用扰动后的hashCode除留取余求得元素在table中的索引
  4. 如果没有碰撞冲突，直接存入桶中
  5. 如果有碰撞冲突，桶中维护一个链表存储哈希值相同的元素，java7是头插法，java8是尾插法
  6. 链表长度超过TREEIFY_THRESHOLD，链表转为红黑树
  7. 如果元素已存在，替换value。元素存在先通过key的hashCode查看桶中是否有元素，没有则不存在，有元素需要依次遍历桶中元素，通过key的equals方法比较是否相等，有相等的则存在。
  8. 哈希表实际存储元素数量超过了阈值threshold（哈希表大小 * 装载因子），调用resize()扩容。

get方法的大致过程

  1. 获取key的hashCode()并扰动
  2. 根据哈希值求得table索引
  3. 若桶中第一个元素命中，直接返回
  4. 有冲突则依次遍历链表或红黑树，通过key的equals比较来寻找目标节点，找到了返回其value，没有找到返回null

HashMap为什么线程不安全？高并发下会产生什么问题？

一句话：jdk7的HashMap在扩容时会改变链表中元素原本的顺序，高并发情况下容易导致链表产生环，进而导致死循环，CPU占用率飙升到100%。

jdk7中扩容采用头插法是考虑到缓存的时间局部性原则，最近访问过的数据下次大概率会再次访问，把刚访问过的元素放在链表最前面可以直接被查询到，减少查找次数。

jdk8中扩容改为尾插法，高并发情况下不会产生死循环了，但是resize依然不是原子性的，可能会产生数据丢失。

其他方法例如链表和红黑树互转的过程，都不是原子性的，都可能会产生数据丢失的问题。

参考

Java 8 对HashMap做出了哪些改进？

  1. 桶中链表长度超过8将链表转为红黑树，以应对不均匀的散列函数导致的查询次数增多
  2. 链表插入元素由头插法改为尾插法，以解决并发下插入元素时链表产生环进而导致的死循环

modCount是做什么的？

对哈希表做出了修改（添加和删除元素），modCount就会增加，表示修改的次数，使用迭代器迭代哈希表时一旦发现modCount变化了，就会立刻抛出ConcurrentModificationException，以避免迭代时的不确定性，这称为fail-fast机制。注意修改一个已存在的元素的value不改变modCount。

HashMap的缺点是什么？想要用哈希表还有哪些选择？

缺点就是结构复杂，占用内存可能较多，对哈希表有简单需求的地方不需要这么复杂而完善的类

例如ThreadLocalMap就自己实现了一套简单的哈希表，采用开放定址法

还有Android上SparseArray、ArrayMap实现的内存消耗更低的哈希表

HashMap与Hashtable的区别？

  1. Hashtable的get、put、clear、contains、size等大部分方法上都加上了synchronized关键字，给整个对象上锁，HashMap非线程安全
  2. Hashtable中没有红黑树仅有链表
  3. Hashtable继承Dictionary类，HashMap实现Map接口
  4. Hashtable不允许null的key和value，而HashMap都允许
  5. Hashtable求key的hashCode没有扰动
  6. HashMap和Hashtable使用Iterator遍历元素过程中对哈希表添加或删除元素是会抛出异常的（fast-fail），但Hashtable用Enumeration迭代时不会fast-fail，因为通过Enumeration的nextElement()获取下一个元素时没有对modCount做判断，而Iterator的next方法对modCount做了判断。
  7. Hashtable是jdk1添加的，HashMap是jdk2添加的

Dictionary已被废弃，所以Hashtable已经被废弃，而且同步性能较差，大多数操作都会锁住整个对象。用jdk1.5引入的采用分段锁的ConcurrentHashMap同步性能更好。