【Android面试】2023最新面试专题一：HashMap篇

1、 请说一说HashMap，SparseArrary原理，SparseArrary相比HashMap的优点、ConcurrentHashMap如何实现线程安全？

这道题想考察什么？

1、HashMap，SparseArrary基础原理？

2、SparseArrary相比HashMap的优点是什么？

3、ConcurrentHashMap如何实现线程安全？

考察的知识点

HashMap，SparseArrary、ConcurrentHashMap

考生如何回答

HashMap和SparseArray，都是用来存储Key-value类型的数据。

SparseArray和HashMap的区别：

双数组、删除O(1)、二分查找

• 数据结构方面：hashmap用的是链表。sparsearray用的是双数组。
• 性能方面：hashmap是默认16个长度，会自动装箱。如果key是int 的话，hashmap要先封装成Interger。sparseArray的话就就会直接转成int。所以spaseArray用的限制是key是int。数据量小于1k。如果key不是int小于1000的话。可以用Arraymap。

HashMap的基本原理

HashMap内部是使用一个默认容量为16的数组来存储数据的，而数组中每一个元素却又是一个链表的头结点，所以，更准确的来说，HashMap内部存储结构是使用哈希表的拉链结构（数组+链表）。

4.png

HashMap中默认的存储大小就是一个容量为16的数组，所以当我们创建出一个HashMap对象时，即使里面没有任何元素，也要分别一块内存空间给它，而且，我们再不断的向HashMap里put数据时，当达到一定的容量限制时，HashMap就会自动扩容。

SparseArray的基本原理

SparseArray比HashMap更省内存，在某些条件下性能更好，主要是因为它避免了对key的自动装箱（int转为Integer类型），它内部则是通过两个数组来进行数据存储的，一个存储key，另外一个存储value，为了优化性能，它内部对数据还采取了压缩的方式来表示稀疏数组的数据，从而节约内存空间，我们从源码中可以看到key和value分别是用数组表示：

private int[] mKeys;
private Object[] mValues;

我们可以看到，SparseArray只能存储key为int类型的数据，同时，SparseArray在存储和读取数据时候，使用的是二分查找法，

public void put(int key, E value) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        ...
        }
 public E get(int key, E valueIfKeyNotFound) {
        int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
        ...
        }

也就是在put添加数据的时候，会使用二分查找法和之前的key比较当前我们添加的元素的key的大小，然后按照从小到大的顺序排列好，所以，SparseArray存储的元素都是按元素的key值从小到大排列好的。而在获取数据的时候，也是使用二分查找法判断元素的位置，所以，在获取数据的时候非常快，比HashMap快的多，因为HashMap获取数据是通过遍历Entry[]数组来得到对应的元素。

添加数据

public void put(int key, E value)

删除数据

public void remove(int key)

获取数据

public E get(int key)
  
public E get(int key, E valueIfKeyNotFound)

虽说SparseArray性能比较好，但是由于其添加、查找、删除数据都需要先进行一次二分查找，所以在数据量大的情况下性能并不明显，将降低至少50%。满足下面两个条件我们可以使用SparseArray代替HashMap：

• 数据量不大，最好在千级以内
• key必须为int类型，这中情况下的HashMap可以用SparseArray代替：

ConcurrentHashMap基本原理

• JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry。

• JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了。

• JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表。

3.png

2 、请说一说HashMap原理，存取过程，为什么用红黑树，红黑树与完全二叉树对比，HashTab、concurrentHashMap，concurrent包里有啥?

这道题想考察什么？

1、HashMap，HashTab基础原理？

2、ConcurrentHashMap相比HashMap的优点是什么？

3、Concurrent包里面有什么样的的函数？

考察的知识点

HashMap，HashTab、ConcurrentHashMap

考生如何回答

HashMap的原理

HashMap内部是使用一个默认容量为16的数组来存储数据的，而数组中每一个元素却又是一个链表的头结点，所以，更准确的来说，HashMap内部存储结构是使用哈希表的拉链结构（数组+链表）。

1.png

HashMap中默认的存储大小就是一个容量为16的数组，所以当我们创建出一个HashMap对象时，即使里面没有任何元素，也要分别一块内存空间给它，而且，我们再不断的向HashMap里put数据时，当达到一定的容量限制时，HashMap就会自动扩容。

HashTab的原理

