写代码啦
Collection初体验
回复数(0) 浏览数(27)
{{topic.upvote_count || 0}} 编辑 回复

集合框架

这是从博客找的一张集合框架图片,从上向下可以看到MapCollection处于类的顶端,并且支持Iterator(迭代器)。迭代器主要用途是遍历集合中的元素,比较有趣的是遍历好手for each语句也是转换成对iterator.next()和iterator.hashNext()方法的调用,算是对Iterator语句的一种封装。迭代器和foreach中进行remove/add操作好像比较迷,暂时还没搞懂。
集合框架 集合框架

Collection

Collection有两个子类,分别是List和Set。List约定是有序且可重复,Set约定是无序且不允许重复。

List

主要说一下ArrayList,下图是ArrayList源码注释首段。大致上翻一下,值得注意的是段首的Resizable-array讲出了ArrayList的本质上是可调整大小的数组。ArrayList本身实现了List的接口,实现所有可选list操作,也允许null存在。除此之外,ArrayList还提供了可以改变内部存储元素的size的方法。它和Vector很相似,但本身存在线程不安全性。
ArrayList源码首段 ArrayList源码首段


看完源码很容易有一个问题,数组本身是不可扩容的,ArrayList是如何实现扩容的?

在你使用add()方法时,会先调用ensureCapacityInternal(size + 1)方法确定添加元素后的minCapacity值。得到minCapacity值后会进行判断现有的size和的minCapacity之间的大小关系。如果现有size不能确保加入新元素。就会进行扩容操作,具体是新建一个数组,使其size变为原本的1.5倍,再于minCapacity进行比较并取高值作为新数组容量。最后将原数组拷贝进入新数组。(旧数组就在薛定谔被删除状态)

Set

Set的约定就是不允许有重复元素且无序,判断重复使用的是equals约定。
* 如何实现set的约定呢?
按照顺序判断新加入的元素是否contains原数组,如果不,就add,否则返回。假设一组足够大的完全不重复的数组样本,判断次数就是等差数列求和,难度与样本数量是正向二次关系。
* 那么如何高效实现set的约定呢?


在此之前,我们先聊一下HashCode。

HashCode

如果说equals约定是JAVA中第一重要的约定,第二重要的就一定是HashCode。
Object是所有class的源头,其中有就有HashCode方法,即返回当前对象的一个int型的HashCode值。约定如下:
* 同一个对象必须返回同一个HashCode
* 两个对象equals返回true ,必须相同的HashCode
* 两个对象不等,也可能返回同一个HashCode
也就解释了override,equals时会连带有Hashcode方法重载。因为其本身是int型,具有最大值,而Object可能不止21亿多,所以本质是从对象到HashCode的单向映射。


再说回HashCode高效实现Set的约定的方法,首先想象有很多的hash桶,每个hash桶有自己的HashCode。对object处理前先实现HashCode方法,根据HashCode匹配hash桶,新加入的元素不需要每个对象都要比较,先去根据HashCode找hash桶,再在桶内比较。
结论就是hash桶的数量和元素总量及分布决定了HashCode算法的效率倍数,即桶数目越多,元素样本越大,分布越均匀,效率越高。

基于这个原因我们可以使用HashSet对ArrayList进行去重操作。需要注意的是,HashSet本身是无序的,如果对顺序有需求可以使用LinkedHashSet,它的顺序是元素插入顺序。

Map

MAP是从key键映射到值的映射,一个map不包含重复的key,每个键最多映射一个value。按照我的理解,和高中数学中常见X/Y坐标系中的函数很像,除了圆锥曲线,一般x作为定义域,y作为值域,一个y肯定是存在一个x映射,每个x最多只能映射一个y,不同x映射y可能相同。即x为key,y为value。

