Linkedlist,arrayDeque,HashMap,linkedHashMap

时间:2021-07-30 12:37:03

Linkedlist

1.extneds AbstractSequentialList, implements List<E>, Deque<E>, Cloneable, java.io.Serializable  ,element,peek

2.双向链表,header链表头,size大小

3.按下标访问元素—get(i)/set(i,e) 遍历链表将指针移动到位(如果i>数组大小的一半,会从末尾移起),

get set 优化后的线程时间O(n),add,remove,只需要改变指针

4.相对于arraylist需要更耗内存,创建Entry对象

ArrayDeque

1.基于动态数组实现的,双端,双端指针

HashMap

1.继承abstractMap,实现Map,Serializable,Cloneable,序列化通过,writeObject,readObject 方法实现

2.先线性安全,默认容量和加载因子16,0.75,数组resize为原来的两倍,伴随着rehash操作,支持键值null,key为null,存储在第一个bucket中

3.链表法解决哈希冲突,

4.通过modcount成员变量支持fail-fast规则,迭代器抛出ConcurrentModificationException异常

5.get put, put 根据k的hashcode值确定 数组下标,再根据k.hashcode,k比较,是否相同,相同则返回旧值,否则新增,再判断是否超过阈值,超过容量变为两倍

6.indexFor(hash, table.length)按位与 数组长度&

hashCode是native方法,对每一个不同的java环境来说,同一个key所计算的hashCode是不相同的,所以反序列化后table的index会发生变化,无法还原

HashMap的bullet存在null数据,如果对这部分数据进行序列化则造成不必要的资源浪费。

transient使用小结

  • transient关键字只能修饰变量,变量如果是用户自定义类变量,则该类需要实现Serializable接口。
  • 被transient关键字修饰的变量不再能被序列化,一个静态变量不管是否被transient修饰,均不能被序列化。

总结

    • 当父类继承Serializable接口时,所有子类都可以被序列化。
    • 子类实现了Serializable接口,父类没有,父类中的属性不能被序列化(不报错,数据不会丢失),但是在子类中的属性仍能正确序列化
    • 如果序列化的属性是对象,则这个对象也必须实现Serializable接口,否则会报错。
    • 在反序列化时,如果对象的属性有修改或删减,则修改的部分属性会丢失,但不会报错。
    • 在反序列化时,如果serialVersionUID被序列化,则反序列化时会失败
    • static,transient修饰后的变量不能被序列化

与hashTable区别

  1. HashMap非线程安全的,并可以支持键值为null,而Hashtable非线程安全的,key和value都不能为null
  2. Hashtable和HashMap默认的容量和resize方式不同。HashTable中hash数组默认大小是11,增加的方式是 old*2+1。HashMap中hash数组的默认大小是16,而且一定是2的指数。
  3. hashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器。

  HashMap可以通过下面的语句进行同步:Map m = Collections.synchronizeMap(hashMap);
  

LinkedHashMap

1.继承HashMap,实现Map接口

2.通过hash表加双向链表实现,依靠着双向链表实现迭代顺序为插入顺序或者访问顺序,倒序;LRU缓存,先线性安全

package collections;

import java.util.Map;

public class LRUCache {

    private int capacity;
private Map<Integer, Integer> cache; public LRUCache(final int capacity) {
this.capacity = capacity;
this.cache = new java.util.LinkedHashMap<Integer, Integer> (capacity, 0.75f, true) {
// 定义put后的移除规则,大于容量就删除eldest
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
};
} public int get(int key) {
if (cache.containsKey(key)) {
return cache.get(key);
} else
return -;
} public void set(int key, int value) {
cache.put(key, value);
}
}

Collections.sort()

加强型归并排序