JAVA学习记录(一)————JAVA中的集合类

时间:2022-12-02 05:33:20

JAVA学习记录(一)————JAVA中的集合类

JAVA学习记录(一)————JAVA中的集合类

这个图是总体的框架图,主要是两个接口Collection和Map都继承接口Iterator(Iterable),为了实现可以使用迭代器。Collection和Map类似平级关系。
1、这里我先学习下ArrayList和LinkedList:
ArrayList先从源码的注释看起,讲述ArrayList的特性;
》允许添加的元素为NULL
》size、get、set、isEmpty、iterator、listIterator操作都是常量时间,add是均摊时间,其他的操作都是线性时间,但是常数因子是小LlinkedList
》非同步,如果多个线程读取,至少一个线程进行结构上的修改(add、remove、显式修改数组大小),需要同步,可以使用Collections.synchronizedList(list)把其包装为同步对象。
》快速失败:如果使用迭代器列表后(Iterator iteratoList=arrayList.iterator();)这一步初始化创建new Itr时,就已经把赋值expectModCount=modCount,如果在遍历结束之前,对原始list进行任何结构上的修改,都将会抛出ConcurrentModificationException异常,这是因为使用next时,都会先检查(checkForComodification()检查modCount记录结构别修改的次数是否与迭代前的期望一样)是否已经发生结构上的修改。(除非使用iterator或者listiterator自带方法add和remove因为自带方法实现了expectedModCount = ArrayList.this.modCount;两者值相等)。但这个特性只能用于测试程序中的bug,而不能验证程序的正确性。这个值没有进行同步或可见性操作因此也是不一定可靠:修改后也可能没有即时发现,真正防止修改应该是对那些操作加锁。
下面进入源码:
ArrayList继承了抽象类AbstractList,实现了接口list、cloneable(通过源码发现,使用的应该是浅克隆,如果数据元素是对象,则并没有进行clone)等。
ArrayList底层实现是一个object数组,当创建一个对象时,如果没有指定大小,那么默认数组大小为0(指向空数组),当添加一个元素后,使用默认值10来作为初始大小。
容量增长最终是通过grow()方法来增长,在1.7中是newCapacity = oldCapacity + (oldCapacity >> 1);(8+4;9+4 )即小于等于1.5倍.
通过两个内部类Itr、ListItr来实现迭代。
LinkedList先从源码的注释看起,讲述LinkedList的特性;
》继承了抽象类AbstractSequenceList,实现了接口List、Deque、Cloneable(浅克隆)等。允许添加元素为NULL
》双向链表操作,插入特定下标位置元素,需要从头或者尾部开始遍历。
》非同步的,如果是多个线程访问和至少一个线程进行结构上修改,则需要同步。同步最好在创建的时候就进行同步,比如Collections.synchronizedList(new LinkedList())包装成同步对象。
》同样在使用iterator和listinterator方法的时候,如果已创建了迭代对象,指向原来的对象且值expectedModCount值被赋予LinkedList域modCount,那么在迭代结束期间如果有线程对LinkedList对象结构上进行了修改,那么也会抛出ConcurrentModificationException异常,即即时失败。
下面进入源码:
继承了抽象类AbstractSequenceList,实现了接口List、Deque、Cloneable(浅克隆)等。
底层实现是通过内部Node类来实现双向链表结构,first指向链表头节点,last指向链表尾节点。
同样是通过内部类ListItr继承接口Iterator来实现迭代功能。
可以被用作栈或者队列
ArrayList与LinkedList的相同与区别:
相同点:
都是线程不安全的、继承了接口list、serializable、cloneable接口,可以进行迭代访问,同时支持快速失败。
区别:
它们之间的区别主要是它们的底层实现原理不同造成的:
AllayList因为底层是数组来实现的,因此在查找元素的时候,是十分快速的,当然这个优点也变成了其缺点,当要插入(删除)元素的时候,就需要移动后面的元素,同时当插入数量查过现有的容量时会以接近1.5倍的因子扩容,同时要复制数组,因此开销比较大。如果没有指定大小,默认数组大小为10。
LinkedList因为底层实现是利用双向链表来实现,所以对于查找某个元素,是从就近的头或者尾节点开始遍历,相对来说,查找速率比较慢,但是对于插入和删除元素的时候,由于不需要移动元素,只需要修改指针,因此速度比较快。由于使用链表,默认为空,只有添加元素才会出现元素节点。
2、学习下HashSet和TreeSet:
从HashSet源码的注释看起,讲述HashSet的特性:
》实现了Set接口,底层是实现是HashMap,不保证有序,且添加元素可以为NULL
》基础操作add、remove、size、contains常量时间,迭代时间是HashSet的size+HashMap的capacity(因此初始化时capacity不能太大或太小)。
》非同步的,如果多个线程并发访问,至少一个线程进行修改,则必须进行同步:Collections.synchronizedSet(new HashSet());
》同样支持快速失败,性质与上面集合一样。
下面进入源码
HashSet继承了AbstractSet,实现了接口Set、Cloneable(浅克隆)等,内部是以HashMap作为底层存储结构,因此很多方法都是调用map的方法。
HashSet默认无参构造方法调用HashMap的构造方法(初始大小16,参数因子是0.75),HashSet的值是作为底层HashMap的Key,因此这也是不允许重复的,同时value是一个空的Object对象。如果使用add添加重复数据是会返回false(失败)。而它也是无序(准确说不保证顺序),位置可能会变或者根据不能预测位置。
从TreeSet的源码的注释看起,讲述TreeSet的特性:
》实现了基于TreeMap的NavigableSet接口,元素的排序是根据他们的自然排序或者实现的比较器接口进行排序。
》add、remove、contains方法操作时间是logn
》由于Set接口规范是按照equals方法来比较的,如果按照Set接口规范,就要与equals方法一致。但TreeSet实例使用它的compareTo方法执行所有元素比较,所以如果比较的方法实现中出现了相等就认为相等(比如两个不同对象只有属性年龄一样,如果比较方法是按照年龄来比较,那么相等就会返回0)。按照Set的方法相等就不能插入,所以要修改,比如相等就返回1,而不是0。
》非同步,并发访问修改可以使用包装:Collections.synchronizedSortedSet(new TreeSet())
》快速失败,一其他集合一样特性。
下面进入源码
TreeSet继承了AbstractSet,实现了接口NavigableSet(并没有直接实现Set),Cloneable(浅克隆)
TreeSet的底层实现是treeMap,方法跟多也是直接调用原本方法,同样是使用Map所以也是值作为map的key来使用,而value是一个占位的object对象。TreeSet是SortedSet接口的唯一实现类,TreeSet可以确保集合元素处于排序状态。
TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false,或者通过CompareTo方法比较没有返回0。
如果我们将两个对象的equals方法总是返回true,则这两个对象的compareTo方法返回应该返回0。插入的元素不能是NULL,否则无法比较,抛出空指针异常。
相同点:
元素不可重复,非同步,但都可以使用类库包装成线程安全类。都支持快速失败。
不同点:
底层数据结构不一样:HashSet底层结构是HashMap,TreeSet底层实现是treeMap
add、remove、contains操作中HashSet时间复杂度为常量,而TreeSet需要logn
HashSet的数据是无序的,TreeSet中的数据是排好序的
保证唯一性不同:HashSet的唯一性是通过HashCode和equals方法来保证;Treeset则是通过实现comparable或者利用comparator来比较,返回0则表示相等(则属于向重复元素,适当的修改可以实现插入重复元素)
HashSet可以插入一个NULL,但TreeSet不允许
根据特性可以看出如果需要排好序的结构,且不是很频繁变化的可以使用TreeSet。但最常用的就是hashSet,通常性能优于TreeSet。
3、学习下HashMap与TreeMap
HashMap从源码注释看起,讲述HashMap的特性
》基于Hash Table实现,允许key和value值为NULL。与Hashtable大致上相等,除了在非同步和允许为null。不保证有序,随着时间变化,不保证顺序不会变
》基本操作get和put时间为常量时间,迭代遍历集合需要花费代价:Map的capacity加上map的size
》HashMap主要有两个重要参数:capacity和load factor。capacity是HashMap的创建时桶的数量,load factor是权重因子,当前容量乘以权重因子值小于需要扩充的数量时,进行扩容,并且是原来的容量的两倍。
》load factor默认值是0.75,这是一个在时间和空间的平衡,如果值过高,则会造成时间上浪费,如果值过低,则会造成重新进行hash计算分配造成时间上的开销。
》如果有很多元素需要放进去,如果是按照系统自动增长的来扩容,则不如一开始创建一个满足的容量来进行放入原来效率好
》非同步,如果有多个线程进行访问和至少一个线程进行修改,则需要进行同步,可以使用类库工具类来进行包装:Collections.synchronizedMap(new HashMap())
》使用Iterator进行迭代时,支持快速失败,当遍历对象一旦被创建,如果期间有结构上的修改则会抛出异常:ConcurrentModificationException,但如果使用Iterator自带的方法remove的方法除外
》快速失败只能被用于来发现bug,不能被用于正确的程序
下面进入源码
HashMap继承了抽象类AbstractMap,实现了Map接口和cloneable(浅克隆)接口等。
默认初始容量是16,权重因子是0.75,内部元素是内部类Entry数组,Entry包含K、V、hash值和Next对象指针。
当key值为字符串,并且hashSeed不为0时(默认为0),会调用sun.misc.Hashing.stringHash32((String) k)来计算hash值,否则则会调用对象自己的hashcode方法基础上进行hash计算,key如果为NULL,则hash值永远为0。
容量必须是2的n次方,
get方法如果参数key为NULL,则会进行专门查找(hash值为0;table[0]),返回NULL有两种情况,要么值为NULL,要么HashMap的size为0;
put方法如果传入的参数key已经存在,那么再次放入将会把原来的值给替换,同时返回原来的value。如果不存在则会返回NULL(或者key不存在或者key对应的原来的值为NULL)
如果如果扩容,则最终通过transfer来进行扩容,重新计算hash值,并进行分配位置。
TreeMap从源码注释看起,讲述TreeMap的特性:
》TreeMap是基于红黑树的算法实现,并且排序标准是根据comparable(实现改接口的方法compareTo(参数为1个))或comparator(实现方法compare(两个比较的参数))的接口实现来进行排序具体使用详情参考。
》该集合可以实现在logn的时间里完成containsKey、put、remove、get操作
》集合的顺序是依靠tree map来进行维护的,不论是否显示实现比较接口,如果要正确实现Map接口,那么就需要保持比较器实现与equlas方法一致,这是因为Map是依靠equals方法来实现比较相等,而sorted map判断比较则是根据compareTo或者compare方法来实现的,sorted map这种实现对于排序Map来说是很符合的规范,只不过是违背了Map的规范
》非同步的,如果多个线程都并发访问和至少一个线程进行结构上的修改,则都需要进行额外的同步,同步可以通过类库进行包装:Collections.synchronizedSortedMap(new TreeMap())
》快速失败 当进行迭代的时候,一旦迭代对象(复制一份)被创建,在迭代结束期间,如果集合有任何结构上的修改,都会对抛出异常ConcurrentModificationException,除了使用iterator自带的remove方法。
》同样快速失败只能用于去寻找bug,并不能用于真正的正确代码。
》Map.Entry返回的都是当前时间的快照,不能使用Map.setValue来进行改变映射,但可以使用put进行改变映射。
下面进入源码
TreeMap继承了抽象类AbstractMap,实现了接口NavigableMap、cloneable(浅克隆)等。
内部有一个比较器comparator,如果参数有则可以直接用,没有则用户实现comparable接口也可以。
内部通过实现类Entry(实现接口Map.Entry)来来作为树的节点包含K key; V value;Entry
---------------------
作者:深山里的天空
来源:CSDN
原文:https://blog.csdn.net/qq_26564827/article/details/80853769