Java Map相关题

Map

哈希表 HashMap 和 HashTable

HashMap夺命14问，你能坚持到第几问

HashMap 和 HashTable 区别

HashMap 如何计算数组下标？

https://blog.csdn.net/duihsa156165/article/details/106860412

ArrayMap、SparseMap 和 HashMap

HashMap(空间换时间)

1. HashMap 占用空间大，每次存数据都需要存个 Entry
2. HashMap 在存储数据时将要不断地扩容，且不断地做 hash 运算，对内存空间造成很大消耗和浪费

ArrayMap(时间换空间)

1. 基于两个数组实现，一个存放 hash:mHashes，一个存放 key/value 键值对:m<Array

mHashes[index] = hash mArray[index<<1]=key mArray[(index<<1)+1]=value

1. 存放 hash 的数组是有序的 (升序?)，查找时使用二分查找
2. 插入数据时，根据 key 的 hashCode() 得到 hash 值，计算在 mArray 的 index 位置，然后利用二分查找找到对应的位置进行插入，当出现哈希冲突时，会在 index 的相邻位置插入
3. 扩容时不像 HashMap 直接 double，也不需要重建哈希表，只需要调用 System.arraycopy 进行数组拷贝
4. 适合数据类 1000 内，数据量大的时候二分查找比红黑树会慢很多
5. ArrayMap 的小数组复用池

Android 用的 Map 都很小，所以就把 4 和 8 大小的数组缓存起来，以备使用，减少 GC

SparseArray(时间换空间)

1. SparseArray ⽐ HashMap 更省内存，在某些条件下性能更好，主要是因为它避免了对 key 的⾃动装箱（int 转为 Integer 类型），它内部则是通过两个数组来进⾏数据存储的，⼀个存储 key，另外⼀个存储 value，为了优化性能，它内部对数据还采取了压缩的⽅式，从⽽节约内存空间，我们从源码中可以看到 key 和 value 分别是⽤数组表示：
   private int[] mKeys;
   private Object[] mValues;
2. SparseArray 存储和读取数据，使用的是二分查找法；SparseArray 是按 key 从小到大排序的，可以用二分查找元素位置，获取速度非常快，比 HashMap 快很多

如何抉择

1. 数据类 1000 以内且增删不频繁的情况
   1. 如果 key 的类型确定为 int 类型，用 SparseArray，避免自动装箱过程；key 为 long 类型用 LongSparseArray
   2. 如果 key 为其他类型，用 ArrayMap，基本类型 ArrayMap 存在自动装箱
2. 数据类 1000 以上或增删频繁用 HashMap
   

谈谈 LinkedHashMap 和 HashMap 的区别？

ConcurrentHashMap

见 并发工具类→ ConcurrentHashMap面试题

HashMap 面试题

HashMap 是线程安全的吗？如何实现线程安全的 HashMap？

HashMap 不是线程安全的。
为什么 HashMap 是线程不安全的？

1. put() 方法不是同步的
2. resize() 方法也不是同步的，扩容过程，会重新生成一个新的容量的数组，然后对原数组的所有键值对重新进行计算和写入到新的数组，之后指向新生成的数组

如何线程安全的使用 HashMap？

1. HashTable

方法级别的 synchronized

1. Collections.synchronizedMap(Map)

底层用的是 Collections 内部的 SynchronizedMap 类，它是对传入的 Map 的一个包装，synchronized 代码块的方式

1. ConcurrentHashMap

JDK7 采用的是 Segment 分段锁实现的，而 JDK8 采用的是 CAS 算法实现的。

HashMap 中的 Hash 冲突解决和扩容机制（扩容机制常考）

冲突解决：链地址法，出现了 hash 冲突用链表链起来（JDK8.0 出现了红黑树）

扩容机制：到 size 大于等于 threshold 时，扩容为原有的 2 倍大小

为什么 HashMap 的 remove 和 clear 没有缩容的操作？

缩容的意义在哪呢，如果这个 map 很快就释放了。那何必多此一举。如果 map 还继续用很可能还会有同样的数据量。也没必要在多此二举（还得扩回来）。而且这东西线程本就不安全。操作还是简单点好。提高 remove 复杂度是得不偿失的