导图社区 Java基础
- 142
- 8
- 2
- 举报
Java基础
深入源码分析Java 容器框架，面试重点内容分析，包含了基本概念、集合（容器）、迭代器、实现类剖析等内容。
编辑于2021-07-15 15:10:27
- 相似推荐
- 大纲
Java基础
基本概念
初始化顺序
在类的内部，变量定义的顺序决定了初始化的顺序，即使变量定义散布于方法定义之间，他们仍会在任何方法（包括构造方法）调用之前得到初始化。（针对类中没有静态变量）
在类的内部，static块与变量的初始化顺序是由定义顺序决定的，即谁先定义谁就先初始化
集合（容器）
简介
基本概念
Java容器类类库的用途是“保存对象”，即不能存储基本数据类型。Java中有2个顶级容器Collection、Map
Collection
一个独立元素的序列，这些元素都服从一条或多条规则。List必须按照插入的顺序保存元素，而Set不能有重复的元素。Queue按照排队规则来确定对象产生的顺序（通常与他们被插入的顺序相同）。
Map
一组成对的“键值对”对象，允许你使用键来查找值。映射表允许我们使用另一个对象来查找某个对象，它也被称为“关联数组”，因为它将某些对象与另外一些对象关联在了一起。
集合相关工具类
Collections
该类的方法都是静态方法，这些方法提供了很多功能，比如排序
Arrays
该类的方法都是静态方法，这些方法提供了很多功能，比如排序
集合结构图
实现类剖析
Collection
List
概念
List承诺可以将元素维护在特定的序列中
实现类
ArrayList
通过阅读源码发现，ArrayList的底层实现是基于Object类型的数组，名称为elementData，数组的默认长度字段size为10。由于集合的长度是可以动态扩展的，因此当elementData被装满了的时候，ArrayList的扩展方法是grow。之后通过Arrays.copyOf创建一个新的数组
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); }
源码解释
关键代码是newCapacity=oldCapacity+(oldCapacity>>1) 意思就是newCapacity是oldCapacity的1.5倍。
add()方法
源码
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
解释
就是在elementData数组的最后一个元素后面添加新的元素e
特性
优点
遍历，查询速度快
缺点
插入、删除效率低
LinkedList
通过阅读源码发现，LinkedList的底层实现是2个Node类型的字段，名称分别为first、last、以及表示容器大小的int类型的字段size；Node类型是LinkedList中的静态内部类。
Node静态内部类
源码
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
源码解释
Node包含3部分，item、prev、next
LinkedList类的成员变量
源码
transient int size = 0; transient Node<E> first; transient Node<E> last;
源码解释
size：表示容器大小。 first：表示第一个节点。 last：表示最后一个节点。
add()方法
源码
public boolean add(E e) { linkLast(e); return true; }
解释
将添加的元素放到链表的末尾
linkLast()方法
源码
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
解释
该方法会将形参e放到链表的末尾
特性
优点
插入、删除数据效率高
缺点
随机查询、遍历效率低
Vector
通过源码发现，Vector的底层实现是基于Object类型的数组elementData，默认情况下的初始容量是10，还有2个重要字段，他们都是int类型，elementCount用来表示元素的总数，capacityIncrement指定的值表示每当数组满了的时候增加的容量，用户可以通过构造器传入值。
线程安全源码分析
部分源码
public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; }
vector实现线程安全的原理： 在public方法上添加synchronized关键字
特性： 我们都知道Vector是线程安全的，而且底层实现是数组。
Set
概念
Set不保存重复的元素
思考：如何判断元素重复？
Set具有与Collection完全一样的接口，只是他们的行为不同
实现类
HashSet
通过源码发现，HashSet的底层实现是基于HashMap类型的成员变量map，还有一个Object类型的成员常量PRESENT。
源码
add方法
public boolean add(E e) { return map.put(e, PRESENT)==null; }
分析，PRESENT是一个Object类型对象
hash方法
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
分析，用于计算key的哈希值
TreeSet
通过源码发现，TreeSet的底层实现是基于NavigableMap类型的成员变量m，还有一个Object类型的成员常量PRESENT。
LinkedHashSet
LinkedHashSet类继承了HashSet，并且没有新增成员变量，只是增加了几个方法
Queue
总结
List类型容器
数据的添加顺序就是容器中数据排列的顺序
Map
概念
Map是一个键值对集合，key无序且唯一
实现类
HashMap
特性
键不可重复，值可重复
底层哈希表
线程不安全
允许key为null，允许value为null
源码
通过源码分析发现，HashMap类定义了多个常量，默认初始化容量为16、最大容量为2的30次方、默认负载系数为0.75、以及多个阈值；还有多个变量， Node<K,V>类型的数组table（存储键值对）， int类型的size（表示map中包含键值对的数量）， int类型的modCount（此HashMap在结构上被修改的次数结构修改是指那些更改HashMap中映射的数量或以其他方式修改其内部结构的修改）， int类型的threshold（容量的零界点，当容器包含的元素达到这个零界点就会使table数组进行扩容），threshold的值为loadFactor*initialCapacity（即负载系数乘以初始容量）； HashMap中有个很重要的静态内部类Node<k,v>，该内部类继承自Map.Entry<k,v>。
静态内部类Node部分源码
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; }
代码分析，hash是哈希值（不可变），key是键（不可变），next表示下一个节点
put()方法源码
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
putVal()方法源码
方法形参说明
/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */
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; }
解读，该方法是向HashMap中添加元素的核心逻辑。 1.声明一个Node<K,V>类型的数组tab，声明一个Node<K,V>类型的变量p，以及2个整数n、i。 2.将成员变量table的引用赋给tab，如果tab为null，那么满足if条件，就执行条件语句；如果第一个条件不满足，继续判断第二个条件，判断table的长度是否等于0，即判断table中是否有键值对。 3.resize()方法的用途是初始化或扩大Node<K,V>数组的大小，这里的含义明显是初始化并返回这个数组table；因此n的值表示Node<K,V>数组的长度。 4.这是一个if语句的条件部分，这部分做了如下操作：给i赋值，赋值规则是(n-1)&hash，这个hash是key的哈希值，n是数组的长度；给i赋值之后，将tab[i]赋值给p,如果p为空，那么执行满足if条件的语句。 5.这里是满足条件的语句，newNode(hash,key,value,null)语句会创建一个Node<K,V>类型的对象，我们知道Node的成员变量有4个，分别是hash、key、value、next，那么参数null肯定是传参个next，即next被赋值为null；创建的这个Node对象的引用会被传给tab[i]；之后使modCount执行自加操作，接着执行if(++size>threshold)语句，这个语句的用途是判断size自加后是否大于threshold。 6.这里不满足条件语句，即p!=null，那么声明一个Node<K,V>类型变量e、以及一个K类型的变量k;之后执行条件判断语句。 7.如果p.hash等于新加的对象的hash，且，....
hash()方法源码
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
用于计算key的hash值
HashMap构造方法
默认构造方法
/** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
总结
默认情况下，即使用默认构造方法时，table数组的初始容量为16,负载系数为0.75
指定初始容量与负载系数的构造方法
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ 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); }
总结
指定table数组的初始容量和负载系数，从而确定临界值threshold
指定初始容量的构造方法
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
总结
指定初始容量，负载系数仍是使用默认值，即0.75
总结
如果在创建HashMap之前就知道元素的数量，那么可以指定初始化容量与负载系数，从而确定临界值，使临界值等于元素的数量。
如果在创建时不知道HashMap中的数量，那么就使用默认的构造函数
初始化或扩容方法resize()
源码
/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
总结
扩容策略是：容量扩大一倍，临界值也扩大一倍
如何构建hashMap才最高效
参考自https://blog.csdn.net/l18848956739/article/details/85998121
Hashtable
特性
键不可重复，值可重复
底层哈希表
线程安全
key与value都不能为null
键为null会在put方法中执行key.hashCode()时发生空指针异常
值为null会在put方法中满足if(value==null)条件，从而通过throw抛出空指针异常
通过源码分析发现，Hashtable类包含的重要成员变量如下： Entry<?,?>类型的数组table，用于存储Hashtable的数据； int类型的count，表示Hashtable中Entry的总量； int类型的threshold，容量临界值，值为capacity*loadFactor,当Hashtable包含的Entry大于threshold时，table数组会重新哈希； float类型的loadFactor，负载系数； int类型的modCount，Hashtable被修改的次数。
源码
成员变量
/** * The hash table data. */ private transient Entry<?,?>[] table; /** * The total number of entries in the hash table. */ private transient int count; /** * The table is rehashed when its size exceeds this threshold. (The * value of this field is (int)(capacity * loadFactor).) * * @serial */ private int threshold; /** * The load factor for the hashtable. * * @serial */ private float loadFactor; /** * The number of times this Hashtable has been structurally modified * Structural modifications are those that change the number of entries in * the Hashtable or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the Hashtable fail-fast. (See ConcurrentModificationException). */ private transient int modCount = 0;
put()方法
public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry<K,V> entry = (Entry<K,V>)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; }
TreeMap
特性
键不可重复，
底层是红黑树
线程不安全
key不能为null
通过源码分析发现，TreeMap主要包含以下成员变量： Entry<K,V>类型的变量root，表示根节点； int类型的变量size，表示树包含的节点数，即Entry的数量； Comparator类型的变量comparator，用于比较对象的大小； int类型的变量modCount，改变树结构的次数。
源码
TreeMap的成员变量
源码
/** * The comparator used to maintain order in this tree map, or * null if it uses the natural ordering of its keys. * * @serial */ private final Comparator<? super K> comparator; private transient Entry<K,V> root; /** * The number of entries in the tree */ private transient int size = 0; /** * The number of structural modifications to the tree. */ private transient int modCount = 0;
功能分析
comparator
用于比较key的大小
root
树根
size
所有的Entry数量
modCount
被结构化的次数
put()方法
public V put(K key, V value) { Entry<K,V> 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<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }
静态内部类Entry
static final class Entry<K,V> implements Map.Entry<K,V> { K key; V value; Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent; boolean color = BLACK;
通过源码发现，TreeMap最重要的成员变量是Entry<K,V>类型的root，是树根的意思，这个树是红黑树。
更多详细内容参考《Java核心技术卷I》
迭代器
基本概念
任何容器类，都必须有某种方式可以插入元素并将他们再次取回。虽然不同类型的容器有他们自己的具体取回方式，但是每种不同类型的容器的取回方式不一样。那么如何才不重写代码就可以应用于不同类型的容器？这就是需要迭代器的目的。
接口
Iterable
该接口最重要的方法是iterator()，用于获取Iterator类型的对象
Collection接口继承了该接口
Iterator
用于获取容器中的元素
接口方法
E next()
boolean hasNext()
void remove()
删除上次调用next()方法返回的元素
注意事项
迭代器Iterator只能向后遍历
获取迭代器后必须先调用next()方法，之后才能调用remove方法删除元素
不能连续调用remove()方法，中间必须存在next()方法
详细内容参考《Java核心技术卷I》