文章目录
ArrayList的扩容机制
- 使用无参的构造方法初始的ArrayList的初始值为0
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
-
ArrayList（int a）会使用指定容量的大小
-
ArryList（Collection<？extends E> c）会还是用c的大小作为数组容量
-
add(object o)首次扩容为10，再次扩容为上次容器的1.5倍 使用移位计算
15 —>1111 移位移位 15>>111=7 原始容量15+7=22
-
addAll(Collection c)没有元素时候，扩容为Math.max(10，实际元素个数)，
有元素时候Math.max(原始容量1.5倍，实际个数)
fail-fast fail-soft
fail-fast 一旦发现遍历的同时有人来修改他，则立即抛出异常
fail-soft 发现遍历的同时如果其他人来修改，应当能有对应的策略，例如牺牲一致性来让整个遍历运行
fali-fast ArrayList主要代表
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
// moudCount是初始List的大小
int expectedModCount = modCount;
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];
}
//此方法判断List的大小是否发生改变，如果发生了改变则抛出并发修改异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
fail-soft copyOnWriteArrayList是fail-safe的典型代表，遍历的同时可以修改，原理是读写分离
如果对数据遍历时进行了更改，进行遍历和最后的数组不是同一个数组，因此可以安全的遍历完成
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
final Object[] getArray() {
return array;
}
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//核心
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
ArrayList 和 LinkList
！！！ 千万不能说 ArrayList查找快，增删慢 是指随机访问快，如果要根据元素内容进行查找，则还是O（n）
ArrayList
-
基于数组，需要连续内存
-
随机访问快（根据下表访问）
-
尾部删除性能可以，其他部分插入，删除都会移动数据，性能很低
-
可以利用CPU缓存，局部性原理
LinkedList
- 基于双向链表，无序连续内存
- 随机访问慢，需要（沿着链表遍历）
- 头部删除删除性能高,中间的插入性能不高，因为需要定位元素
- 占用内存多（头指针，尾指针）
RandomAccess
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList实现了RandomAccess的接口，证明可以实现随机访问，但RandomAcces的接口中什么都没有写，原因是在类加载时候会根据是否实现此接口来判断访问的方法（根据下标随机访问/根据next的地址访问）
* <pre>
* for (int i=0, n=list.size(); i < n; i++)
* list.get(i);
* </pre>
*
* <pre>
* for (Iterator i=list.iterator(); i.hasNext(); )
* i.next();
* </pre>
HashMap
底层数据结构 1.7和1.8
1.7是数据+链表 1.8 数组+（链表|红黑树）
Hash表的快速查找
如果的ArrayList，想要查找其中的某一个元素，需要逐一去进行比较，时间复杂度为O(n)
在HashMap，我们可以根据Hash函数快速定位到某元素的位置，时间复杂度为O（1）
链表过长的解决
固定hash= 元素hash/容量
当我们要放进去的元素的所计算的桶下表相同时，就会产生hash冲突，数组不能够存储多个元素，就改为了链表，如果链表过程，那么获得该元素的值的空间复杂度为O(n),效率较差。因此我们可以扩大容量来解决Hash冲突（超过当前长度的3/4会自动扩容），但这并不是最好的办法，存在不同元素计算所得的桶下表值相同，此时链表的长度仍然很长，那么就需要进行树化
进行树化需要满足两个条件：数组长度大于64，链表长度大于8
为什么要用红黑树，为什么一上来不树化，树化阈值为啥是8
- 红黑树用来避免DOS攻击，防止链表超长时性能下降，树化时偶然情况
- hash的查找，更新的时间复杂度是O(1)，而红黑树的查找，更新时间的复杂度是O（logn），TreeNode占用空间也比Node大，如非必要，尽量还是使用链表
- hash的值足够随机，在负载因子为0.75的情况下，长度超过8出现的概率是0.00000006，选择8就是为了让数化的几率够小
何时会退化为链表
- 在扩容时候如果拆分树的话，树元素<=6,则会退化链表
- remove树节点时，如果root，root.left，root.right，root.left.left有一个为null时，也会退化为链表
索引如何计算？
计算对象的hashCode，再进行HashMap的hash()方法进行二次哈希，最后对数组容量取模得到索引
为什么要进行二次hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
使hash的分布更加均匀，防止超长链表的产生
为什么容量是2的n次方
0&0=0 0&1=0 1&0=0 1&1=1
总结：两位同时为1，结果才为1，否则结果为0。
计算索引时，如果是2的n次幂可以使用位运算代替取模，效率更高；
扩容时候hash & 桶下标 如果为0，则元素留着原始位置，否则新位置 =hash & 桶下标 +原始容量
介绍一下Put方法流程
-
HashMap是懒惰创建数组的，首次使用才会创建数组
-
根据hash，计算索引（桶下表）
-
如果桶下标没人占用，创建Node占位返回
-
如果桶下表已经占用
已经是TreeNode走红黑树的添加或更新逻辑
是普通Node，走链表的添加或更新逻辑，如果链表超过了树化阈值，走树化逻辑
-
返回前检查是否超过了阈值，一旦超过进行扩容。（先插入，后进行复制扩容）
Put方法1.7和1.8的区别
- 链表插入节点时候，1.7是头插法，1.8是尾插法
- 1.7是大于等于阈值且没有空位的时候进行扩容，1.8是大于阈值就会扩容
- 1.8,计算hash时候做了优化，Hash分布更加均匀
加载因子为何默认是0.75
- 在空间和查询时间上取得了较好的权衡
- 大于这个值，空间节省了，但链表就会比较长吗，影响性能，查询时间慢
- 小于这个值，冲突减少了，但扩容就会更加频繁，空间占用多
key的要求
- HashMap的key可以为null，有且只有一个
- 作为key的对象，必须实现hashCode和equals方法，并且key的内容不能被修改。 如果key被修改，那么根据key查找value时，计算hash不一致，会找不到值
可以用hashcode来判断两个对象是否相等，但有时候会存在hash冲突，因此我们需要使用equals方法进行比较两个对象是否相等
String对象的hashCode()如何设计的，为啥每次都是乘31
- 目标是达到较为均匀的散列效果，使得每个hashcode足够独特
字符串中的每个字符可以表现为一个数字，称为Si 其i的范围是0-n-1
散列公式为 S0*31^n-1+S1*31^n-2+
31带入公式有很好的散列特性，并且31*h可以被优化为
31 * h - h
2^5 * h - h
h<<5 -h