哈希表（Hash table，也叫散列表）， 是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希表hash table(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

在使用的时候，有以下几种方式：

• Hashtable 是一个散列表，它存储的内容是键值对(key-value)映射。
• Hashtable 继承于Dictionary，实现了Map、Cloneable、java.io.Serializable接口。
• Hashtable 的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。

HashMap为什么要用红黑树？红黑树相对完全二叉树有有什么优点？

我们来看看红黑树的主要特性:

• 每个节点都带有颜色属性（颜色为红或黑）的平衡二叉查找树。
• 节点是红色或黑色。
• 根节点是黑色。
• 所有叶子结点都是黑色。
• 每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
• 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

2.png

红黑树是平衡二叉树的一种，插入时遵循二叉树“左右”定律，

该父节点的左子节点：为小于父节点中且子树中最接近父节点值得数。

该父节点的右子节点：为大于父节点中且子树中最接近父节点值得数。

Concurrent包里面有什么

ConcorrenctHashMap：将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成，Segment是一种可重入锁ReentrantLock。

CopyOnWriteArrayList：CopyOnWrite并发容器用于读多写少的并发场景，线程安全的写时复制。

ReentrantLock：效果和synchronized一样，都可以同步执行，lock方法获得锁，unlock方法释放锁。ReetrantLockqubie添加了类似锁投票、定时锁等候和可中断锁等候的一些特性争用下的 ReentrantLock 实现更具可伸缩性。ReentrantLock支持公平锁，同一个线程可以多次获取同一把锁。ReentrantLock和synchronized都是可重入锁。

CountDownLatch：CountDownLatch类位于java.util.concurrent包下，利用它可以实现类似计数器的功能。比如有一个任务A，它要等待其他4个任务执行完毕之后才能执行，此时就可以利用CountDownLatch来实现这种功能了。

Semaphore：它负责协调各个线程, 以保证它们能够正确、合理的使用公共资源。Semaphore可以控制某个资源可被同时访问的个数，通过 acquire() 获取一个许可，如果没有就等待，而 release() 释放一个许可实现对资源的保护。

Future：Callable接口可以看作是Runnable接口的补充，call方法带有返回值，并且可以抛出异常。runnable接口实现的没有返回值的并发编程。

CyclicBarrier：这个类是一个同步工具类，它允许一组线程在到达某个栅栏点(common barrier point)互相等待，发生阻塞，直到最后一个线程到达栅栏点，栅栏才会打开，处于阻塞状态的线程恢复继续执行。它非常适用于一组线程之间必需经常互相等待的情况。

3、 请说一说HashMap put()底层原理,发生冲突时，如何去添加(顺着链表去遍历，挨个比较key值是否一致，如果一致，就覆盖替换，不一致遍历结束后，插入该位置) ？

这道题想考察什么？

1、Hashmap的put函数基础原理？

考察的知识点

HashMap底层的源码

考生如何回答

HashMap put函数的底层源码解析

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0) //首次放入元素时,分配table空间-默认size=16
            n = (tab = resize()).length;
 
        if ((p = tab[i = (n - 1) & hash]) == null) // 算出新node在table中的位置，若对应位置为null,新建一个node并放入对应位置.
        // 注意:  (n - 1) & hash 求余操作 等价于 hash%n 
            tab[i] = newNode(hash, key, value, null);
        else {                                      //在table对应位置有node时
            Node<K,V> e; K k;
            if (p.hash == hash &&                   // key一样 (hash值相同，且key 一样，相同实例或者满足Object.equals方法)
                ((k = p.key) == key || (key != null && key.equals(k)))) // 不满足此条件则发生hash碰撞
                e = p;
            else if (p instanceof TreeNode)                // hash碰撞的情况下,用链表解决,链表大于8时，改为红黑树. 当node为treeNode时,putTreeVal->红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {                                                                               //hash
                for (int binCount = 0; ; ++binCount) {                          //用for循环将链表指针后移，将新node在链表加在尾部
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // 当链表长度大于8时，转成红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&                                               
                        ((k = e.key) == key || (key != null && key.equals(k))))         
                        break;                                                          
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)  //当node中旧的值null或者onlyIfAbsent==false时,将新的value替换原来的value.
                    e.value = value;
                afterNodeAccess(e); //新node塞入table后做的做的事情，在HashMap中是一个空方法（LinkedHashMap中有有使用， move node to last）
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)  //新的size大于阈值(默认0.75*table.length)时,扩容.
            resize();
        afterNodeInsertion(evict);
        return null;
    }

思路如下：

• 对key的hashCode()进行hash后计算数组下标index;
• 如果当前数组table为null，进行resize()初始化；
• 如果没碰撞直接放到对应下标的bucket里；
• 如果碰撞了，且节点已经存在，就替换掉 value；
• 如果碰撞后发现为树结构，挂载到树上。
• 如果碰撞后为链表，添加到链表尾，并判断链表如果过长(大于等于TREEIFY_THRESHOLD，默认8)，就把链表转换成树结构；
• 数据put后,如果数据量超过threshold，就要resize。

通过上面的思路我们可以看到，HashMap的put函数在添加的时候会判断碰撞后是否为链表，如果是链表就添加到链表尾，并判断链表如果过长(大于等于TREEIFY_THRESHOLD，默认8)，就把链表转换成树结构。

文末

更多面经和进阶详解可看我的个人简介