创意电子

标题: 深入分析Java集合源码 [打印本页]

作者: Javaer.Yan 时间: 2021-10-2 14:51
标题: 深入分析Java集合源码
1 Java集合概览

2 List接口下集合源码分析

2.1 ArrayList

（1）集合体系

（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[size++] = 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[size++] = e;
return true;
}
添加元素时并没有代码要求元素不能为null

2.2 LinkedList

（1）集合体系

（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）集合体系

（2）根本使用
//实例化
Vector vector = new Vector(18);
//添加元素
vector.add(100);
（3）源码剖析

是否线程安全：线程安全，具有互斥锁synchronized
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = 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）集合体系

（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）集合体系

（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[index];
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）集合体系

（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

欢迎光临创意电子 (https://wxcydz.cc/)