集合
ArrayList
底层是动态数组
DEFAULT_CAPACITY=10;默认大小
第一个构造方法使用提供的initialCapacity来初始化elementData数组的大小。
第二个构造方法调用第一个构造方法并传入参数10,即默认elementData数组的大小为10。
第三个构造方法则将提供的集合转成数组返回给elementData(返回若不是Object[]将调用Arrays.copyOf方法将其转为Object[])。
ensureCapacity(数组检查是否需要扩容,在添加的时候)
int newCapacity = (oldCapacity * 3)/2 + 1; //新的大小是老的1.5倍
RangeCheck (取数据的时候,检查是否越界,抛出 IndexOutOfBoundsException 异常)
private void RangeCheck(int index) {
if (index >= size) throw new IndexOutOfBoundsException( "Index: "+index+", Size: "+size); }
HashMap源码
多线程使用HashMap的死循环问题
在并发的情况,发生扩容时,可能会产生循环链表,在执行get的时候,会触发死循环,引起CPU的100%问题,所以一定要避免在并发环境下使用HashMap。
获取线性安全的Map map = Collections.synchronizedMap(newHashMap());
默认大小是16
transient Entry[] table;//存储元素的实体数组 transient
int size;//存放元素的个数
int threshold; //临界值 当实际大小超过临界值时,会进行扩容
threshold = 加载因子*容量
final float loadFactor; //加载因子 0.75
transient int modCount;//被修改的次数
HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同,底层是数据跟链表的形式
loadFactor :加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。
存储数据
public V put(K key, V value) {
// 若“key为null”,则将该键值对添加到table[0]中。if(key ==null)
return putForNullKey(value);
// 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。int hash = hash(key.hashCode());
//搜索指定hash值在对应table中的索引 int i = indexFor(hash, table.length);
// 循环遍历Entry数组,若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!
for(Entry e = table[i]; e !=null; e = e.next) {
Object k;
if(e.hash == hash && ((k = e.key) == key || key.equals(k))) {//如果key相同则覆盖并返回旧值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
//修改次数+1modCount++;
//将key-value添加到table[i]处
addEntry(hash, key, value, i);
return null;}