复习：Map面试基础笔记

Map

1. 采用了 Key-value键值对映射的方式进行存储

1 key在Map里面是唯一的但是value可以重复一 个key对应一个value。
2 key是无序、唯一的
3 value是无序不唯一的

2. HashMap（重中之重）

• 查找 时间复杂度都要小，无限接近O(1)
• 是可以序列化的
• 是线程不安全的
• 底层主要是基于数组和链表实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储位置的。（这里本人之前也有过简单的HashMap简介可以了解下：HashMap简介）
• JDK1.7中结构
• 数组+ 链表
• JDK1.8中结构
  • 数组 +链表/红黑树
  • 进化的阈值 8 （链表转化为红黑树）
  • 退化的阈值 6（红黑树转化为链表）
• 初始化数组长度是多少 16
• 每次扩容都会扩容成2的n次方数值 当然也就是扩容两倍
• 扩容因子是0.75

1.HashMap的长度为什么必须是2的次幂？
为了实现一个尽量分布均匀的hash函数，利用的是Key值的HashCode来做某种运算。因此问题来了，如何进行计算，才能让这个hash函数尽量分布均匀呢？
首先想到的就是将Key值的HashCode值与HashMap的长度进行取模运算，即 index = HashCode(Key) % hashMap.length，但是，但是！这种取模方式运算固然简单，然而它的效率是很低的，浪费性能。所以jdk用了位运算的方式index = HashCode(Key) & (hashMap.length - 1);
举例：
“abc”十进制hashcode为96354，二进制为‭1 0111 1000 0110 0010‬，HashMap的默认长度为16，与15进的二进制1111位运算， 得到index = 2；
可以看出来，hash算法得到的index值完全取决与Key的HashCode的最后几位。这样做不但效果上等同于取模运算，而且大大提高了效率。
如果不是会怎样呢？
我们假设HaspMap的初始长度为10，要与9的二进制1001进行位运算。得到0，
但是 如果 hashCode为1 0111 1000 0110 1001 或者1 0111 1000 0110 1011这样会造成 有些索引出的值挤压太多。无法更好的分布均匀。

2.加载因子为什么是0.75？
加载因子过高，例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本；
加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash(重哈希)操作的次数。
在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash操作次数，所以，一般在使用HashMap时建议根据预估值设置初始容量，减少扩容操作。
选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择

3.处理冲突的几种方法
开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
再哈希法
链地址法
建立一个公共溢出区
hashmap出现了Hash冲突的时候采用第二种办法：链地址法。

4.equals()和hashCode()在HashMap中的重要性
使用HashMap，如果key是自定义的类，就必须重写hashcode()和equals()。

如果你重载了equals，比如说是基于对象的内容实现的，而保留hashCode的实现不变，那么很可能某两个对象明明是“相等”，而hashCode却不一样。
这样，当你用其中的一个作为键保存到hashMap中，再以“相等的”找另一个作为键值去查找他们的时候，则根本找不到。
对于每一个对象，通过其hashCode()方法可为其生成一个整形值（散列码），该整型值被处理后，将会作为数组下标，存放该对象所对应的Entry（存放该对象及其对应值）。
equals()方法则是在HashMap中插入值或查询时会使用到。当HashMap中插入值或查询值对应的散列码与数组中的散列码相等时，则会通过equals方法比较key值是否相等，
所以想以自建对象作为HashMap的key，必须重写该对象继承object的hashCode和equals方法。

• HashTable

  • 线程安全的
  • 对整个结构加锁 性能不好

• ConcurrentHashMap 线程安全的 Juc包下的

• 而ConcurrentHashMap在JDK1.7和1.8下也有很大的改变

• 下边我用图来解释下：

• 

• 

• 、
  底层数据结构：

  • JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
  • 实现线程安全的方式（重要）：
    • ① 在 JDK1.7 的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
    • 到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表/红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后 对 synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。