深入理解Array、List、Map集合框架底层实现原理
背景:
为什么要做这篇文章呢?本人很讨厌去记冗长的词,更喜欢去理解钻研,发现有趣的事,其实就是大脑海马区水平下降,也叫记忆力不好,初学者看本文需要对数组、集合有一定的了解,任何集合框架都有三大模块:对外的接口、接口的实现和对集合运算的算法。
Arrays
下面创建一个数组
int[] array=new int[10];
下图是在内存上的存储状况
数组,在内存上给出了连续的空间
缺点
- 数据类型定型
- 数组定长、大小固定,不适合动态存储,不方便动态添加
- 只能通过数组索引去赋值,所以不存在数组插入说法
- 不能切确的知道数组内存了多少数据,length只是读取数组长度,这个长度不受数组内容影响
优点
- 拥有数组索引,查询速度比链表快
List
Java中的集合框架层次结构
List接口
public interface List<E> extends Collection<E>
List存在于java.util,有兴趣的同学可以去阅读jdk1.8Api文档
List接口的特点:
一个有序集合(也被称为序列)。此接口的用户在列表中的每个元素都被插入的地方有精确的控制。用户可以通过它们的整数索引(在列表中的位置)访问元素,并在列表中搜索元素。
与设置不同的是,列表通常允许重复元素。更正式,通常允许列表元素e1和e2这样e1.equals(e2)对,他们通常允许多个null元素是否允许null元素在所有。(引用官方文档的话)
ArrayList
- 优点:操作读取操作效率高,基于数组实现的,可以为null值,可以允许重复元素,有序,异步。
- 缺点:由于它是由动态数组实现的,不适合频繁的对元素的插入和删除操作,因为每次插入和删除都需 要移动数组中的元素。
ArrayList底层数据结构
话不多说上源码(主要谈谈add()方法)
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
源码可以看出List fruits=new ArrayList();构造一个初始容量为10的空列表。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
读懂这段对于初学者也是毫不费力的,唯一要懂的就是java 的位运算符,’>>‘与’<<’,oldCapacity >> 1表示oldCapacity /2,oldCapacity << 1表示oldCapacity *2,由此可见底层是基于数组改造的,所以数据结构图就是
(上图若存在侵权请联系作者,谢谢)
如图可见一旦list超过初始容量就会扩大到以前的容量的1.5倍。
上面说过数组是没有真正意义上的插入的,ArrayList虽然底层是数组,但JDK对其做了大量的封装所以拥有随机访问和随意插入的能力
打印结果:
当然这里建议大家使用for循环,比较适合数组遍历,foreach适合LinkedList的遍历循环
LinkedList
- LinkedList是List接口的双向链表非同步实现,并允许包括null在内的所有元素。
- 底层的数据结构是基于双向链表的,该数据结构我们称为节点
- 允许所有元素为null
- 它的查找是分两半查找,先判断index是在链表的哪一半,然后再去对应区域查找,这样最多只要遍历链表的一半节点即可找到(具体找JDK1.8文档)
Map
实现类介绍
- <K,V> K不能为null,没有意义(机制可以认为K为null),也不能重复,后面讲解Key生成hash值会解释。
- 一个K只能对应唯一的V,既不能一对多,这个就很符合我国婚姻法了
- HashMap底层采用数组和链表组合成的数据结构,无序、方法不同步,线程不安全,(翻阅源码可以发现HashMap方法内没标明synchronized关键字)HashMap效率较高,Hashtable效率较低
- HashTable和HashMap一样,就是方法同步,线程安全
- TreeMap有序,底层采用红黑树(自平衡的二叉树),线程不安全(ensure)
HashMap使用频繁,重点讲解
/**
* The default initial capacity - MUST be a power of two.
* 默认初始容量—必须是2的幂。
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
说明初始化容量是16
static final int MAXIMUM_CAPACITY = 1 << 30;
最大容量是2的30次方
/**
* The load factor used when none specified in constructor.
* 构造函数中没有指定时使用的负载因子。
* 负载因子,当 已使用容量 > 总容量 * 负载因子 时,需要扩容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Map<?,?> entity=new HashMap<>();就会调用上述代码,可以发现并没有创建数组,这里只是采用了延迟加载模式,只有put时才会创建一个容量默认的数组,这样就不造成内存浪费,下面是源码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
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)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
细心阅读者会发现key是经过hash计算过才存入内存中,内存不可能存在相同的hash值.所以不能有重复的key
HashMap数据结构
第一次put时,首先计算key的hash值
计算这次put要存入数组位置的索引值:index=(数组大小 - 1) & hash
大家不要介意图有点烂,主要还是看源码。不断的put就会产生数组不够用和Hash碰撞的问题,数组不够用就会触发扩容,一旦扩容就会产生哈希碰撞,这时链表就派上用场了,HashMap就是通过链表解决哈希冲突的。
(上图存在侵权请联系作者)
**感谢阅读,祝你在程序的世界里越走越远!!**