集合有两个分支,一是Collection 另一个是Map
Collection的子类有Set , List
List:
----arrayList 底层通过数组实现, 带索引,但是一旦改动数据就会使数据重新排序,所以优点是查询快,缺点是增删慢
-----linkedLIst 底层通过链表实现,通过下标实现排序,优缺点正好与arraylist相反
-----vector 线程安全的集合
(ArrayList 补充) : arraylist 初始长度默认是10 , 每次扩容默认扩原来的1.5倍
(linkedLIst 补充):
linkedList底层是双向链表,每一个元素都有三部分,头,中,尾 . 头指向上一个元素,尾部指向下一个元素,头指向为空的元素,就是第一个元素,尾部指向元素为空的,就是最后一个元素,
增删快的原因: 删除元素后,只需要改变上一个元素的尾部指向,跟下一个元素的头部指向,不需要移动链表
查询慢的原因: 链表要查询某个位置上的元素,需要通过下标一个个找,效率低下.
Set: hashSet底层实际就是一个HashMap,通过hashmap的key值不能重复的特点实现set的元素唯一性,map的value值存的都是new Object();
treeSet: treeSet底层就是一个treeMap;
Map
HashMap HashMap 的优点是 :结合了arraylist跟linkedList的优点,既查询快,增删也快
实现原理 : hashmap是基于哈希表实现的。如上图, map在调用put的时候,会将key的哈希码取出,将key进行算法运算后分配到entry[] 数组中相应的位置, 如:HashMap默认长度为16(当使用量达到75%时,会进行扩容到原来的两倍),索引值为hashCode%16的方式(效率最低的算法是hashCode/hashCode, 即退化成一个单向链表),当确定索引后,会将数据以链表形式存入数组,( hash|key | value | next ) , jdk8以后,当链表长度大于8,会转换为红黑树,进而增加查询效率
取数据的实现如下图
HashTable: hashTable 基本与hashMap相似,但是hashTable是线程安全的,效率较低,并且hashTable是不允许key跟value为null的
TreeMap: treeMap是基于红黑二叉树实现的,是可排序的map集合,如果是对象需要排序,对象需要实现Comparable接口,并重写 CompartTo方法实现排序
网友评论