一、collection
- Cloneable 可克隆
- Serializable 可序列化
- RandomAccess 为 List 提供快速访问功能，为空接口，只是一个可以快速访问的标识，即通过序号获取元素
1. List
基本介绍
ArrayList、Vector、LinkedList继承AbstractList(实现List接口)
- ArrayList和Vector使用数组实现，区别是前者不是线程同步，线程不安全，后者线程安全，且Vector扩容时翻倍size/创建对象时设置扩容量，ArrayList则扩容一半
- LinkedList使用循环双向链表数据结构
ArrayList
特点
- 维护一个数组，数组是拥有连续存储地址的存储块
- 查询修改效率高，插入删除较低
- 遍历ArrayList删除元素：使用iterator迭代器
- 线程不安全
1) 成员变量
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable{private static final long serialVersionUID = 8683452581122892189L;/*** 默认初始化容量*/private static final int DEFAULT_CAPACITY = 10;/*** 初始化时若容量为0，先不创建数组，第一次进行add操作才创建数组*/private static final Object[] EMPTY_ELEMENTDATA = {};/*** 主要用于使用无参构造器创建的对象（没有指定初始容量的对象）,在第一次添加元素时，扩容到初始变量10*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};/*** 用于存储元素的数组，数组的长度就是容器的容量* 当第一次添加元素并且满足elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA时，数组会扩容到 * 长度为DEFAULT_CAPACITY（10）* 非私有便于嵌套类访问*/transient Object[] elementData;/*** 数组储存的元素的个数，不等于容器容量*/private int size;/*** Integer的最大值减去8 = 2147483647 - 8 = 2147483639* 这是数组能够申请最大的大小，如果试图申请比这个还要大的大小，* 就会超过VM虚拟机的限制而抛出内存溢出的错误OutOfMemoryError*/private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
transient:
2) 构造方法
- 传入初始容量
- 容量为0：
elementData = EMPTY_ELEMENTDATA; - 容量大于0：
elementData = new Object[initialCapacity]; - 容量参数不合法，抛出异常
- 容量为0：
/*** 初始化容量** @param initialCapacity the initial capacity of the list* @throws IllegalArgumentException if the specified initial capacity* is negative*/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);}}
无参: `elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;````java /**
- Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } ```
传入容器
- 将容器转化为数组，赋值给elementData 传入容器前做非空判断
- 获取数组elementData长度
- 长度为0：
elementData = EMPTY_ELEMENTDATA; - 长度不为0，确保elementData是储存object的数组
public ArrayList(Collection<? extends E> c) {//确保容器c不能为null，否则会抛出异常elementData = c.toArray();if ((size = elementData.length) != 0) {//c.toArray()可能出错返回的不是Object，当返回的不是object时，就将elementData转化为储存object的数组if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}
- 长度为0：
// Collection.toArray调用的方法public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {@SuppressWarnings("unchecked")//根据class的类型来决定是new 还是反射去构造一个泛型数组T[] copy = ((Object)newType == (Object)Object[].class)? (T[]) new Object[newLength]: (T[]) Array.newInstance(newType.getComponentType(), newLength);//利用native函数，批量赋值元素至新数组中。System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));return copy;}
// 第一个参数：源数组// 第二个参数：开始复制的起始位置// 第三个参数：目标数组// 第四个参数：复制到的目标数组的起始位置// 第五个参数：复制的元素的长度System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
- 当
new ArrayList()时，底层创建空数组，只有第一次add的时候才重新初始化数组，容量默认为10```java private void grow(int minCapacity) {
//扩容1.5倍 等同于newCapacity = oldCapacity + (oldCapacity / 2)// overflow-conscious codeint oldCapacity = elementData.length;
} ```int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);
3) 增加
- 添加单个
- 确定底层elementData的容量
- 计算容器需要的容量
- 比较需要的容量和当前容量，看是否需要扩容(如果需要就进行扩容)，并将操作数加一
扩容：
- 计算新容量: 1.5倍—> 不够，则为需要的容量 —> 新容量超出虚拟机允许值，重新计算
- 复制原来的数组到新的数组
- 元素插入结尾，element存储个数加一
public boolean add(E e) {//确定内部容量ensureCapacityInternal(size + 1);//元素插入尾端，再将size加一//没有判断是否为null，所以可以存储nullelementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {//先调用calculateCapacity计算容器需要的容量，再调用ensureExplicitCapacity看是否需要扩容，并执行操作数加一ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {//如果对象调用无参构造器创建，并且是第一次执行add操作，就有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA//此时容器需要的容量是默认的10if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);}//否则，容器需要的容量是已经储存的元素个数加一 因为minCapacity= size + 1;return minCapacity;}private void ensureExplicitCapacity(int minCapacity) {//操作数加一modCount++;// 如果当前数组的容量小于需要的容量，就对数组进行扩容if (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {int oldCapacity = elementData.length;//先设置新容量为原来容量的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);//如果1.5倍的容量仍然小于需要的容量，设置新容量为需要的容量if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//当新容量超过虚拟机允许的大小，会重新计算合适的新容量if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// 将原来的数组复制到新的数组，并赋值给elementDataelementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {//如果所需容量小于0，抛异常if (minCapacity < 0)throw new OutOfMemoryError();//如果所需容量大于虚拟机允许值，返回整数最大值return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}
- 批量添加```java
public boolean addAll(Collection<? extends E> c) {
}//需要确保传入的集合不能为nullObject[] a = c.toArray();int numNew = a.length;//确认新的容量ensureCapacityInternal(size + numNew);System.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;
public boolean addAll(int index, Collection<? extends E> c) { //检查是否越界 rangeCheckForAdd(index);
Object[] a = c.toArray();int numNew = a.length;//确认新容量ensureCapacityInternal(size + numNew);int numMoved = size - index;//如果移动数大于0，复制需要移动的元素到尾端if (numMoved > 0)System.arraycopy(elementData, index, elementData, index + numNew,numMoved);
//将添加的元素复制到数组相应的位置 System.arraycopy(a, 0, elementData, index, numNew); //储存元素数目增加 size += numNew; //传入的集合长度为0，则添加失败 return numNew != 0; }
<a name="qL9HW"></a>#### 4) 删除- 删除特定对象```javapublic boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;}
删除指定位置的元素```java public E remove(int index) { //位置大于size（不是容量），抛异常
rangeCheck(index);modCount++;
//获取删除的元素，用于返回
E oldValue = elementData(index);
//计算需要移动的个数
int numMoved = size - index - 1;if (numMoved > 0)//复制删除位置后面的元素，从删除的位置开始覆盖，此时 最后一个元素和倒数第二个元素相同，即elementData[size-1] = elementDAta[size - 2]System.arraycopy(elementData, index+1, elementData, index,numMoved);
//将尾端元素置为null，给gc处理
elementData[--size] = null;
//返回删除的元素
return oldValue;
} ```
删除所有```java public void clear() {
modCount++;// clear to let GC do its workfor (int i = 0; i < size; i++)elementData[i] = null;size = 0;
} ```
批量删除
- 会删除原集合和传入的集合相同的元素 ```java public boolean removeAll(Collection<?> c) { //判空 Objects.requireNonNull(c); return batchRemove(c, false); }
private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; //r表示遍历原数组的当前下标， w表示批量删除后，数组剩下的元素个数 int r = 0, w = 0; boolean modified = false; try { //遍历数组，比较原数组和c的元素，删去所有相同的元素，将原数组有的而c中没有的元素放回原来的数组 for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { //如果遍历出错，则r ！= size为true // 此时elementData[r]以及之后的元素都没有遍历，没有处理，而elementData[0] ~ elementData[w-1] 则是目前为止已经处理过了的，不需要删除的元素 // 所以将elementData[r]以及之后的元素复制移动到elementData[w] if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } // 如果原数组有元素删除，则w ！= size为true // 此时 elementData[0] ~ elementData[w-1]是处理后最终的无需删除的元素 if (w != size) { // 将elementData[w]以及之后的元素置为null，交给gc处理 for (int i = w; i < size; i++) elementData[i] = null; //操作数加上 删除的元素个数 modCount += size - w; size = w; modified = true; } } return modified; }
<a name="MvCuS"></a>#### 5) 改- 不修改modCount- 相对增删更为高效```javapublic E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}
6) 查
- 不修改modCount
- 相对增删高效
public E get(int index) {rangeCheck(index);return elementData(index);}@SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}
LinkedList
基本介绍
- 实现接口： List、Deque
可以作为双端队列、Cloneable、Serializeble - 未实现RandomAcess，随机访问元素较慢
- 底层是链表，增删移动指针，效率较高，无需扩容，空间效率高
- 时间效率低，会根据index判断目标Node在前半段还是后半段，然后决定是顺序还是逆序查询，以提升时间效率。不过随着n的增大，总体时间效率依然很低。
- 增删修改modCount
1) 成员变量
transient int size = 0;//头节点//(first == null && last == null) ||(first.prev == null && first.item != null) 始终是正确的//也就是，头节点有两种情况//第一，链表未储存元素，头节点为null//第二，链表有储存元素，头节点储存的内容不为null，其指向的前结点一定为nulltransient Node<E> first;//尾结点//(first == null && last == null) || (last.next == null && last.item != null)始终是正确的//第一，链表未储存元素，尾节点为null//第二，链表有储存元素，尾节点储存的内容不为null，其指向的后结点一定为nulltransient Node<E> last;
2）构造方法
无参
java public LinkedList() { }有参
- 确认插入结点的前一个结点和后一个结点
- 新建结点（此时已经建立了新结点单方面对prev的联系）
- 建立prev与新结点的关系，并使prev指向新结点
- 所有结点创建后，再建立最后一个插入的结点与succ双方的关系 ```java public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
public boolean addAll(Collection<? extends E> c) { //从尾端开始插入元素 return addAll(size, c); }
/*
index为插入的起始位置 */ public boolean addAll(int index, Collection<? extends E> c) { //检查越界
checkPositionIndex(index);
//与ArrayList一样，在传入集合进行初始化之前，要判断是否为null
Object[] a = c.toArray();
//添加的元素个数
int numNew = a.length;if (numNew == 0)return false;
//初始的pred为插入的第一个结点的first结点，会随着元素的插入不断后移，即 index.pre = pred //succ为插入的最后一个结点指向的next结点，即 lastIndex.next = succ
Node<E> pred, succ;
//如果从尾端插入 //插入的最后一个的结点是链表的尾结点，而链表尾结点必有 last.next= null，则succ = null //第一个插入的结点的前一个结点是尾结点，即 pred = last
if (index == size) {succ = null;pred = last;} else {//succ为插入位置的next结点succ = node(index);pred = succ.prev;}
//遍历集合，将其插入链表相应的位置
for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;//新建结点储存元素， 前面指向pred结点，后面指向nullNode<E> newNode = new Node<>(pred, e, null);if (pred == null)//从头开始插入结点时，新建的第一个结点就是头结点first = newNode;else//使 pred后面指向新结点pred.next = newNode;// 插入完成后，pred总是指向最后一个插入的结点pred = newNode;}
//succ == null 即尾端插入，此时链表的尾结点是最后一个新结点
if (succ == null) {last = pred;} else {pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;
}
```java//不属于尾端插入结点时，返回index指向的结点Node<E> node(int index) {//优化查询，如果插入位置在链表的前半部分，从前往后找//插入位置在链表的后半部分，从后往前找if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}}
3) 增
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;elsel.next = newNode;size++;modCount++;}
public void add(int index, E element) {checkPositionIndex(index);//尾端插入if (index == size)linkLast(element);elselinkBefore(element, node(index));}void linkBefore(E e, Node<E> succ) {//不是尾端插入， succ一定不为nullfinal Node<E> pred = succ.prev;//新建结点已经单方面建立起与pred、succ的关系final Node<E> newNode = new Node<>(pred, e, succ);//建立succ与newNode的关系succ.prev = newNode;//建立pred与newNode的关系if (pred == null)first = newNode;elsepred.next = newNode;size++;modCount++;}
4) 删
public boolean remove(Object o) {if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null) {unlink(x);return true;}}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) {unlink(x);return true;}}}return false;}/***传入要删除的结点*/E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;final Node<E> 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;}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//清空所有
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
ArrayList与LinkedList区别
1) 增加元素到尾端
- ArrayList：
- 容量够大时，直接使用add()操作，效率高
- 容量需求超过当前数组大小时，会调用System.arraycopy()方法扩容进行数组复制，效率也是挺高的> System.arraycopy 为 Native 层的方法，可以高效复制数组元素。
- LinkedList：不需要维护容量大小，但每次增加元素都需要新建结点，性能较低
2）插入元素到列表任意位置
- ArrayList：数组是一块连续的内存空间，每次插入元素都会进行一次数组复制，大量复制导致系统性能下降
- LinkedList：此时任意位置插入与在尾端增加是一样的
- 这种情况下选择LinkedList更好
3）删除任意位置元素
- ArrayList：每次remove()都需要进行数组重组，删除的元素位置越靠前开销越大
- LinkedList：首先通过循环找到要删除的元素。效率很低
- 删除的元素位置处于List前半段就从前往后找；
- 处于后半段，从后往前找
- 处于中间，会遍历完半个List
4）容量参数
- 是ArrayList和Vector等基于数组的List的特有性能参数，表示初始数组的大小
ArrayList默认初始大小10 - 合理设置容量参数，能减少数组扩容，提升系统性能
5）遍历数组
使用for循环随机遍历列表，ArrayList速度很快，但LinkedList则表现不佳，对LinkedList随机访问，总会进行一次列表的遍历操作
2. Map
HashMap
1.基本介绍
实现java.util.Map接口的实现类主要有4个
- HashMap:具有很快的访问速度，遍历顺序不确定，线程不安全
- LinkedHashMap：是HashMap的一个子类，保存了记录的插入顺序
HashTable:遗留类，功能与HahMap相似，但是是线程安全的，不推荐使用。
ConcurrentHashMap使用分段锁，并发性能大于HashTable，需要线程安全就使用ConcurrentHashMap
TreeMap:实现SortedMap接口，可以根据key值排序(默认升序)，可以指定排序的比较器。
key必须实现Comparable接口或者在构造TreeMap时传入自定义Comparator
注意：key最好是不可变对象，确保hashCode的值不会被改变
2.存储结构
数组+链表+红黑树(jdk 1.8新增)
3.成员变量
//哈希表，存储键值对
transient Node<K,V>[] table;
//集合
transient Set<Map.Entry<K,V>> entrySet;
//当前实际存储容量
transient int size;
//操作数
transient int modCount;
//扩容阈值，超过这个数就扩容
int threshold;
//负载因子，默认0.75
final float loadFactor;
容量length：即哈希表table的长度length，默认16
这里要求桶的容量必须是2^n(是合数)，是非常规设计，是为了取模及扩容时候优化 常规设计：桶的大小设计为素数(素数引起冲突的概率要小于合数引起的)
负载因子loadFactor：决定扩容阈值
0.75默认值是对时间和空间效率的平衡选择，无必要不修改
- 内存空间很多，对时间效率要求高，可以降低负载因子的值
- 内存空间紧张，对时间效率要求不高，可以增加负载因子的值，可以大于1
扩容阈值：表示当前表的阈值，当所需容量超过阈值时，进行2倍扩容(保证2的次幂)
threshold = loadFactor * length
4. 构造方法
无参构造器
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }有参构造器
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;
//在这里并没有根据用户输入的初始容量来初始化table，只是先用阈值记录
//第一次执行put操作时再初始化数组
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
//用于找出大于等于cap的最小2的幂来作为容量
//优化了jdk1.7通过循环位移的算法，使用了很巧妙的位运算减少了大容量时的很多次循环次数
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
5. 确定哈希数组索引位置
//jdk1.8
static final int hash(Object key) {
int h;
//让高位也参与运算，减少冲突，
//这里运算结束后还没有得到数组索引位置，还要在put方法中执行与运算获得下标
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//jdk1.7
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//该方法是jdk1.7才有的，jdk1.8中没有单独写成一个方法，而是放在put方法中
static int indexFor(int h, int length) {
//取模操作做了优化
return h & (length-1);
}
- 获取数组下标三步：取key的hashCode值—>高位参与运算(一次与+一次异或)—>取模运算
由于哈希表的容量length必须是2的n次幂，故，length-1的二进制必是000……111…，这样和哈希值进行与运算时，就能得到哈希值的后n位的值，也是h%length的值
6.增
public V put(K key, V value) {
// 对key的hashCode()做hash
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;
// 步骤①：tab为空则创建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步骤②：计算index，并对null做处理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步骤③：节点key存在，直接覆盖value
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);
//链表长度大于8转换为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已经存在直接覆盖value
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;
}
- 扩容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//第一次执行时，旧容量为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
//用来记录新容量，新阈值
int newCap, newThr = 0;
//不是第一次执行，table已经初始化
if (oldCap > 0) {
//当旧容量超过最大值1<<30，直接将 Integer.MAX_VALUE 作为阈值，这样以后都不会扩容
//旧容量小于最大值时，直接将旧容量翻倍获得新容量newCap
//如果newCap<最大容量并且，oldCap大于等于默认容量，旧阈值翻倍获得新阈值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
//第一次执行put操作时
//如果阈值大于0(意味着使用有参构造器传入的初始容量大于0)，则新容量为当前阈值，即传入的初始化容量
//否则，新容量为默认容量，阈值为 加载因子*容量
else if (oldThr > 0)
newCap = oldThr;
else {
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 {
//loHead指向最终放在原索引位置的链表的表头，loTail指向表尾
Node<K,V> loHead = null, loTail = null;
//hiHead指向最终放在原索引+oldCap位置的链表的表头，hiTail指向表尾
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//判断之前的哈希值的高一位是0还是1
//是0则放在原索引位置的链表表尾
//是1则放在原索引+oldCap位置的链表表尾
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;
}
- resize方法中，jdk1.8进行了优化
- 关于扩容后hash值的计算
1.7中，不断rehash计算新的位置 1.8中只需要判断高一位来确定是原索引还是原索引旧容量 省去重新计算hash值时间，并且高一位是0还是1是随机的，由本身的hash值决定，也就使得之前冲突的值尽可能分散均匀
- 关于扩容后hash值的计算
- 关于链表插入方式：
1.7中采用头插入，容易出现倒序，且并发时出现循环链表 1.8中使用尾插入法
LinkedHashMap
- HashMap + LinkedList
- map的非同步实现，同时可以用于实现LRU
1. 存储结构
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
JDK1.7使用环形双向链表，只有头结点
2. 成员变量
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
//true表示按照访问顺序迭代，false按插入顺内迭代
final boolean accessOrder;
3. 构造方法
public LinkedHashMap() {
super();
//是否基于访问顺序排序 有两种，插入排序和访问排序
accessOrder = false;
}
4. put方法
- HashMap类似，重写newNode方法
```java
Node
//添加到链表尾部LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
}linkNodeLast(p); return p;
private void linkNodeLast(LinkedHashMap.Entry
<a name="3JNzj"></a>
#### 5.访问顺序
- HashMap定义三个回调方法，由LinkedHashMap重写实现，在调用父类的put、remove方法时。会调用LinkedHashMap的这些方法
```java
//处理元素被访问后的情况
void afterNodeAccess(Node<K,V> p) { }
//处理元素插入后的情况
void afterNodeInsertion(boolean evict) { }
//处理元素被删除后的情况
void afterNodeRemoval(Node<K,V> p) { }
afterNodeRemoval:删除链表中的节点
void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; }afterNodeInsertion：插入节点后，判断是否需要删除头结点，即最久未访问元素 ```java void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;//判断是否要删除头结点，默认返回false //如果要实现LRU，就需要重写removeEldestEntry，使得在链表超过某个长度时，返回true
if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); }}
//默认返回false
protected boolean removeEldestEntry(Map.Entry
- afterNodeAccess：访问节点后，如果是基于访问顺序迭代的，就将该节点移到链表的尾端
```java
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
6. 遍历
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
//从头结点开始
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
//并发不安全
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
7. 实现LUR
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
容器排序
- 调用Collentions.sort，实际调用Arrays.sort方法
Arrays.sort
public static <T> void sort(T[] a, Comparator<? super T> c) { if (c == null) { sort(a); } else { //请求传统归并排序，jdk5就是调用该方法实现 if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); else //改进后的归并排序，对归并排序在已经反向排好序的输入O(n^2)的问题做了优化 //能够对已经正向排好序的输入减少回溯，对一会升序一会降序的输入处理较好 TimSort.sort(a, 0, a.length, c, null, 0, 0); } }TimSort.sort
- 排序长度小于32，进行不必合并的mini-TimeSort
否则，执行以下
- 将待排序数组分为minRun大小的子数组
- 如果数组大小为2的N次幂，则返回16（MIN_MERGE / 2）
- 其他情况下，逐位向右位移（即除以2），直到找到介于16和32间的一个数
- 对各子数组进行min-Timesort并记录对应的信息(下标+长度)
- 检查是否需要合并，是就进行合并
最后，对还未合并的数组进行合并 ```java static
void sort(T[] a, int lo, int hi, Comparator<? super T> c, T[] work, int workBase, int workLen) {assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
int nRemaining = hi - lo; //排序长度小于2，不必排序 if (nRemaining < 2)
return;// 排序长度小于MIN_MERGE（32）时，无需合并，执行mini-TimeSort即可 if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi, c); binarySort(a, lo, hi, lo + initRunLen, c); return;}
TimSort
ts = new TimSort<>(a, c, work, workBase, workLen); //子数组的长度 int minRun = minRunLength(nRemaining); do { //找到初始的一组升序数列(降序的进行翻转) int runLen = countRunAndMakeAscending(a, lo, hi, c); // 如果该序列长度小于minRun，将后续补足，对[lo：lo+force]进行mini-Timesort //得到[lo:lo+force]是有序的 if (runLen < minRun) { //可能最后未排序的个数不足minRun int force = nRemaining <= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen, c); runLen = force; } //入栈，记录排好序各个子数组的起始以及大小，为后续merge准备 ts.pushRun(lo, runLen); //合并检查，相邻区间能合并的先合并 ts.mergeCollapse(); // 下一个子数组的起始下标 lo += runLen; //还未排好序的个数 nRemaining -= runLen;} while (nRemaining != 0);
assert lo == hi; //还有未meage的区块，就进行合并 ts.mergeForceCollapse(); assert ts.stackSize == 1; }
- 将待排序数组分为minRun大小的子数组
//记录排序好的子数组块的起始下标及长度 private void pushRun(int runBase, int runLen) { this.runBase[stackSize] = runBase; this.runLen[stackSize] = runLen; stackSize++; }
<a name="8uepP"></a>
### `mini-TimeSort`过程
```java
if (nRemaining < MIN_MERGE) {
//从数组开始找到连续升序或降序(进行翻转)的序列长度
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
//二分查找将后续的数插入已经排序好的数组
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
Comparator<? super T> c) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
//降序
if (c.compare(a[runHi++], a[lo]) < 0) {
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
runHi++;
//翻转
reverseRange(a, lo, runHi);
} else {
//升序
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
runHi++;
}
return runHi - lo;
}
//对a[start:hi]中的每个元素调用二分查找在[lo:start]中找到位置并插入
private static <T> void binarySort(T[] a, int lo, int hi, int start,
Comparator<? super T> c) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
T pivot = a[start];
int left = lo;
int right = start;
assert left <= right;
while (left < right) {
int mid = (left + right) >>> 1;
if (c.compare(pivot, a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
int n = start - left;
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}
合并检查过程
//假设X Y Z为3个相邻的区块
//若区块数为2：当x长度 <= y长度，合并x y
//区块数>=3， 当x长度 <= y + z，合并x，y，直到x > y + z以及 y > z
private void mergeCollapse() {
while (stackSize > 1) {
int n = stackSize - 2;
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
if (runLen[n - 1] < runLen[n + 1])
n--;
mergeAt(n);
} else if (runLen[n] <= runLen[n + 1]) {
//如果前一个区间的长度小于当前区间长度，就进行merge
mergeAt(n);
} else {
break; // Invariant is established
}
}
}
合并过程mergeAt(i):合并i和i+1的数组
前提：i的长度小于i+1的长度
private void mergeAt(int i) { assert stackSize >= 2; assert i >= 0; assert i == stackSize - 2 || i == stackSize - 3; int base1 = runBase[i]; int len1 = runLen[i]; int base2 = runBase[i + 1]; int len2 = runLen[i + 1]; assert len1 > 0 && len2 > 0; assert base1 + len1 == base2; //更新合并后区间大小 runLen[i] = len1 + len2; if (i == stackSize - 3) { runBase[i + 1] = runBase[i + 2]; runLen[i + 1] = runLen[i + 2]; } stackSize--; //找到区间2首(最小)元素在区间1的插入位置k，此时区间1[base1：k]就是合并后的最小元素数组，无需排序 int k = gallopRight(a[base2], a, base1, len1, 0, c); assert k >= 0; //更新区间1未排序首元素下标 base1 += k; //更新区间1未排序长度 len1 -= k; if (len1 == 0) return; //找到区间1尾(最大)元素在区间2的插入位置k，此时区间2[k：结尾]就是合并后的最大元素数组，无需排序,len2表示base2-k len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c); assert len2 >= 0; if (len2 == 0) return; //到这，有a[base1]>a[base2]. 且a[base1+len1]<a[base2+len2] if (len1 <= len2) mergeLo(base1, len1, base2, len2); else mergeHi(base1, len1, base2, len2); }
迭代器
- 迭代器提供了同一个接口遍历元素
Java中，Iterator为一个接口，提供迭代的基本规则;
package java.util; public interface Iterator<E> { boolean hasNext();//判断是否存在下一个对象元素 E next();//获取下一个元素 void remove();//移除元素 }Java还提供一个Iterable接口，能返回一个迭代器。实现这个接口允许对象成为foreach语句的目标，就能通过foreach遍历底层序列
快速失败机制：当遍历集合元素时，使用迭代器，在迭代遍历元素的过程中，如果集合的结构被改变，就会抛出异常
ConcurrentModificationException防止继续遍历- 迭代器在执行操作之前都会判断expectedModCount和modCount是否相等，不等就会抛出异常
- 只有调用Iterator的remove方法才不会造成快速失败
java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改 ```java //以ArrayList的迭代器为例 private class Itr implements Iterator
{ int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such //expectedModCount在初始化前就是确定的 //当其他线程或自身执行了list.remove()，modcount就会改变，而expectedModCount不会变，就会造成错误 int expectedModCount = modCount; Itr() {}
final void checkForComodification() {
if (modCount != expectedModCount) throw new ConcurrentModificationException();}
public boolean hasNext() {
return cursor != size;}
@SuppressWarnings(“unchecked”) public E next() {
checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i];}
public void remove() {
if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; //更新expectedModCount的值 expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); }}
```
- 安全失败机制：遍历时不直接在集合内容上范文，而是先复制原有集合内容，在拷贝的集合上进行遍历
- 缺点：无法访问到修改后的内容
- java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改
若有收获，就点个赞吧
0 人点赞
