map
HashMap:
JDK1.7
HashMap 里面是一个数组(transient Node<K,V>[] table)，然后数组中每个元素是一个单向链表,由Node内部类实现；
数组的优点是：
数组是顺序存储结构，通过数组下标可以快速实现对数组元素的访问，效率极高；
数组的缺点是：
插入或删除元素效率较低，因为可能需要数组扩容、移动元素；
链表的优点是：
链表是一种链式存储结构，插入或删除元素不需要移动元素，只需要修改指向下一个节点的指针域，效率较高；
链表的缺点是：
链表访问元素需要从头到尾逐个遍历，效率较低；
JDK1.8 hashMap优化
1.数据存储结构,1.8中,如果链表长度超过了8,那么链表将转换为红黑树(平衡二叉树,TreeNode<K,V>),优化链表的查询速率,节点是根据hash值排序的
链表时的 复杂度为O(n),红黑树的时候O(log(n))
2.发生hash碰撞时,1.7会在链表的头部插入,而1.8会在链表的尾部插入
3.1.8中Entry被Node(实现Map.Entry接口)替代
4.hash的实现,1.8中,是通过hashCode的高16位异或低16位实现的
(h = k.hashCode()) ^ (h >>> 16)
主要是从性能,hash碰撞来考虑,减少系统的开销,也不会造成因为高位没有参与下表的计算,从而引起的碰撞(减少hash碰撞)
hash值的实现(JDK 1.8)
当key为null时,hash为0
其他key的hash为hashCode的高16位异或低16位,hash是32位
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
下标的计算方式
i = (n - 1) & hash;//n为数组长度
hashMap的扩容
hashMap初始容量16,扩容因子0.75,容量最大值2^30
如果当HashMap的容量超过12时,则进行扩容.
新建一个Node<K,V>[]数组,遍历原数组数据,赋值给新数组(需要重新计算每个元素的下标)
新hashMap容量为原Map的2倍
HashMap的put操作源码分析
1、调用哈希函数获取Key对应的hash值，再计算其数组下标；
2、如果没有出现哈希冲突，则直接放入数组，如果出现哈希冲突，则以链表的方式放在链表后面；
3、如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树；
4、如果结点的key已经存在，则替换其value即可；
5、如果集合中的键值对大于12，调用resize方法进行数组扩容
HashMap的get操作源码分析
1、根据key的hash值计算数组的下标；
2、根据计算得到的数组下标访问数组元素，如果数组元素为null，则返回空；
3、根据计算得到的数组下标访问数组元素，如果数组元素不为null，则遍历该数组元素单向链表的每个节点，如果某个节点的key与当前key相等，则把该节点的值返回；
4、根据计算得到的数组下标访问数组元素，如果数组元素不为null，则遍历该数组元素单向链表的每个节点，如果某个节点的key与当前key都不相等，则返回null；
5.判断元素是否为要查询的元素条件为
first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))
即hash值一致,key值一致
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
HashMap的常见面试
1、HashMap 的数据结构？
哈希表结构（数组+链表）实现，结合数组和链表的优点，当链表长度超过8时，链表转换为红黑树；
2、HashMap的hash运算如何实现的？为什么这样实现？
HashMap为什么不直接使用对象的原始hash值？它的实现代码如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
JDK 1.8 中，是通过 hashCode() 的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从性能，hash碰撞来考虑的，减少系统的开销，也不会造成因为高位没有参与下标的计算，从而引起的碰撞；
使用异或操作，一个是提高性能，一个减少hash碰撞；
通过移位和异或运算，可以让 hash 变得更复杂，进而影响 hash 的分布性；
3、HashMap的容量是多少？加载因子是什么？容量如何变化？容量不够怎么办？
数组大小是由 capacity 这个参数确定的，默认是16，也可以构造时传入，最大限制是1<<30；
loadFactor 是装载因子，主要目的是用来确认table 数组是否需要动态扩展，默认值是0.75，比如table 数组大小为 16，装载因子为 0.75 时，threshold 就是12，当 table 的实际大小超过 12 时，table就需要动态扩容；
扩容时，调用 resize() 方法，将 table 长度变为原来的两倍；
扩容时创建一个新的数组，其容量为旧数组的两倍，并重新计算旧数组中结点的存储位置；
如果数据量很大的情况下，扩容时将会带来性能的损失，在性能要求很高的地方，这种操作性能很低；
4、什么是hash碰撞，发生hash碰撞怎么办？
如果两个键计算出来的数组下标一样，那么就产生了hash碰撞，hash碰撞的解决办法有
- 开放地址法
- 再哈希法
- 链地址法（拉链法） -->hashmap采用是该办法
- 建立一个公共溢出区，
HashMap采用的是3.链地址法（拉链法），当发生冲突时，将新结点添加在链表后面；
5、HashMap 和 HashTable 有什么区别？
HashMap 是线程不安全的，HashTable 是线程安全的；
由于线程安全，所以 HashTable 的效率比不上 HashMap；
HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 HashTable不允许；
HashMap 默认初始化数组的大小为16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1；
HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode；
6、HashMap 与 ConcurrentHashMap 的区别？
除了加锁之外，原理上无太大区别，ConcurrentHashMap 类（是 Java并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现）。
ConcurrentHashMap，在 JDK 1.7 中采用分段锁的方式，JDK 1.8 中直接采用了CAS + synchronized，另外HashMap 的键值对允许有null，但是ConCurrentHashMap 都不允许。
7、我们能否让HashMap实现同步（线程安全）？
当然可以，使用Map map = Collections.synchronizeMap(hashMap);