HashMap是最常用,最高效的Map实现,下图是其源码首段,试着解读有利于加深对HashMap的理解。
这是Map接口基于Hash表的实现,此实现提供所有可选的地图操作,允许存在null value和null key。HashMap和Hashtable大致相似,不同点在于HashMap允许null存在和线程不安全性。它无法保证Map其中的有序性,并且随着时间推移,现有顺序也不保证恒定不变。
HashMap源码首段 HashMap源码首段


源码中提到HashMap是无序的,其key对应的HashSet也是无序的,两者其实背后是同一组数据,也就是说对其中一个的修改就是对两个的修改。如果对顺序有需求的话,可以使用TreeMap,本身具有有序性。

另外一点就是HashMap和ArrayList都提到线程不安全性。ArrayList是线程非安全的,因为ArrayList中所有的方法都不是同步的,在并发下一定会出现安全问题。HashMap也是类似,在多线程同时使用put操作时很可能造成数据丢失,在多线程扩容resize过程中也可能条件竞争,形成死循环的链表,多线程下可使用ConcurrentHashMap。

HashMap的扩容

上面提到的resize,是用来实现HashMap的扩容。当新的元素不断加入时,Map的饱和度会慢慢升高。Key映射位置发生冲突的几率会逐渐提高。达到一定负载是,HashMap需要扩展它的长度,也就是resize。
1. 创建一个新的Entry空数组,长度是原数组的2倍
2. 遍历原Entry数组,把所有的Entry重新Hash到新数组

在Java7之前,假设不论是被攻击还是巧合,不同对象拥有相同的HashCode的数据会导致少数hash桶被绝大多数元素使用,无法高效应用其他绝大部分hash桶,会丧失hash算法带来的速度优势,类似于降维成list。

而同一Hash桶中的数据结构是链表,这种情况下会大大增加运算时间和负载。在Java7之后这种碰撞由链表结构变为红黑树,其优势就是把链表的线性运算时间变为对数时间


最后,Collection作为Java数据类型中重要的一环,其本身的方法很强大。并且有更强大的Guava可供使用,拥有更多更全面的类库,当需要一个Collection相关的方法时,不妨去其中搜索。

{{topic.upvote_count || 0}}

集合框架

这是从博客找的一张集合框架图片,从上向下可以看到MapCollection处于类的顶端,并且支持Iterator(迭代器)。迭代器主要用途是遍历集合中的元素,比较有趣的是遍历好手for each语句也是转换成对iterator.next()和iterator.hashNext()方法的调用,算是对Iterator语句的一种封装。迭代器和foreach中进行remove/add操作好像比较迷,暂时还没搞懂。
集合框架 集合框架

Collection

Collection有两个子类,分别是List和Set。List约定是有序且可重复,Set约定是无序且不允许重复。

List

主要说一下ArrayList,下图是ArrayList源码注释首段。大致上翻一下,值得注意的是段首的Resizable-array讲出了ArrayList的本质上是可调整大小的数组。ArrayList本身实现了List的接口,实现所有可选list操作,也允许null存在。除此之外,ArrayList还提供了可以改变内部存储元素的size的方法。它和Vector很相似,但本身存在线程不安全性。
ArrayList源码首段 ArrayList源码首段


看完源码很容易有一个问题,数组本身是不可扩容的,ArrayList是如何实现扩容的?

在你使用add()方法时,会先调用ensureCapacityInternal(size + 1)方法确定添加元素后的minCapacity值。得到minCapacity值后会进行判断现有的size和的minCapacity之间的大小关系。如果现有size不能确保加入新元素。就会进行扩容操作,具体是新建一个数组,使其size变为原本的1.5倍,再于minCapacity进行比较并取高值作为新数组容量。最后将原数组拷贝进入新数组。(旧数组就在薛定谔被删除状态)

Set

Set的约定就是不允许有重复元素且无序,判断重复使用的是equals约定。
* 如何实现set的约定呢?
按照顺序判断新加入的元素是否contains原数组,如果不,就add,否则返回。假设一组足够大的完全不重复的数组样本,判断次数就是等差数列求和,难度与样本数量是正向二次关系。
* 那么如何高效实现set的约定呢?


