一、HashMap的数据结构
java编程语言中，最基本的数据结构就两种。一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体。IDK1.8里面对HaspMap做了一个更新，采用了数组+链表+红黑树，为什么要做更新呢？因为数组加链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布，当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题,当桶中的元素元素大于八个时就会转化为红黑树。图中的红色小圆点即代表一个key-value。
HashMap的工作原理
HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。
当两个不同的键对象的hashcode相同时会发生什么？ 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。
因为HashMap的好处非常多，我曾经在电子商务的应用中使用HashMap作为缓存。因为金融领域非常多的运用Java，也出于性能的考虑，我们会经常用到HashMap和ConcurrentHashMap。
HashMap源代码
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; #aka 16,初始容量为16
static final int MAXIMUM_CAPACITY = 1 << 30; #最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; # 扩容因子
The bin count threshold for using a tree rather than list for a bin.
static final int TREEIFY_THRESHOLD = 8;
HashMap结构图
新增的红黑树代码如下
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
红黑树这块，JDK1.8更新了一个重要的操作----桶的树形化treeifyBin()
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
二、HashMap的get操作
HashMap的hashcode的作用
hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，
hashCode是用来在散列存储结构中确定对象的存储地址的。
如果两个对象相同，就是适用于equals(java.lang.Object) 方法，那么这两个对象的hashCode一定要相同。
两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object) 方法，
只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里”。
例如内存中有这样的位置
0 1 2 3 4 5 6 7
而我有个类，这个类有个字段叫ID，我要把这个类存放在以上8个位置之一，如果不用HashCode而任意存放，
那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。
但以上问题如果用HashCode就会使效率提高很多
定义我们的HashCode为ID％8，比如我们的ID为9，9除8的余数为1，那么我们就把该类存在1这个位置，
如果ID是13，求得的余数是5，那么我们就把该类放在5这个位置。依此类推。
但是如果两个类有相同的HashCode，例如9除以8和17除以8的余数都是1，
也就是说，我们先通过HashCode来判断两个类是否存放某个桶里，但这个桶里可能有很多类，
那么我们就需要再通过equals在这个桶里找到我们要的类。
equals相等，hashcode必相等；hashcode相等，equals可能不相等。
Q:为什么需要hashCode?
1、通过hashCode可以很快的查到小内存块。
2、通过hashCode比较比equal方法快，当get时先比较hashCode，如果hashCode不同，直接返回false。
Q:HashMap和HashTable的区别
Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现，它们都是集合中将数据无序存放的。
1、hashMap去掉了HashTable的contains方法，但是加上了containsValue()和containsKey()方法，HashTable Synchronize同步的，线程安全，HashTable不允许空键值为空，效率低。
HashMap 非Synchronize线程同步的，线程不安全，HashMap允许空键值为空，效率高。
查看Hashtable的源代码就可以发现，除构造函数外，Hashtable的所有 public 方法声明中都有 synchronized 关键字，而HashMap的源代码中则连 synchronized 的影子都没有
2、Hashtable不允许 null 值(key 和 value 都不可以)，HashMap允许 null 值(key和value都可以)。
3、两者的遍历方式大同小异，Hashtable仅仅比HashMap多一个elements方法。
Hashtable table = new Hashtable();
table.put("key", "value");
Enumeration em = table.elements();
while (em.hasMoreElements()) {
String obj = (String) em.nextElement();
System.out.println(obj);
}
4、HashTable使用Enumeration，HashMap使用Iterator
Q:HashMap与LinkedHashMap,和TreeMap的区别。
共同点：
HashMap,LinkedHashMap,TreeMap都属于Map的实现类.
不同点:
1.HashMap不保证顺序，即为无序的，具有很快的访问速度，HashMap最多只允许一条记录的键为Null，允许多条记录的值为 Null。
2.TreeMap实现SortMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。
3.LinkedHashMap 是HashMap的一个子类，LinkedHashMap可以保证HashMap集合有序，存入的顺序和取出的顺序一致,如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现。
如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。
如果需要输出的顺序和输入的相同,那么用LinkedHashMap 可以实现,它还可以按读取顺序来排列。
Q:HashMap和ConcurrentHashMap的区别
1、HashMap不是线程安全的，而ConcurrentHashMap是线程安全的。
2、ConcurrentHashMap采用锁分段技术，将整个Hash桶进行了分段segment，也就是将这个大的数组分成了几个小的片段segment，而且每个小的片段segment上面都有锁存在，那么在插入元素的时候就需要先找到应该插入到哪一个片段segment，然后再在这个片段上面进行插入，而且这里还需要获取segment锁。
3、ConcurrentHashMap让锁的粒度更精细一些，并发性能更好。
Q:get原理
通过hash获得对应数组位置，遍历该数组所在链表（key.equals（））
Q:hashcode相同，冲突怎么办？
“头插法”，放到对应的链表的头部。
为什么是头插法（其设计原理是什么）？
因为HashMap的发明者认为，后插入的Entry被查找的可能性更大（因为get查询的时候会遍历整个链表）。
Q:JDK1.7的hashmap和JDK1.8的hashmap的区别（即1.8做了哪些优化）？
为了加快查询效率，java8的hashmap引入了红黑树结构，当数组长度大于默认阈值64时，且当某一链表的元素>8时，该链表就会转成红黑树结构，查询效率更高。（问题来了，什么是红黑树？什么是B+树？（mysql索引有B+树索引）什么是B树？什么是二叉查找树？）
这里只简单的介绍一下：红黑树是一种自平衡二叉树，拥有优秀的查询和插入/删除性能，广泛应用于关联数组。
