Java系列之 - HashMap详解

什么是HashMap？

---

1. HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。
2. 这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。
3. HashMap数组每一个元素的初始值都是Null

HashMap结构图.png

static class HashMapEntry<K, V> implements Entry<K, V> {
    final K key;
    V value;
    final int hash;
    HashMapEntry<K, V> next;
   ......
}

1、HashMap本质上是一个HashMapEntry构成的数组，当插入一个基本类型的时候会产生自动装箱的消耗。
2、每个Entry的实体都包括：
    a、一个非基本类型的key
    b、一个非基本类型的value
    c、一个key的Hashcode
    d、指向下一个Entry的指针

HashMap和HashTable的区别

---

1. HashMap是非synchronized，而Hashtable是synchronized。
2. HashMap可以接受为null的键（key）和值（value），而HashTable不行。
3. HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。
4. 单线程环境下HashMap比HashTable要快。
5. HashMap不能保证随着时间的推移Map中的元素次序是不变的。
   
   

你知道HashMap的工作原理吗？

---

1. HashMap是基于hashing的原理，我们使用put(key,value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。
2. 当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。
   
   

当两个对象的hashcode相同会发生什么？

---

1. hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。
2. 在同一个位子上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。
   
   

如果两个键的hashcode相同，你如何获取值对象？

---

1. 当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置。
2. 找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。
   
   

如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

---

1. 默认初始容量是16，负载因子大小为0.75，即超过16 * 0.75 = 12时就会扩容。
2. 初始大小和扩展大小都是2的n次方，这样元素分布相对均匀，性能最高。
3. 扩容之后要重新rehashing计算hashcode来找到在新的数组中的位置，比较消耗性能。

/**
 * 1、为什么加载因子要默认是0.75？
 */
首先如果为0.5空间浪费太多，如果为1势必会影响put的效率 
在理想情况下,使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布
0: 0.60653066
1: 0.30326533
2: 0.07581633
3: 0.01263606
4: 0.00157952
5: 0.00015795
6: 0.00001316
7: 0.00000094
8: 0.00000006
如上表，用0.5作为加载因子时，碰撞链表长度大于8的概率已经很小了
如果用0.75作为加载因子，链表长度几乎不可能大于8
所以从某种意义上说这个0.75是一个概率统计的结果，也是一个佛系的选择
实际上在JDK1.8中，如果链表的长度大于8，那么链表转为红黑树

/** 
 * 2、为什么数组大小为2的幂？
 * HashMap寻找Index位置是通过位运算计算出来的，但是原理是hashCode对length取余数
 * 只有是2的次幂的时候 hashCode & (length - 1) == hashCode % length
 */
static int indexFor(int hashCode, int length) {  
    return hashCode & (length-1);  
} 

你了解重新调整HashMap大小存在什么问题吗？

---

1. 当多线程的情况下，可能产生条件竞争(race condition)。
2. 如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。
   
   

android.util.ArrayMap/android.support.v4.util.ArrayMap

---

1. ArrayMap 用了两个数组。在它内部用了Object[] mArray来存储Object,还用了int[] mHashes 来存储hashcode,当存储一对键值对的时候。

• Key/Value会被自动装箱。
• key会存储在mArray[]的下一个可用的位置。
• value会存储在mArray[]中key的下一个位置。（key和value在mArray中交叉存储）
• key的哈希值会被计算出来并存储在mHashed[]中。

2. 当查找一个key的时候：

• 计算key的hashcode。
• 在mHashes[]中对这个hashcode进行二分法查找。也就意味着时间复杂度增加到了O(logN)
• 一旦我们得到了这个哈希值的位置index。我们就知道这个key是在mArray的2index的位置，而value则在2index+1的位置。
  
  

android.util.SparseArray/SparseIntArray/SparseLongArray/SparseBooleanArray

---

1. 和ArrayMap一样，它里面也用了两个数组。一个int[] mKeys和Object[] mValues。从名字都可以看得出来一个用来存储key一个用来保存value的。

2. 当保存一对键值对的时候：

• key（不是它的hashcode）保存在mKeys[]的下一个可用的位置上。所以不会再对key自动装箱了。
• value保存在mValues[]的下一个位置上，value还是要自动装箱的，如果它是基本类型。

3. 查找的时候：

• 查找key还是用的二分法查找。也就是说它的时间复杂度还是O(logN)
• 知道了key的index，也就可以用key的index来从mValues中检索出value。
• 相较于HashMap,我们舍弃了Entry和Object类型的key,放弃了HashCode并依赖于二分法查找。在添加和删除操作的时候有更好的性能开销。
• KitKat以前的版本用android.support.v4.util.SparseArrayCompat