在此之前,我们先聊一下HashCode。

HashCode

如果说equals约定是JAVA中第一重要的约定,第二重要的就一定是HashCode。
Object是所有class的源头,其中有就有HashCode方法,即返回当前对象的一个int型的HashCode值。约定如下:
* 同一个对象必须返回同一个HashCode
* 两个对象equals返回true ,必须相同的HashCode
* 两个对象不等,也可能返回同一个HashCode
也就解释了override,equals时会连带有Hashcode方法重载。因为其本身是int型,具有最大值,而Object可能不止21亿多,所以本质是从对象到HashCode的单向映射。


再说回HashCode高效实现Set的约定的方法,首先想象有很多的hash桶,每个hash桶有自己的HashCode。对object处理前先实现HashCode方法,根据HashCode匹配hash桶,新加入的元素不需要每个对象都要比较,先去根据HashCode找hash桶,再在桶内比较。
结论就是hash桶的数量和元素总量及分布决定了HashCode算法的效率倍数,即桶数目越多,元素样本越大,分布越均匀,效率越高。

基于这个原因我们可以使用HashSet对ArrayList进行去重操作。需要注意的是,HashSet本身是无序的,如果对顺序有需求可以使用LinkedHashSet,它的顺序是元素插入顺序。

Map

MAP是从key键映射到值的映射,一个map不包含重复的key,每个键最多映射一个value。按照我的理解,和高中数学中常见X/Y坐标系中的函数很像,除了圆锥曲线,一般x作为定义域,y作为值域,一个y肯定是存在一个x映射,每个x最多只能映射一个y,不同x映射y可能相同。即x为key,y为value。

HashMap是最常用,最高效的Map实现,下图是其源码首段,试着解读有利于加深对HashMap的理解。
这是Map接口基于Hash表的实现,此实现提供所有可选的地图操作,允许存在null value和null key。HashMap和Hashtable大致相似,不同点在于HashMap允许null存在和线程不安全性。它无法保证Map其中的有序性,并且随着时间推移,现有顺序也不保证恒定不变。
HashMap源码首段 HashMap源码首段


源码中提到HashMap是无序的,其key对应的HashSet也是无序的,两者其实背后是同一组数据,也就是说对其中一个的修改就是对两个的修改。如果对顺序有需求的话,可以使用TreeMap,本身具有有序性。

另外一点就是HashMap和ArrayList都提到线程不安全性。ArrayList是线程非安全的,因为ArrayList中所有的方法都不是同步的,在并发下一定会出现安全问题。HashMap也是类似,在多线程同时使用put操作时很可能造成数据丢失,在多线程扩容resize过程中也可能条件竞争,形成死循环的链表,多线程下可使用ConcurrentHashMap。

HashMap的扩容

上面提到的resize,是用来实现HashMap的扩容。当新的元素不断加入时,Map的饱和度会慢慢升高。Key映射位置发生冲突的几率会逐渐提高。达到一定负载是,HashMap需要扩展它的长度,也就是resize。
1. 创建一个新的Entry空数组,长度是原数组的2倍
2. 遍历原Entry数组,把所有的Entry重新Hash到新数组

在Java7之前,假设不论是被攻击还是巧合,不同对象拥有相同的HashCode的数据会导致少数hash桶被绝大多数元素使用,无法高效应用其他绝大部分hash桶,会丧失hash算法带来的速度优势,类似于降维成list。

而同一Hash桶中的数据结构是链表,这种情况下会大大增加运算时间和负载。在Java7之后这种碰撞由链表结构变为红黑树,其优势就是把链表的线性运算时间变为对数时间


最后,Collection作为Java数据类型中重要的一环,其本身的方法很强大。并且有更强大的Guava可供使用,拥有更多更全面的类库,当需要一个Collection相关的方法时,不妨去其中搜索。

27
回复 编辑