不同版本的JDK的HashMap的底层实现均有所不同
JDK各个版本的源码查看
各个版本的源码查看：https://blog.csdn.net/zuochao_2013/article/details/79624579
android各个版本对应的JDK版本
https://blog.csdn.net/u010825468/article/details/78909550
通过改变build.gradle里的版本，即可查看对应JDK的源码。
后来我发现上面的这个表不准确，android我用SDK API 19，然后按照下面的方法，用010Editor来查看HashMap.class，发现竟然是JDK1.5。
https://blog.csdn.net/mengxiangxingdong/article/details/89437087
image.png
经我测试，真正的情况是API19、20都是JDK1.5，然后到了API21直接就JDK1.7了，没有用到JDK1.6。
大坑：
看了很多的博客，但是用android.jar里的源码一对比，怎么也对不上。
http://www.apkbus.com/thread-567645-1-1.html
原来android源码里的JDK和Java的JDK不是一个东西。
HashMap的特性
- 线程不安全
各个版本的HashMap的区别
https://www.nowcoder.com/discuss/151172
https://www.2cto.com/kf/201707/654203.html
https://blog.csdn.net/qq_36520235/article/details/82417949
JDK1.8的HashMap实现
https://www.cnblogs.com/little-fly/p/7344285.html
https://blog.csdn.net/qq_22200097/article/details/82791479
JDK1.7及以下的HashMap实现
- HashMap的主干是数组(不要以为带个Hash就和HashTable扯上关系了)，数组的元素是HashMapEntry
- HashMapEntry是一个链表结构
https://blog.csdn.net/qq_38455201/article/details/80732839
https://blog.csdn.net/C18298182575/article/details/87167323
JDK1.5源码分析
主干数组初始化
/**
* Min capacity (other than zero) for a HashMap. Must be a power of two
* greater than 1 (and less than 1 << 30).
*/
private static final int MINIMUM_CAPACITY = 4;
/**
* An empty table shared by all zero-capacity maps (typically from default
* constructor). It is never written to, and replaced on first put. Its size
* is set to half the minimum, so that the first resize will create a
* minimum-sized table.
*/
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];
/**
* Constructs a new empty {@code HashMap} instance.
*/
@SuppressWarnings("unchecked")
public HashMap() {
table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
}
可见，HashMap的无参构造方法默认会创建一个大小为2的数组。
...版本太旧，就不往下分析了。
JDK1.6源码分析
https://blog.csdn.net/rocksteadypro/article/details/80082822
JDK1.7源码分析
https://www.cnblogs.com/xiaolovewei/p/7993521.html
https://www.cnblogs.com/xiaozhongfeixiang/archive/2019/09/23/11548563.html
需要注意的点：
-
key是如何计算出数组的下标的
image.png
哈希值求数组下标
hash & (tab.length - 1);扩容为啥是2的倍数，和上面这个公式也是相关的：https://blog.csdn.net/ptsx0607/article/details/68945883,保证了散列的均匀性,哈希碰撞的机率就会减小。
-
头插法与链表
https://blog.csdn.net/insomsia/article/details/88367436
看put方法：@Override public V put(K key, V value) { if (key == null) { return putValueForNullKey(value); } int hash = secondaryHash(key); HashMapEntry<K, V>[] tab = table; int index = hash & (tab.length - 1); for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) { if (e.hash == hash && key.equals(e.key)) { preModify(e); V oldValue = e.value; e.value = value; return oldValue; } } // No entry for (non-null) key is present; create one modCount++; if (size++ > threshold) { tab = doubleCapacity(); index = hash & (tab.length - 1); } addNewEntry(key, value, hash, index); return null; }重复元素判断:hash相同，key相同的肯定是同一个元素。
e.hash == hash && key.equals(e.key)但是可能不同的元素hash值不一样，算出的index却一样，但是又不是同一个元素(这就是哈希碰撞问题，哈希算法无法逃避这个问题)，数组中的这个索引位置已经被占据了，那么我怎么存储这个新的元素呢？
请看HashMapEntry这个类：
image.png
再看添加HashMapEntry的方法：void addNewEntry(K key, V value, int hash, int index) { table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]); } HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) { this.key = key; this.value = value; this.hash = hash; this.next = next; }对于addNewEntry方法
如果index处本身没有元素占据，此时table[index]就是null。
那么直接就添加一个HashMapEntry元素，它的next指针指向原来Index位置的元素，也就是null；如果index处本身有元素，也就是哈希冲突了，
那么直接就添加一个HashMapEntry元素，它的next指针指向原来Index位置的元素，也就是哈希冲突的元素。头插法就是这么来的。对于计算机专业的人来说，得出上面的结论可能不难。但是对于非计算机专业的我来说，慢慢的发现了数据结构之类，简直太美妙了！
网友评论