学过数据结构的读者们想必其实也都学过HashMap
,面试官问你的时候,想来你都是很清楚的知道HashMap
是怎样的一个构成?确实很简单,就是数组加链表嘛。那再问你Hashtable
和HashMap
的区别是什么?脑子也不用想,又能出来一个答案线程安全和线程不安全,Hashtable
不允许存在空值呗。那继续往深处问,HashMap
是怎么做性能优化的?这个时候你是怎么样的反应呢?如果知道红黑树,那就能答出来;不知道的话那不是就凉了,因为这个时候连ConcurrentHashMap
都需要放弃回答了!!!
其实思路大致都是相同的,所以这里只分析一个HashMap
,先贴出他的几个常见用法。
HashMap hashMap = new HashMap(); hashMap.put(key, value); hashMap.get(key); 复制代码
主要从这个方面对HashMap
的整个工作流程进行分析。
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 对数组的一个保护,不能超过int最大值范围 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); } 复制代码
其实在无参构造方法,我们并没有看到所谓的数组的初始化,他只对我们的负载因子做了一个初始化,也就是我们一直常说的0.75f,但为什么是0.75f呢,只能说是一个经验值,也就是经验所致,因为0.5f时空间太浪费,1f时容易出现极端情况,当然也不是随便定的,设计师肯定是做了很多的测试的,但依旧是一个经验值,或者说是测试后的最优解。
回到我们之前的问题,既然我们学习的时候学到过HashMap
是一个数组+链表。那做第一个思考为什么初始化不见了? 先带着这样的问题继续啊往下走。
先看看自己动手初始化容量构造函数,最后都会调用下方的tableSizeFor()
方法。
static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } 复制代码
本质意思就是把数值变成2的指数倍,这样的好处是计算方便处理。但是出现同样的问题,没有初始化,这里也只看到了容量。问题继续保留。
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); // 1 } // 由注释1直接调用的方法putVal() final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 第一次来判断的时候,显然的tab是一个空,因为在构造函数中,我们并没有看到他的初始化,那么必然要调用resize()方法。 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 2,未能初始化而必然调用的方法 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode)这篇关于面试中的HashMap、ConcurrentHashMap和Hashtable,你知道多少?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!