这一块问来问去主要还是ArrayList和HashMap。HashMap这一块源码是必须要懂的。在有的面试官眼里是必备的基础。
ArrayList继承自AbstractList,初始默认容量为10(private static final int DEFAULT_CAPACITY = 10)
ArrayList有三个构造函数,一个不传参默认生成一个初始容量为10的elementData数组,另一个传入一个初始容量参数,小于0会抛出异常,最后一个是传入一个指定的集合
传入初始容量的构造函数如下:
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
ArrayList使用add添加元素的时候会调用grow(size+1)方法来增加容量
private Object[] grow(int minCapacity) { return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity)); } private int newCapacity(int minCapacity) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity <= 0) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) return Math.max(DEFAULT_CAPACITY, minCapacity); if (minCapacity < 0) throw new OutOfMemoryError(); return minCapacity; } return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity); }
上述代码中ArrayList的MAX_ARRAY_SIZE为Integer.MAX_VALUE-8
HashMap的数据结构为:
JDK1.7及之前:数组+链表;JDK1.8:数组+链表+红黑树
静态常量(常用)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; //负载因子
哈希桶数组中的存储数据结构
//这个是HashMap的一个内部类,实现了Map.Entry接口,其构造方法包含四个参数:hash,key,value,next。 //然后这里面还定义了一些其他方法,如getKey(),getValue(),toString(),setValue(),还重写了equals方法。 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; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
构造方法(4个)
//第一个传入初始容量和负载因子 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); 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 } //第四个传入一个指定的Map public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
hash函数
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
put源码
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } //参数onlyIfAbsent表示是否替换原值,参数evict我们可以忽略它,它主要用来区别通过put添加还是创建时初始化数据的 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //首先判断table是否为空或者长度是否为0,如果是则需要调用resize()扩容 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //根据hash值计算在哈希桶中的索引,如果当前索引的位置没有节点,直接新建节点添加 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //如果有节点 else { Node<K,V> e; K k; //判断要插入的key是否等于当前索引中的首个元素,如果等于直接覆盖 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判断是否是红黑树,如果是,则在树中直接插入节点 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //如果不是则开始遍历链表准备插入,如果链表长度大于8则转换成红黑树插入,否则链表插入,若key存在直接覆盖 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //插入成功后,判断键值对数量size是否超过了最大容量threshold,超过则扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
get源码
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //首先判断table是否为空,其长度是否大于0,以及当前位置是否为空,如果有一个是则返回null,不是继续判断 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //判断当前位置的首节点是否等于key,是则返回,不是则遍历下一节点,然后判断是否为树节点,如果是转为树查找,不是则遍历链表查找。 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
下述代码为Java1.7的源代码
void resize(int newCapacity) { //传入新的容量 Entry[] oldTable = table; //引用扩容前的Entry数组 int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了 return; } Entry[] newTable = new Entry[newCapacity]; //初始化一个新的Entry数组 transfer(newTable); //将数据转移到新的Entry数组里 table = newTable; //HashMap的table属性引用新的Entry数组 threshold = (int)(newCapacity * loadFactor);//修改阈值 }
Java1.8对扩容做了哪些优化?
在java1.7版本的时候,扩容的时候每次都需要重新计算hash值,但是因为HashMap使用的是2的幂次方扩展,所以可以发现每次扩容,
元素的位置要么在原位置,要么在原位置上移动新扩容的大小所处的位置。而元素在哈希桶上的位置是由(length-1)& hash得到的,
所以并不需要每次都重新计算hash值,只要看之前hash新增的那个比特是1还是0即可。
HashMap扩容为什么要取2的幂次方?
因为只有在length为2的幂次方的时候hash%length==(length-1)& hash,使用位运算符能够大大提高计算效率
HashMap在并发时可能出现的问题主要是以下两方面:
比如有两个线程A和B,首先A希望插入一个key-value对到HashMap中,首先计算记录所要落到的 hash桶的索引坐标,然后获取到该桶里面的链表头结点,此时线程A的时间片用完了,而此时线程B被调度得以执行,和线程A一样执行,只不过线程B成功将记录插到了桶里面,假设线程A插入的记录计算出来的 hash桶索引和线程B要插入的记录计算出来的 hash桶索引是一样的,那么当线程B成功插入之后,线程A再次被调度运行时,它依然持有过期的链表头但是它对此一无所知,以至于它认为它应该这样做,如此一来就覆盖了线程B插入的记录,这样线程B插入的记录就凭空消失了,造成了数据不一致的行为。
这种情况发生在JDK1.7 中HashMap自动扩容时,当2个线程同时检测到元素个数超过 数组大小 × 负载因子。此时2个线程会在put()方法中调用了resize(),两个线程同时修改一个链表结构会产生一个循环链表(JDK1.7中,会出现resize前后元素顺序倒置的情况)。接下来再想通过get()获取某一个元素,就会出现死循环
因为红黑树和其他平衡树的查找时间复杂度都是O(log(n)),但是红黑树的插入和删除最多两次旋转即可实现平衡,而其他平衡树的旋转比红黑树的旋转要复杂许多
HashMap的链表结构什么时候会转化成红黑树
长度为8时
为什么选长度为8时转换
这个严格意义上来说是由概率决定的,因为链表长度大于等于8时转成红黑树正是遵循泊松分布
加载因子如果定的太大,比如1,这就意味着数组的每个空位都需要填满,但如果一直等数组填满才扩容,虽然达到了最大的数组空间利用率,但会产生大量的哈希碰撞,同时产生更多的链表。如果设置的过小,比如0.5,这样一来保证了数组空间很充足,减少了哈希碰撞,这种情况下查询效率很高,但消耗了大量空间。
因此,我们就需要在时间和空间上做一个折中,选择最合适的负载因子以保证最优化,取到了0.75
这个与HashMap中table下标的计算有关。
n = table.length; index = (n-1) & hash;
因为,table的长度都是2的幂,因此index仅与hash值的低n位有关,hash值的高位都被与操作置为0了。 假设table.length=24=16
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bitejTv7-1632552369746)(C:\Users\MiracleWK\AppData\Roaming\Typora\typora-user-images\image-20210706101655387.png)]
由上图可以看到,只有hash值的低4位参与了运算。 这样做很容易产生碰撞。设计者权衡了speed, utility, and quality,将高16位与低16位异或来减少这种影响。
3.8和3.9推荐大家看博客ConcurrentHashMap实现原理与分析