Javaer.Yan 发表于 2021-10-2 14:51:52

深入分析Java集合源码

1 Java集合概览

https://p9.toutiaoimg.com/large/pgc-image/816f656afb284d1f95a20fdf8abec157
2 List接口下集合源码分析

2.1 ArrayList

(1)集合体系
https://p6.toutiaoimg.com/large/pgc-image/fc24d9b0dbc94ced95cfc535cf29ae91
(2)根本使用
//实例化
ArrayList list = new ArrayList(5);
//添加元素
list.add(1);
list.add(2);
//遍历元素
for (Integer i : list) {
System.out.print(i);
}
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i));
}
//删除元素
System.out.println(list.remove(0));
(3)源码剖析

[*]线程安全问题:线程不安全
[*]public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData = e;
return true;
}
[*]理由:没有任何线程同步机制和分段锁等保护线程安全的措施
[*]扩容机制:当元素添加满时将数组大小扩大1.5倍
[*]//主要是调用grow方法举行扩容
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);
}
[*]元素是否可以为null:可以为null
[*]public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData = e;
return true;
}
[*]添加元素时并没有代码要求元素不能为null
2.2 LinkedList

(1)集合体系
https://p5.toutiaoimg.com/large/pgc-image/6cc50d29b92245f38ca1d922386dad02
(2)根本使用
//实例化
LinkedList linkedList = new LinkedList();
//添加元素
linkedList.add(23);
linkedList.add(44);
linkedList.add(12);
//删除元素,删除的是第一个结点
linkedList.remove();
//修改某个结点对象
linkedList.set(1, 999);
//获取链表的第二个对象
Object o = linkedList.get(1);
//遍历
Iterator iterator = linkedList.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.print(next);
}
for (Object o1 : linkedList) {
System.out.print(o1);
}
for (int i = 0; i < linkedList.size(); i++) {
System.out.print(linkedList.get(i));
}
(3)源码剖析

[*]是否须要扩容:不须要扩容,添加元素时直接放在队列的尾部,由上一个元素的next指针指该元素
[*]public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node l = last;
final Node newNode = new Node(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
[*]删除元素过程:将被删除元素的上一个节点的next指针指向被删除元素的下一个节点
[*]public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node x) {
// assert x != null;
final E element = x.item;
final Node next = x.next;
final Node prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
2.3 Vector

(1)集合体系
https://p3.toutiaoimg.com/large/pgc-image/638e332363564791a3d9723a33010ba9
(2)根本使用
//实例化
Vector vector = new Vector(18);
//添加元素
vector.add(100);
(3)源码剖析

[*]是否线程安全:线程安全,具有互斥锁synchronized
[*]public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData = e;
return true;
}
[*]扩容机制:当元素添加满时默认将数组大小扩大2倍,可以实例化时指定扩容的大小capacityIncrement
[*]private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
3 Set接口下集合源码分析

3.1 HashSet

(1)集合体系
https://p6.toutiaoimg.com/large/pgc-image/b596935af4e848a9b99e0daf028c24d0
(2)根本使用
HashSet hashSet = new HashSet();
hashSet.add(null);
hashSet.add(null);
hashSet.add("2");
System.out.println("hashSet=" + hashSet);
hashSet.forEach(s -> System.out.println(s));
hashSet.remove(null);
System.out.println(hashSet.contains("2"));
System.out.println(hashSet.contains(null));
(3)源码剖析

[*]底层:HashMap
[*]public HashSet() {
map = new HashMap();
}
[*]add方法:将HashMap的减存放元素,将HashMap的值放入空对象PRESENT,然后直接调用HashMap的add方法
[*]// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
[*]元素是否可以为null:可以
3.2 TreeSet

(1)集合体系
https://p3.toutiaoimg.com/large/pgc-image/f57cfa1ac1ca4384bbd20743fb559fdf
(2)根本使用
TreeSet treeSet = new TreeSet(new Comparator() {
//排序规则
@Override
public int compare(Object o1, Object o2) {
return ((String) o1).compareTo((String) o2);
}
});
treeSet.add("zs");
treeSet.add("ls");
treeSet.add("ww");
treeSet.add("zl");
(3)源码剖析

[*]自定义元素排序规则:
[*]TreeSet treeSet = new TreeSet(new Comparator() {
//排序规则 o1和o2代表先后元素的比较规则 (String) o1).compareTo((String) o2表示比较字符串的阿斯卡码 雷同时不放入
@Override
public int compare(Object o1, Object o2) {
return ((String) o1).compareTo((String) o2);
}
});
[*]add方法:底层调用了TreeMap的put方法 m.put(e, PRESENT)
[*]public V put(K key, V value) {
Entry t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry parent;
// split comparator and comparable paths
Comparator tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry entry = (Entry)tab;
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
4.3 TreeMap

(1)集合体系
https://p6.toutiaoimg.com/large/pgc-image/eaf768238bc7418dac82f4d39b015cfc
(2)根本使用
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
//按照Key的长度大小排序 相称时只插入一个
return ((String) o2).length() - ((String) o1).length();
}
});
treeMap.put("1", "zs");
treeMap.put("11", "ls");
treeMap.put("12", "ww");
(3)源码剖析
<ul>排序机制:构造方法中传入Comparator接口的匿名内部类
public TreeMap(Comparator
页: [1]
查看完整版本: 深入分析Java集合源码