HashMap的基础回顾：
- HashMap实现于Map接口
- HashMap采用key-value方式进行数据存储
- HashMap存储的数据没有顺序性
- HashMap是线程不安全的
- JDK1.7版本中，HashMap底层是“数组+链表”，通过建立pos=key%size这样的关系去为hashMap插入存储；pos求余就是数组下标。1.8多加了红黑树
- HashMap里边的数组初值是16个空间。数组里存放的就是链表的引用地址。
- 数组中某个位置上关联的链表存储的数据个数大于等于8时，HashMap就把链表改变为红黑树，要是桶中的值数又由多变少，至到为6个，那就又变回链表。static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6; - 对象也可以作为hashMap的键，任何类都可以，主要它覆盖了hashCode()和equals()方法，hashCode方法用于向HashMap中插入键，而equals()方法用于从HashMap中检错值。
- HashMap中只允许一个空键。如果HashMap的键是空的，那么它将始终存在于索引0中。如果试图在空键上调用hashCode()方法，则会抛出NullPointerException。
各种前菜：
HashMap的迭代用法
使用keySet()和iterator()
Set<String> keySet = map.keySet();
Iterator<String> keySetIterator = keySet.iterator();
while(keySetIterator.hasNext()) {
String key = keySetIterator.next();
System.out.println("key: " + key + " value: " + map.get(key));
}
使用entrySet()和增强的for循环
for (String key : map.keySet()) {
System.out.println("key: " + key + " value: " + map.get(key));
}
使用entrySet()和iterator()
Set<Map.Entry<String, Object>> entrySet2 = map.entrySet();
Iterator<Map.Entry<String, Object>> entryIterator = entrySet2.iterator();
while (entryIterator.hasNext()) {
Map.Entry<String, Object> entry = entryIterator.next();
System.out.println("key: " + entry.getKey() + " value: " + map.get(entry.getKey()));
}
使用keySet()和get()方法
Set<Map.Entry<String, Object>> entrySet = map.entrySet();
for (Map.Entry entry: entrySet) {
System.out.println("key: " + entry.getKey() + " value: " + map.get(entry.getKey()));
}
HashMap和HashTable的区别？
- 最大区别就是HashMap能够容纳key为null或者value为null的，但是HashTable不可以。
- HashTable是同步的，HashMap不是同步的，也就意味着其线程不安全
- HashMap会比HashTable更快，因为HashMap不是同步的。
HashMap和ArrayList的区别？
- 实现:Java中HashMap实现Map接口，ArrayList实现List接口
- 存储对象:HashMap存储key和value两个对象，ArrayList只存储一个对象。
- 排序:HashMap不提供排序保证，而ArrayList维护插入它们的对象的顺序。
- 重复:HashMap不允许重复键，尽管它允许重复值，而ArrayList允许重复。
- Equals和Hashcode方法:HashMap和ArrayList之间的第五个区别是，HashMap的键必须实现Equals()和Hashcode()方法，而ArrayList则不必实现这些方法。
- get()方法性能:HashMap和ArrayList的第六个区别是，HashMap get(key)方法的性能在最好的情况下是O(1)，在最坏的情况下是O(n)，而ArrayList get(index)方法的性能总是O(1)。
各种领悟+源码：
HashMap中的数组是在何时进行初始化的？
虽然HashMap有四种构造方法，但是里面并没有定义数组初始化的代码。实际是在put方法里才会初始化数组。生当第一次调用put时，他首先会判断底层数组是否被初始化，如果没有初始化，则先进行初始化：
//构造方法里的赋值操作，没有看到定义数组的代码
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; //赋值操作
}
//put方法里的初始化数组部分
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
我们的HashMap的工作原理？
1.HashMap是基于hash算法产生一个集合工具类。
2.HashMap采用key-value键值对方式进行数据存储。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
3.当通过HashMap中put方法存入键值对时，首先通过hash函数（由Object类继承而来）计算key关联的hashcode值。通过hashcode值确定数据bucket中位置（A bucket is used to store key value pairs .bucket就是存储许多键值对的）。在确认位置之后将key-value封装的Entry对象存储到此bucket中（或者出现覆盖操作）。
tab[i] = newNode(hash, key, value, null);
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
afterNodeAccess(e);
4.当通过hashMap的get(key k)方法读取值时，首先通过hashCode方法将key转换成hashcode，然后在bucket上找到对应位置上的Entry对象读取并输出Entry对象里放的value值，否则返回null。
return (e = getNode(hash(key), key)) == null ? null : e.value;
//?first node 不是的话就循环找了
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
hash碰撞以及解决方案？
hash碰撞就是我和你都需要在这个bucket里存着。使用put方法来保存数据时，将数据中的KEY转换为hash值，再根据hash值定位数组存放位置，若当前数组的位置上已经存在链表并且新数据key与链表上节点的key不同，此时遍历链表节点，找到相同的覆盖，不同的则将新数据作为最后一个节点存储在链表的最后一个位置。
hash碰撞存在的问题就是链表可能会很长。数据量大可能还要等待，因为要不断去遍历会导致存放速度就会变慢。解决方案呢就是开放地址方案和链表算法方案。
开放地址方案（Open Addressing）确保数组存放就是key-value，而不是键值对（散列表）。也就是改变之前那种“二维”的感觉，这就是一维的。如果要存入数据key对应的hash值在数组中位置上已经存在了数据，则通过数学算法对key进行新的运算得到新的hash值，就是新的数组位置，将新数组存入到数组新位置。不同的 key 会生成不一样的探测序列，也可以想象成是一种虚拟链条。
root = hash(key) % m // 第一个位置，m 为数组的长度
index_i = (root + p(key, i)) % m // 链条中的第 i 个位置
index_1 = (root + p(key, 1)) % m
index_2 = (root + p(key, 2)) % m
...
链表算法方案就是取单向链表代替散列表。当存入数据的key与链表第一个数据key不同相同时，向第一个数据next指针指向新数据。将数据next指针指向第二个数据位置，这个比较好理解，就是纯纯的链表，数据元素的逻辑顺序通过链表中的指针链接次序实现的。
get()时，要是两个不同key计算的hashcode相等时怎么办？怎么辨别我要取的是哪个value？
equals()方法来救场！虽然我们都对应着一个bucket，但是不要忘记了bucket是一个链表。而且它不是java.util.LinkedList中的那个LinkedList——它是一个单独的实现，仅用于映射的表。所以我们去遍历链表，使用keys.equals()方法比较存储好的键值，直到遇到相等的，也就是返回true了，那么这时候再返回相应的value值就好啦~
这个现象也叫做碰撞效应：如果两个对象拥有相等的hashcode。此时在bucket上存储位置一定是相同的，此时hashMap采用链表形式存储两个对象，就好比说在第一个Entry对象后放一个指针。
两个对象的hashCode相等时，她们的key未必相等，但是要是都相等，那就overrides吧~如果您试图存储HashMap中已经存在的键，那么它将用新值覆盖旧值，HashMap的大小也不变。这就是为什么当你在HashMap上调用keySet()方法来获取所有键时，它将返回Set而不是Collection，因为Set不允许重复。
还是总结一下：
- HashMap通过hash函数计算出key对应的HashCode
- HashMap通过HashCode定位bucket上存储位置（数组下标）
- 如果数组下标对应链表，此时HashMap遍历链表中每一个Entry对象
- 在遍历过程中，HashMap使用equals方法检测当前Entry对象中key去传入可以是否相等，如果相等读取Entry中value值。
如何衡量HashMap的性能呢？
根据Oracle Java文档，HashMap实例有两个影响其性能的参数:初始容量和负载因子。容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。
负载因子是衡量散列表容量自动增加之前允许其达到的满度。当哈希表中的条目数量超过负载因子和当前容量的乘积时，将对哈希表进行重新哈希(即重建内部数据结构)，以便哈希表的桶数量大约是当前的两倍。
在HashMap类中，load factor的默认值是(.75)。
static final float DEFAULT_LOAD_FACTOR = 0.75f;//装载因子
HashMap的扩容机制
- HashMap默认容量是16，就是初始化的时候开辟了16块内存。
- HashMap默认负载因子是我们说的0.75
- HashMap在调用put方法时，如果发现HashMap中bucket占用率到16*0.75值则进行扩容
- HashMap在扩容后其容量达到原始容量2倍
- HashMap在扩容后通过重新计算entry对象在bucket中存储位置//hashcode是这么计算来的:异或，经过异或，可以提高hash值的散列度
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12（2的倍数避免内存碎片，可以减少冲突，移位操作效率也高）
threshold = newThr; //12
(p = tab[i = (n - 1) & hash]) //做与运算
//扩容
if(--size > threshold) resize();
HashMap为什么要进行扩容？
HashMap进行扩容操作时并不是为了存储更多数据。HashMap进行扩容时为了减少碰撞几率，来提供HashMap运行效率。因为经常发生碰撞几率的时候，是要去遍历链表的，这样就增加了时间。
HashMap扩容时会出现什么问题？
- 在单线程情况下，HashMap扩容时对运行效率产生降低问题，就不会有其他问题。
- 多线程情况下，产生竞条件（race condition）进而导致死循环。假设线程a和线程b在同一时刻下都认为当前HashMap进行扩容，扩容链表中Entry对象存放顺序会反过来，此时Entry对象新的Bucket位置上从链表中第一个位置开始重新存储。HashMap这样做的本次防止出现尾部遍历地场景。当时此时如果线程a和线程b都要将自己的管理的Entry存入到同一个链表中第一个位置，此时出现竞争条件进行产生了死循环。
- 在多线程的情况下，不能使用HashMap
参考链接：
① Hashing :How HashMap Works In Java Or How Get() Method Works Internally
