1.关于map
首先，map是用来存储键值对（以前我一直有一个认知误区，数组里存的是key,然后value挂在key后面，形成链表），所以map的基本单位是Entity,那么Entity是从哪儿来的呢？
interface Entry<K,V>
这是map的内部接口，也就是说我们用的put(key,value)会被内部封装成一个Entity存储。，至于为什么不能有重复的key是因为hashcode()算法。下面是map的常见实现类：
linkedHashMap:记录了插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯 定是先插入的，也可以在构造时带参数，按照访问次序排序。
TreeMap:TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。
HashMap:它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
上面这些话是从别的地方引用的，相信大多数人和我一样：看不懂，记不住，不过没关系，我把他们的特点总结了：
- Treemap有序，hashmap快
- hashmap线程不安全，hashtable线程安全（不过它太low了，下面我会解释）
- hashmap的键，值都可以为null
上面三句话只要谈到map基本是必问的，答不出来基本上就可以凉凉了
2.关于Hashmap
hashmap的考察点很多，但是基本绕不开3个点，插入，扩容，线程安全，
3.hashmap的插入你知道嘛？
我看过很多讲解，这是从美团的技术博客中拿下来的一张图，可以说非常完美的解释了hashmap的存储，结合源码，来一步一步看(调用put方法其实就是调用putVal(),这个方法可以说是HashMap存储的精髓)：
/**
* Implements Map.put and related methods.
*
* @param hash key的hash值
* @param key key的真实值
* @param value value的真实值
* @param onlyIfAbsent 如果为true,就不修改已经存在的value(默认为false)
* @param evict 如果是false,就创建table（默认传true）
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//1.tab为空则创建(也就是说在第一次调用put()的时候它才创建table)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果不是那么就在table[i]后面挂的链表中找
else {
Node<K,V> e; K k;
//3.如果key存在，那么直接覆盖value(在table中判断)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 4.判断该节点是链表还是红黑树
else if (p instanceof TreeNode)
//如果是红黑树是就调用putTreeVal()
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 5.如果是链表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已经存在直接覆盖value（在链表中判断）
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)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 6.超过最大容量 就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
总结：
hashmap的存主要分为6步：
- 判断table是否为null
- 根据key的hash值看table中是否存在相同的hash值，如果有就在链表里找，如果没有就新建一个节点在table里
- 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，如果不一样就遍历链表，遍历完链表以后执行插入逻辑（jdk1.7以前使用头插，jdk1.8使用尾插）
- 判断该节点是红黑树还是链表，如果是红黑树跳转至putTreeVal()处理，否则，按链表处理
- 遍历链表并记录链表长度，如果链表长度大于8,就树化。
- 查看存在的键值对是否数量过多，如果过多就扩容
4.你了解hashmap的扩容机制嘛？
扩容这个过程，我看网上很少有讲扩容源码的，大部分是讲扩容的方法，这里总结一下扩容的方法：
一个关于扩容的小故事：
那时候我还在学C语言，给我讲哈希的陈老师问我们：“hash有一个致命的缺点就是hash冲突，如果hash冲突过多了怎么办？”
“扩容”
”那么扩容怎么扩？“
“......”
"把所有的数据拿出来，重新hash一遍"
“怎么会有这么煞笔的算法”
这段简短的对话在后期解决了我的很多疑惑。
hash扩容的关键就是“怎么扩”和“什么时候扩”
-
关于“怎么扩“
把hash的数据全部拿出来，重新hash一遍。
但是这个前提下我们可以优化整个过程，这里非常敬佩写hashmap的大神，真的牛批，难怪都爱考1.8的hashmap，这个hashmap的写法是真的是相当的优秀，简直让人......(此处略却10000字赞叹只留下一句“卧槽”)，跪舔结束，来看下真正的王者编码
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
-
什么时候扩？
hashmap扩容是因为hash冲突过高，而hash冲突过高在HashMap中有一个默认的负载因子（0.75），当数组的大小占到了总大小的0.75就会触发扩容机制。在jdk1.8以后规定了hashmap的扩容大小为每次扩到一倍,也就是*2(具体为什么要扩大两倍，是因为一个非常巧妙地扩容算法，这里不多)。（这里的两次循环可以证明，扩容机制是把所有的Entry都拿了出来重新的放了一遍）
总结：
在jdk1.7以前，hashmap的建造方式是：Entity+数组+链表，jdk1.8建造方式：Node+数组+红黑树
一个小问题：
为什么要用红黑树来替代链表？
首先如果链表的长度超过8了，就会被树化。选用红黑树是因为分析一下它的竞争对手
- 二叉搜索树，存在最坏情况，导致搜索效率变低
- AVL树，需要满足左右高度条件，使得插入麻烦
- 中庸选择红黑树，红黑树是低配的AVL树
5.hashmap是线程安全的嘛？如果想要线程安全的hashmap怎么办？
hashmap是线程不安全的类，如果想要线程安全的可以使用hashtable,但是hashtable的key和value是不能为null的,还可以使用Collections工具类制造一个synchronizedHashMap接口，或者使用ConcurrentHashMap来获得一个线程安全的hashmap。hashmap线程不安全主要因为：在插入的时候，如果不加锁，两个线程同时进行扩容的时候会形成一个环形链表，造成死锁，所以如果想要线程安全加锁的话，就加在put方法上就好了。
6.concurrentHashMap了解过嘛？
了解过，concurrentHashMap是线程安全的HashMap类，在jdk1.7以前它采用的是：segment分段锁来保证线程安全的，在jdk1.8以后它采用CAS算法来保证线程安全(下一章讲“线程锁”会提到)。这里主要讲segment，segment的源码如下
static class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
final float loadFactor;
Segment(float lf) { this.loadFactor = lf; }
}
首先segment是ReentratLock的实现类（下一章会讲ReentratLock）。这里主要讲一个过程：
- 先算出插入数据的hash值
- 根据此hash值计算出线程要拿的segment锁
- 拿到锁以后对锁内的数据进行操作，用完释放锁
总结
线程安全实在是太重要了，所以下一节细讲。其实考察的点也就三个：存储结构，插入方式，线程安全，其中主要的变化是jdk1.7到jdk1.8的变化：
jdk1.7:数组+链表+segment
jdk1.8:数组+链表+红黑树+CAS
