20201008 王维

学习总结

1. java.util.LinkedList

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable

LinkedList 的直接父类是 AbstractSequentialList ,实现了 ListDeque

LinkedList 是一个双向链表,允许存储 null ,此实现不同步(非线程安全的)

方法名 返回值 描述
addFirst(E e) void 在该列表开头插入指定的元素
addLast(E e) void 将指定的元素追加到此列表的末尾/ add()
get(int index) E 返回此列表中指定位置的元素
getFirst() E 返回此列表中的第一个元素
getLast() E 返回此列表中的最后一个元素
push(E e) void 列表的前面插入元素/ addFirst()
removeFirst() E 从此列表中删除并返回第一个元素/ poll() / pollFirst() / pop()

ArrayList集合采用了和数组相同的存储方式,在内存中分配连续的空间,因此在添加和删除非尾部元素是会导致后面所有元素的移动,这就造成在插入、删除的效率低下。LinkedList采用链表存储方式存储数据,有点就在于插入、删除元素时效率比较高,但是查找效率低

比较 ArrayList / LinkedList

同:都实现了 List 接口,都是有序的、可以重复的、可以存null值得集合

异:ArrayList 在随机访问(获取元素时)效率比 LinkedList 高

在添加元素到末尾时,两个集合效率差不多

在任意位置添加元素时, LinkedList 效率更高

在任意位置删除元素时, LinkedList 效率高

内存, ArrayList 使用的是连续空间。

推荐优先使用 ArrayList

2. java.util.Map

Map 接口不是 Collection 的子类,使用键、值映射表来存储

public interface Map<K,V>

Map 不能有重复的键(覆盖),每个键可以映射到最多一个值

允许将映射内容视为一组键,值集合或键值映射集合

key 不要求有序, value 也不要求有序,但可以重复

当使用对象作为 key 时,要重写 equals 和 hashCode 方法

抽象方法:

方法 返回值 描述
clear() void 删除所有的映射
containsKey(Object key) boolean Map 中是有没有这个 key
containsValue(Object value) boolean Map 有没有这个 value
entrySet() Set<Map.Entry<K,V>> 返回包含的映射的 Set
get(Object key) V 根据 key 返回对应的 value
isEmpty() boolean Map 是不是空的
keySet() Set<K> 返回 Map 中所有 keySet
put(K key, V value) V Map 添加映射
putAll(Map m) void 将指定 Map 中的映射复制到此映射
remove(Object key) V 如果 key 存在,删除映射
remove(Object key, Object value) boolean keyvalue 映射存在时,删除
replace(K key, V value) boolean key 存在时,替换内容
size() int Map 中映射的数量
values() Collection 返回所有 value 的集合

Map 的实现类较多,在此我们关注 HashMapTreeMapHashTableLinkedHashMap

2.1 TreeMap

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable

继承 AbstractMap ,一个红黑树基于 NavigableMap 实现

非线程安全的

key 不能存 null ,但是 value 可以存 null

key必须是可比较的

2.2 Hashtable

public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, Serializable

该类实现了一个哈希表,它将键映射到值

不允许 null 作为键和值

初始容量( initialCapacity )为 11 ,负载因子( loadFactor )为 0.75f

线程安全的

不保证顺序

扩容方式是旧容量的2倍 +1

数组 + 链表

2.3 HashMap

public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

基于哈希表的实现的 Map 接口

允许 null 的值和 null

非线程安全 初始容量 16,负载因子 0.75

扩容是 2倍旧的容量

HashMap 类大致相当于 Hashtable ,除了它是不同步的,并允许null

内部采用 数组 + 链表实现 , JDK 8 及以后版本增加红黑树的支持。

HashMap 的 put 过程:

存储时,根据内部的 hash 方法计算 key ,来确定 value 的存储位置( Map 的桶bucket),如果 hash 相 同,在计算下标。如果产生没有碰撞( key 不相同),直接放到桶中,由于 hash 相同,所以放到一个桶 中。放的时候,如果没有超过阈值,以链表的形式放到后边,长度超过阈值将链表转换成红黑树存储。如果产生碰撞(节点已经存在)就替换值。

心得体会

今天又涉及到了一个新的数据结构,对于他的一些常用知识,不知道的很多,对Map集合的理解需要再多下功夫。还有各个集合的联系,区别,也是需要多下功夫的地方。

标签

评论

© 2021 成都云创动力科技有限公司 蜀ICP备20006351号-1