面试之Java基础问题（2）

本文专门来讲一下跟HashMap有关的问题。
HashMap 和 HashTable的区别可以看这篇文章面试之Java基础问题（1）。

JDK1.7用的是头插法，而JDK1.8及之后使用的都是尾插法，在JDK1.8之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题；
JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
扩容后数据存储位置的计算方式也不一样
JDK1.8 之前 HashMap 底层是数组和链表结合在一起使用也就是链表散列。HashMap 通过 key 的 hashCode 经过hash运算处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。
TreeMap、TreeSet以及 JDK1.8 之后的 HashMap底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为二叉查找树在某些情况下会退化成一个线性结构。

HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry对象
使用Hashmap进行put操作可能会引起死循环，导致CPU利用率接近100%
HashMap 底层是一个 Entry 数组，当发生 hash 冲突的时候，HashMap 是采用链表的方式来解决的，在对应的数组位置存放链表的头结点。对链表而言，新加入的节点会从头结点加入
HashMap 是非线程安全的，同时我们知道 HashTable 是线程安全的，因为里面的方法使用了 synchronized 进行同步

接下来讲一讲HashMap的并发问题。

HashMap通常会用一个指针数组（假设为table[]）来做分散所有的key，当一个key被加入时，会通过Hash算法通过key算出这个数组的下标i，然后就把这个插到table[i]中，如果有两个不同的key被算在了同一个i，那么就叫冲突，又叫碰撞，这样会在table[i]上形成一个链表；
HashMap在并发环境下多线程put后可能导致get进入死循环，具体表现为CPU使用率100%；
多线程put可能导致元素丢失。

使用Hashtable 类，Hashtable 是线程安全的；
使用并发包下的java.util.concurrent.ConcurrentHashMap，ConcurrentHashMap实现了更高级的线程安全；
使用synchronizedMap()同步方法包装 HashMap object，得到线程安全的Map，并在此Map上进行操作。

以上的方法，如果在多线程并发情况下，推荐使用ConcurrentHashMap；Hashtable效率低，已经基本不使用了；synchronizedMap()也不推荐使用。

ConcurrentHashMap内部有一个Segment数组, 该Segment对象可以充当锁。Segment对象内部有一个HashEntry数组，于是每个Segment可以守护若干个桶(HashEntry),每个桶又有可能是一个HashEntry连接起来的链表，存储发生碰撞的元素。
ConcurrentHashMap就是通过设置Segment来实现分离锁。这样就对部分被使用的 Segment上锁，不需要全部上锁
在JDK8中，ConcurrentHashMap不再使用Segment分离(段)锁，而是采用一种乐观锁CAS算法来实现同步问题，但其底层还是“数组+链表->红黑树”的实现。
Java8不是用红黑树来管理HashMap，而是在hash值有很多相同的情况下（且重复数量大于8），用红黑树来管理数据，红黑树相当于排序数据，可以自动的使用二分法进行定位，性能较高。一般情况下，hash值做的比较好的话基本上用不到红黑树。

文章会持续更新，后续还会更新一些本人或者同学在实际秋招中遇到各个公司的笔试或面试题。请大家多多关注！！！谢谢大家！！！
若文中有不准确的地方，或者有其他任何问题，欢迎留言+评论。
上一篇文章：面试之Java基础问题（1）