ArrayList:
ArrayList(int initialCapacity) 是ArrayList实现的比较重要的构造函数,虽然,我们不常用它,但是某认的构造函数正是调用的该带参数:initialCapacity 的构造函数来实现的。 其中参数:initialCapacity
表示我们构造的这个ArrayList列表的初始化容量是多大。如果调用默认的构造函数,则表示默认调用该参数为initialCapacity =10 的方式,来进行构建一个ArrayList列表对象。
为了更好的理解这个initialCapacity 参数的概念,我们先看看ArrayList在Sun 提供的源码中的实现方式。先看一下它的属性有哪些:
ArrayList 继承了AbstractList 我们主要看看ArrayList中的属性就可以了。
ArrayList中主要包含2个属性:
u
private transient Object elementData[];
u
private int size;
其中数组::elementData[]
是列表的实现核心属性:数组。 我们使用该数组来进行存放集合中的数据。而我们的初始化参数就是该数组构建时候的长度,即该数组的length属性就是initialCapacity 参数。
Keys:transient表示被修饰的属性不是对象持久状态的一部分,不会自动的序列化。
第2个属性:size表示列表中真实数据的存放个数。
我们再来看一下ArrayList的构造函数,加深一下ArrayList是基于数组的理解。
从源码中可以看到默认的构造函数调用的就是带参数的构造函数:
public ArrayList(int initialCapacity)
不过参数initialCapacity=10 。
我们主要看ArrayList(int initialCapacity) 这个构造函数。可以看到:
this.elementData = new
Object[initialCapacity];
我们就是使用的initialCapacity 这个参数来创建一个Object数组。而我们所有的往该集合对象中存放的数据,就是存放到了这个Object数组中去了。
我们在看看另外一个构造函数的源码:
这里,我们先看size() 方法的实现形式。它的作用即是返回size属性值的大小。然后我们再看另外一个构造函数public ArrayList(Collection c) ,该构造函数的作用是把另外一个容器对象中的元素存放到当前的List 对象中。
可以看到,首先,我们是通过调用另外一个容器对象C 的方法size()来设置当前的List对象的size属性的长度大小。
接下来,就是对elementData 数组进行初始化,初始化的大小为原先容器大小的1.1倍。最后,就是通过使用容器接口中的Object[]
toArray(Object[] a) 方法来把当前容器中的对象都存放到新的数组elementData 中。这样就完成了一个ArrayList 的建立。
可能大家会存在一个问题,那就是,我们建立的这个ArrayList 是使用数组来实现的,但是数组的长度一旦被定下来,就不能改变了。而我们在给ArrayList对象中添加元素的时候,却没有长度限制。这个时候,ArrayList 中的elementData 属性就必须存在一个需要动态的扩充容量的机制。我们看下面的代码,它描述了这个扩充机制:
这个方法的作用就是用来判断当前的数组是否需要扩容,应该扩容多少。其中属性:modCount是继承自父类,它表示当前的对象对elementData数组进行了多少次扩容,清空,移除等操作。该属性相当于是一个对于当前List 对象的一个操作记录日志号。 我们主要看下面的代码实现:
1.
首先得到当前elementData 属性的长度oldCapacity。
2.
然后通过判断oldCapacity和minCapacity参数谁大来决定是否需要扩容
n
如果minCapacity大于oldCapacity,那么我们就对当前的List对象进行扩容。扩容的的策略为:取(oldCapacity * 3)/2 + 1和minCapacity之间更大的那个。然后使用数组拷贝的方法,把以前存放的数据转移到新的数组对象中
n
如果minCapacity不大于oldCapacity那么就不进行扩容。
下面我们看看上的那个ensureCapacity方法的是如何使用的:
上的两个add方法都是往List 中添加元素。每次在添加元素的时候,我们就需要判断一下,是否需要对于当前的数组进行扩容。
我们主要看看 public boolean
add(Object o)方法,可以发现在添加一个元素到容器中的时候,首先我们会判断是否需要扩容。因为只增加一个元素,所以扩容的大小判断也就为当前的size+1来进行判断。然后,就把新添加的元素放到数组elementData中。
第二个方法public boolean addAll(Collection
c)也是同样的原理。将新的元素放到elementData数组之后。同时改变当前List 对象的size属性。
类似的List 中的其他的方法也都是基于数组进行操作的。大家有兴趣可以看看源码中的更多的实现方式。
最后我们再看看如何判断在集合中是否已经存在某一个对象的:
由源码中我们可以看到,public boolean contains(Object elem)方法是通过调用public
int indexOf(Object elem)方法来判断是否在集合中存在某个对象elem。我们看看indexOf方法的具体实现。
u
首先我们判断一下elem 对象是否为null ,如果为null的话,那么遍历数组elementData 把第一个出现null的位置返回。
u
如果elem不为null 的话,我们也是遍历数组elementData ,并通过调用elem对象的equals()方法来得到第一个相等的元素的位置。
这里我们可以发现,ArrayList中用来判断是否包含一个对象,调用的是各个对象自己实现的equals()方法。在前面的高级特性里面,我们可以知道:如果要判断一个类的一个实例对象是否等于另外一个对象,那么我们就需要自己覆写Object类的public boolean equals(Object obj) 方法。如果不覆写该方法的话,那么就会调用Object的equals()方法来进行判断。这就相当于比较两个对象的内存应用地址是否相等了。
在集合框架中,不仅仅是List,所有的集合类,如果需要判断里面是否存放了的某个对象,都是调用该对象的equals()方法来进行处理的。
HASHMAP。
因为HashMap里面使用Hash算法,所以在理解HashMap之前,我们需要先了解一下Hash算法和Hash表。
Hash,一般翻译做“散列”,也有直接音译为"哈希"的,就是把任意长度的输入(又叫做 预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能 会散列成相同的输出,而不可能从散列值来唯一的确定输入值。
说的通俗一点,Hash算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系,(每一个真实值只能有一个键值,但是一个键值可以对应多个真实值),这样可以快速在数组等里面存取数据。
看下图:
我们建立一个HashTable(哈希表),该表的长度为N,然后我们分别在该表中的格子中存放不同的元素。每个格子下面存放的元素又是以链表的方式存放元素。
u 当添加一个新的元素Entry 的时候,首先我们通过一个Hash函数计算出这个Entry元素的Hash值hashcode。通过该hashcode值,就可以直接定位出我们应该把这个Entry元素存入到Hash表的哪个格子中,如果该格子中已经存在元素了,那么只要把新的Entry元存放到这个链表中即可。
u 如果要查找一个元素Entry的时候,也同样的方式,通过Hash函数计算出这个Entry元素的Hash值hashcode。然后通过该hashcode值,就可以直接找到这个Entry是存放到哪个格子中的。接下来就对该格子存放的链表元素进行逐个的比较查找就可以了。
举一个比较简单的例子来说明这个算法的运算方式:
假定我们有一个长度为8的Hash表(可以理解为一个长度为8的数组)。在这个Hash表中存放数字:如下表
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
32
|
9
|
|
11
|
44
|
45
|
6
|
23
|
|
57
|
|
|
12
|
|
|
|
|
89
|
|
|
|
|
|
|
假定我们的Hash函数为:
Hashcode =
X%8 -------- 对8 取余数
其中X就是我们需要放入Hash表中的数字,而这个函数返回的Hashcode就是Hash码。
假定我们有下面10个数字需要依次存入到这个Hash表中:
11 , 23 , 44 , 9 , 6 ,
32 , 12 , 45 , 57 , 89
通过上面的Hash函数,我们可以得到分别对应的Hash码:
11――3
; 23――7 ;44――4 ;9――1;6――6;32――0;12――4;45――5;57――1;89――1;
计算出来的Hash码分别代表,该数字应该存放到Hash表中的哪个对应数字的格子中。如果改格子中已经有数字存在了,那么就以链表的方式将数字依次存放在该格子中,如下表:
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
32
|
9
|
|
11
|
44
|
45
|
6
|
23
|
|
57
|
|
|
12
|
|
|
|
|
89
|
|
|
|
|
|
|
Hash表和Hash算法的特点就是它的存取速度比数组差一些,但是比起单纯的链表,在查找和存储方面却要好很多。同时数组也不利于数据的重构而排序等方面的要求。
更具体的说明,读者可以参考数据结构相关方面的书籍。
简单的了解了一下Hash算法后,我们就来看看HashMap的属性有哪些:
里面最重要的3个属性:
n
transient Entry[] table: 用来存放键值对的对象Entry数组,也就是Hash表
n
transientint size:当前Map中存放的键值对的个数
n finalfloat loadFactor:负载因子,用来决定什么情况下应该对Entry进行扩容
我们Entry对象是Map接口中的一个内部接口。即是使用它来保存我们的键值对的。
我们看看这个Entry内部接口在HashMap中的实现:
通过查看源码,我们可以看到Entry类有点类似一个单向链表。其中:
final Object key 和 Object value;存放的就是我们放入Map中的键值对。
而属性Entry next;表示当前键值对的下一个键值对是哪个Entry。
接下来,我们看看HashMap的主要的构造函数:
我们主要看看public HashMap(int initialCapacity, float loadFactor)
因为,另外两个构造函数实行也是同样的方式进行构建一个HashMap 的。
该构造函数:
1.
首先是判断参数int initialCapacity和float loadFactor是否合法
2.
然后确定Hash表的初始化长度。确定的策略是:通过传进来的参数initialCapacity来找出第一个大于它的2的次方的数。比如说我们传了18这样的一个initialCapacity参数,那么真实的table数组的长度为2的5次方,即32。之所以采用这种策略来构建Hash表的长度,是因为2的次方的运算对于现代的处理器来说,可以通过一些方法得到更加好的执行效率。
3.
接下来就是得到重构因子(threshold)了,这个属性也是HashMap中的一个比较重要的属性,它表示,当Hash表中的元素被存放了多少个之后,我们就需要对该Hash表进行重构。
4.
最后就是使用得到的初始化参数capacity 来构建Hash表:Entry[] table。
下面我们看看一个键值对是如何添加到HashMap中的。
该put方法是用来添加一个键值对(key-value)到Map中,如果Map中已经存在相同的键的键值对的话,那么就把新的值覆盖老的值,并把老的值返回给方法的调用者。如果不存在一样的键,那么就返回null。我们看看方法的具体实现:
1.
首先我们判断如果key为null则使用一个常量来代替该key值,该行为在方法maskNull()终将key替换为一个非null的对象k。
2.
计算key值的Hash码:hash
3.
通过使用Hash码来定位,我们应该把当前的键值对存放到Hash表中的哪个格子中。indexFor()方法计算出的结果:i 就是Hash表(table)中的下标。
4.
然后遍历当前的Hash表中table[i]格中的链表。从中判断已否已经存在一样的键(Key)的键值对。如果存在一样的key的键,那么就用新的value覆写老的value,并把老的value返回
5.
如果遍历后发现没有存在同样的键值对,那么就增加当前键值对到Hash表中的第i个格子中的链表中。并返回null。
最后我们看看一个键值对是如何添加到各个格子中的链表中的:
我们先看void addEntry(int hash, Object key, Object value, int bucketIndex)方法,该方法的作用就用来添加一个键值对到Hash表的第bucketIndex个格子中的链表中去。这个方法作的工作就是:
1.
创建一个Entry对象用来存放键值对。
2.
添加该键值对 ---- Entry对象到链表中
3.
最后在size属性加一,并判断是否需要对当前的Hash表进行重构。如果需要就在void resize(int newCapacity)方法中进行重构。
之所以需要重构,也是基于性能考虑。大家可以考虑这样一种情况,假定我们的Hash表只有4个格子,那么我们所有的数据都是放到这4个格子中。如果存储的数据量比较大的话,例如100。这个时候,我们就会发现,在这个Hash表中的4个格子存放的4个长长的链表。而我们每次查找元素的时候,其实相当于就是遍历链表了。这种情况下,我们用这个Hash表来存取数据的性能实际上和使用链表差不多了。
但是如果我们对这个Hash表进行重构,换为使用Hash表长度为200的表来存储这100个数据,那么平均2个格子里面才会存放一个数据。这个时候我们查找的数据的速度就会非常的快。因为基本上每个格子中存放的链表都不会很长,所以我们遍历链表的次数也就很少,这样也就加快了查找速度。但是这个时候又存在了另外的一个问题。我们使用了至少200个数据的空间来存放100个数据,这样就造成至少100个数据空间的浪费。在速度和空间上面,我们需要找到一个适合自己的中间值。在HashMap中我们通过负载因子(loadFactor)来决定应该什么时候应该重构我们的Hash表,以达到比较好的性能状态。
我们再看看重构Hash表的方法:void resize(int newCapacity)是如何实现的:
它的实现方式比较简单:
1. 首先判断如果Hash表的长度已经达到最大值,那么就不进行重构了。因为这个时候Hash表的长度已经达到上限,已经没有必要重构了。
2. 然后就是构建新的Hash表
3. 把老的Hash表中的对象数据全部转移到新的Hash表newTable中,并设置新的重构因子threshold
对于HashMap中的实现原理,我们就分析到这里。大家可能会发现,HashCode的计算,是用来定位我们的键值对应该放到Hash表中哪个格子中的关键属性。而这个HashCode的计算方法是调用的各个对象自己的实现的hashCode()方法。而这个方法是在Object对象中定义的,所以我们自己定义的类如果要在集合中使用的话,就需要正确的覆写hashCode() 方法。下面就介绍一下应该如何正确覆写hashCode()方法
覆写hashCode()
在明白了HashMap具有哪些功能,以及实现原理后,了解如何写一个hashCode()方法就更有意义了。当然,在HashMap中存取一个键值对涉及到的另外一个方法为equals (),
设计hashCode()时最重要的因素就是:无论何时,对同一个对象调用hashCode()都应该生成同样的值。如果在将一个对象用put()方法添加进HashMap时产生一个hashCode()值,而用get()取出时却产生了另外一个hashCode()值,那么就无法重新取得该对象了。所以,如果你的hashCode()方法依赖于对象中易变的数据,那用户就要小心了,因为此数据发生变化时,hashCode()就会产生一个不同的hash码,相当于产生了一个不同的“键”。
此外,也不应该使hashCode()依赖于具有唯一性的对象信息,尤其是使用this的值,这只能产生很糟糕的hashCode()。因为这样做无法生成一个新的“键”,使之与put()种原始的“键值对”中的“键”相同。例如,如果我们不覆写Object的hashCode()方法,那么调用该方法的时候,就会调用Object的hashCode()方法的默认实现。Object的hashCode()方法,返回的是当前对象的内存地址。下次如果我们需要取一个一样的“键”对应的键值对的时候,我们就无法得到一样的hashCode值了。因为我们后来创建的“键”对象已经不是存入HashMap中的那个内存地址的对象了。
posted on 2009-08-14 15:22
suker 阅读(527)
评论(0) 编辑 收藏