达内java培训--Java集合体系结构分析与比.doc

达内java培训--Java集合体系结构分析与比较

1. Java集合框架图
Java平台提供了一个全新的集合框架.“集合框架”主要由一组用来操作对象的接口组成.不同接口描述一组不同数据类型.
Java集合框架图如下:
集合接口:6个接口(短虚线表示),表示不同集合类型,是集合框架的基础.
抽象类:5个抽象类(长虚线表示),对集合接口的部分实现.可扩展为自定义集合类.
实现类:8个实现类(实线表示),对接口的具体实现.
在很大程度上,一旦您理解了接口,您就理解了框架.虽然您总要创建接口特定的实现,但访问实际集合的方法应该限制在接口方法的使用上;因此,允许您更改基本的数据结构而不必改变其它代码.
Java集合的顶层接口是Collection,Collection 接口是一组允许重复的对象.Java集合框架主要由以下三个接口组成:
(1) Set 接口继承Collection,但不允许重复,使用自己内部的一个排列机制.
(2) List 接口继承Collection,允许重复,以元素安插的次序来放置元素,不会重新排列.
(3) Map接口是一组成对的键-值对象,即所持有的是key-value pairs.Map中不能有重复的key,拥有自己的内部排列机制.
容器中的元素类型都为Object,从容器取得元素时,必须把它转换成原来的类型.简化后的集合框架图如下:
2. 接口Collection
用于表示任何对象或元素组,想要尽可能以常规方式处理一组元素时,就使用这一接口.
(1) 单元素添加、删除操作:
boolean add(Object o):将对象添加给集合
boolean remove(Object o): 如果集合中有与o相匹配的对象,则删除对象o
(2) 查询操作:
int size():返回当前集合中元素的数量
boolean isEmpty():判断集合中是否有任何元素
boolean contains(Object o):查找集合中是否含有对象o
Iterator iterator():返回一个迭代器,用来访问集合中的各个元素
(3) 组操作:作用于元素组或整个集合
boolean containsAll(Collection c): 查找集合中是否含有集合c 中所有元素
boolean addAll(Collection c) : 将集合c 中所有元素添加给该集合
void clear(): 删除集合中所有元素
void removeAll(Collection c) : 从集合中删除集合c 中的所有元素
void retainAll(Collection c) : 从集合中删除集合c 中不包含的元素
(4) Collection转换为Object数组:
Object[] toArray():返回一个内含集合所有元素的array
Object[] toArray(Object[] a):返回一个内含集合所有元素的array.运行期返回的array和参数a的型别相同,需要转换为正确型别.
此外,您还可以把集合转换成其它任何其它的对象数组.但是,您不能直接把集合转换成基本数据类型的数组,因为集合必须持有对象.
斜体接口方法是可选的.因为一个接口实现必须实现所有接口方法,调用程序就需要一种途径来知道一个可选的方法是不是不受支持.如果调用一种可选方法时,一个 UnsupportedOperationException 被抛出,则操作失败,因为方法不受支持.此异常类继承 RuntimeException 类,避免了将所有集合操作放入 try-catch 块.
Collection不提供get()方法.如果要遍历Collectin中的元素,就必须用Iterator.
2.1 抽象类AbstractCollection
AbstractCollection 类提供具体“集合框架”类的基本功能.虽然您可以自行实现 Collection 接口的所有方法,但是,除了iterator()和size()方法在恰当的子类中实现以外,其它所有方法都由 AbstractCollection 类来提供实现.如果子类不覆盖某些方法,可选的如add()之类的方法将抛出异常.
2.2 接口Iterator
Collection 接口的iterator()方法返回一个 Iterator.Iterator接口方法能以迭代方式逐个访问集合中各个元素,并安全的从Collection 中除去适当的元素.
(1) boolean hasNext(): 判断是否存在另一个可访问的元素
Object next(): 返回要访问的下一个元素.如果到达集合结尾,则抛出NoSuchElementException异常.
(2) void remove(): 删除上次访问返回的对象.本方法必须紧跟在一个元素的访问后执行.如果上次访问后集合已被修改,方法将抛出IllegalStateException.
Iterator中删除操作对底层Collection也有影响.
迭代器是故障快速修复(fail-fast)的.这意味着,当另一个线程修改底层集合的时候,如果您正在用 Iterator 遍历集合,那么,Iterator就会抛出 ConcurrentModificationException (一种 RuntimeException异常)异常并立刻失败.
在遍历Iterator时不能对底层Collection执行remove()操作.
3. 接口List
List 接口继承了 Collection 接口以定义一个允许重复项的有序集合.该接口不但能够对列表的一部分进行处理,还添加了面向位置的操作.
(1) 面向位置的操作包括插入某个元素或 Collection 的功能,还包括获取、除去或更改元素的功能.在 List 中搜索元素可以从列表的头部或尾部开始,如果找到元素,还将报告元素所在的位置 :
void add(int index, Object element): 在指定位置index上添加元素element
boolean addAll(int index, Collection c): 将集合c的所有元素添加到指定位置index
Object get(int index): 返回List中指定位置的元素
int indexOf(Object o): 返回第一个出现元素o的位置,否则返回-1
int lastIndexOf(Object o):返回最后一个出现元素o的位置,否则返回-1
Object remove(int index) :删除指定位置上的元素
Object set(int index, Object element):用元素element取代位置index上的元素,并且返回旧的元素
(2) List 接口不但以位置序列迭代的遍历整个列表,还能处理集合的子集:
ListIterator listIterator() : 返回一个列表迭代器,用来访问列表中的元素
ListIterator listIterator(int index) : 返回一个列表迭代器,用来从指定位置index开始访问列表中的元素
List subList(int fromIndex, int toIndex):返回从指定位置fromIndex(包含)到toIndex(不包含)范围中各个元素的列表视图
对子列表的更改(如 add()、remove() 和 set() 调用)对底层 List 也有影响.
3.1 接口ListIterator
ListIterator 接口继承 Iterator 接口以支持添加或更改底层集合中的元素,还支持双向访问.ListIterator没有当前位置,光标位于调用previous和next方法返回的值之间.一个长度为n的列表,有n+1个有效索引值:
(1) void add(Object o): 将对象o添加到当前位置的前面
void set(Object o): 用对象o替代next或previous方法访问的上一个元素.如果上次调用后列表结构被修改了,那么将抛出IllegalStateException异常.
(2) boolean hasPrevious(): 判断向后迭代时是否有元素可访问
Object previous():返回上一个对象
int nextIndex(): 返回下次调用next方法时将返回的元素的索引
int previousIndex(): 返回下次调用previous方法时将返回的元素的索引
3.2 抽象类AbstractList和AbstractSequentialList
有两个抽象的 List 实现类:AbstractList 和 AbstractSequentialList.像 AbstractSet 类一样,它们覆盖了 equals() 和 hashCode() 方法以确保两个相等的集合返回相同的哈希码.若两个列表大小相等且包含顺序相同的相同元素,则这两个列表相等.这里的 hashCode() 实现在 List 接口定义中指定,而在这里实现.
除了equals()和hashCode(),AbstractList和AbstractSequentialList实现了其余 List 方法的一部分.因为数据的随机访问和顺序访问是分别实现的,使得具体列表实现的创建更为容易.需要定义的一套方法取决于您希望支持的行为.您永远不必亲自提供的是 iterator方法的实现.
3.3 类LinkedList、ArrayList和Vector
在“集合框架”中有两种常规的 List 实现:ArrayList 和 LinkedList.使用两种 List 实现的哪一种取决于您特定的需要.如果要支持随机访问,而不必在除尾部的任何位置插入或除去元素,那么,ArrayList 提供了可选的集合.但如果,您要频繁的从列表的中间位置添加和除去元素,而只要顺序的访问列表元素,那么,LinkedList 实现更好.
ArrayList 和 LinkedList 都实现 Cloneable 接口,都提供了两个构造函数,一个无参的,一个接受另一个Collection
3.1.1 类LinkedList
LinkedList类添加了一些处理列表两端元素的方法.
(1) void addFirst(Object o): 将对象o添加到列表的开头
void addLast(Object o):将对象o添加到列表的结尾
(2) Object getFirst(): 返回列表开头的元素
Object getLast(): 返回列表结尾的元素
(3) Object removeFirst(): 删除并且返回列表开头的元素
Object removeLast():删除并且返回列表结尾的元素
(4) LinkedList(): 构建一个空的链接列表
LinkedList(Collection c): 构建一个链接列表,并且添加集合c的所有元素
使用这些新方法,您就可以轻松的把 LinkedList 当作一个堆栈、队列或其它面向端点的数据结构.
3.1.2 类ArrayList
ArrayList类封装了一个动态再分配的Object[]数组.每个ArrayList对象有一个capacity.这个capacity表示存储列表中元素的数组的容量.当元素添加到ArrayList时,它的capacity在常量时间内自动增加.
在向一个ArrayList对象添加大量元素的程序中,可使用ensureCapacity方法增加capacity.这可以减少增加重分配的数量.
(1) void ensureCapacity(int minCapacity): 将ArrayList对象容量增加minCapacity
(2) void trimToSize(): 整理ArrayList对象容量为列表当前大小.程序可使用这个操作减少ArrayList对象存储空间.
3.1.3 类Vector
Vector类似于ArrayList.从API的角度来看这两个类非常相似.Vector是同步的,这个类中的一些方法保证了Vector中的对象是线程安全的.而ArrayList则是异步的,因此ArrayList中的对象并不是线程安全的.
3.1.4 三者之间的区别
3.1.4.1 LinkedList与ArrayList的区别
ArrayList:支持随机访问,不必在除尾部的任何位置插入或除去元素.
LinkedList:频繁的从列表的中间位置添加和除去元素,而只要顺序的访问列表元素.
3.1.4.2 Vector与ArrayList的区别
(1) 同步性
Vector是同步的.这个类中的一些方法保证了Vector中的对象是线程安全的.而ArrayList则是异步的,因此ArrayList中的对象并不是线程安全的.因为同步的要求会影响执行的效率,所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择,这样可以避免由于同步带来的不必要的性能开销.
(2) 数据增长
从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象.当你向这两种类型中增加元素的时候,如果元素的数目超出了内部数组目前的长度它们都需要扩展内部数组的长度,Vector缺省情况下自动增长原来一倍的数组长度,ArrayList是原来的50%,所以最后你获得的这个集合所占的空间总是比你实际需要的要大.所以如果你要在集合中保存大量的数据那么使用Vector有一些优势,因为你可以通过设置集合的初始化大小来避免不必要的资源开销.
(3) 使用模式
在ArrayList和Vector中,从一个指定的位置(通过索引)查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的,这个时间我们用O(1)表示.但是,如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长:O(n-i),其中n代表集合中元素的个数,i代表元素增加或移除元素的索引位置.为什么会这样呢?以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作.这一切意味着什么呢?
这意味着,你只是查找特定位置的元素或只在集合的末端增加、移除元素,那么使用Vector或ArrayList都可以.如果是其他操作,你最好选择其他的集合操作类.比如,LinkList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的-O(1),但它在索引一个元素的使用却比较慢-O(i),其中i是索引的位置.使用ArrayList也很容易,因为你可以简单的使用索引来代替创建iterator对象的操作.LinkList也会为每个插入的元素创建对象,所有你要明白它也会带来额外的开销.
最后,在《Practical Java》一书中Peter Haggar建议使用一个简单的数组(Array)来代替Vector或ArrayList.尤其是对于执行效率要求高的程序更应如此.因为使用数组(Array)避免了同步、额外的方法调用和不必要的重新分配空间的操作.
4. 接口Set
Set 接口继承 Collection 接口,而且它不允许集合中存在重复项,每个具体的 Set 实现类依赖添加的对象的 equals()方法来检查独一性,因此加入Set的Object必须定义equals()方法以确保对象的唯一性.Set接口没有引入新方法,所以Set就是一个Collection,只不过其行为不同.
4.1 Hash表
Hash表是一种数据结构,用来查找对象.Hash表为每个对象计算出一个整数,称为Hash Code(哈希码).Hash表是个链接式列表的阵列.每个列表称为一个buckets(哈希表元).对象位置的计算 index = HashCode % buckets (HashCode为对象哈希码,buckets为哈希表元总数).
当你添加元素时,有时你会遇到已经填充了元素的哈希表元,这种情况称为Hash Collisions(哈希冲突).这时,你必须判断该元素是否已经存在于该哈希表中.
如果哈希码是合理地随机分布的,并且哈希表元的数量足够大,那么哈希冲突的数量就会减少.同时,你也可以通过设定一个初始的哈希表元数量来更好地控制哈希表的运行.初始哈希表元的数量为 buckets = size * 150% + 1 (size为预期元素的数量).
如果哈希表中的元素放得太满,就必须进行rehashing(再哈希).再哈希使哈希表元数增倍,并将原有的对象重新导入新的哈希表元中,而原始的哈希表元被删除.load factor(加载因子)决定何时要对哈希表进行再哈希.在Java编程语言中,加载因子默认值为0.75,默认哈希表元为101.
4.2 接口Comparable与Comparator
在“集合框架”中有两种比较接口:Comparable接口和Comparator接口.像String和Integer等Java内建类实现Comparable接口以提供一定排序方式,但这样只能实现该接口一次.对于那些没有实现Comparable接口的类、或者自定义的类,您可以通过Comparator接口来定义您自己的比较方式.
4.2.1 接口Comparable
在java.lang包中,Comparable接口适用于一个类有自然顺序的时候.假定对象集合是同一类型,该接口允许您把集合排序成自然顺序.
(1) int compareTo(Object o): 比较当前实例对象与对象o,如果位于对象o之前,返回负值,如果两个对象在排序中位置相同,则返回0,如果位于对象o后面,则返回正值
在 Java 2 SDK版本1.4中有二十四个类实现Comparable接口.下表展示了8种基本类型的自然排序.虽然一些类共享同一种自然排序,但只有相互可比的类才能排序.
类
排序
BigDecimal,BigInteger,Byte, Double,
Float,Integer,Long,Short
按数字大小排序
Character
按 Unicode 值的数字大小排序
String
按字符串中字符 Unicode 值排序
利用Comparable接口创建您自己的类的排序顺序,只是实现compareTo()方法的问题.通常就是依赖几个数据成员的自然排序.同时类也应该覆盖equals()和hashCode()以确保两个相等的对象返回同一个哈希码.
4.2.2 接口Comparator
若一个类不能用于实现java.lang.Comparable,或者您不喜欢缺省的Comparable行为并想提供自己的排序顺序(可能多种排序方式),你可以实现Comparator接口,从而定义一个比较器.
(1)int compare(Object o1, Object o2): 对两个对象o1和o2进行比较,如果o1位于o2的前面,则返回负值,如果在排序顺序中认为o1和o2是相同的,返回0,如果o1位于o2的后面,则返回正值
与Comparable相似,0返回值不表示元素相等.一个0返回值只是表示两个对象排在同一位置.由Comparator用户决定如何处理.如果两个不相等的元素比较的结果为零,您首先应该确信那就是您要的结果,然后记录行为.
(2)boolean equals(Object obj): 指示对象obj是否和比较器相等.
该方法覆写Object的equals()方法,检查的是Comparator实现的等同性,不是处于比较状态下的对象.
4.3 接口SortedSet
“集合框架”提供了个特殊的Set接口:SortedSet,它保持元素的有序顺序.SortedSet接口为集的视图(子集)和它的两端(即头和尾)提供了访问方法.当您处理列表的子集时,更改视图会反映到源集.此外,更改源集也会反映在子集上.发生这种情况的原因在于视图由两端的元素而不是下标元素指定,所以如果您想要一个特殊的高端元素
4.4 类HashSet、TreeSet和LinkedHashSet
4.4.2 类HashSet
为快速查找而设计的Set.存入HashSet的对象必须定义hashCode().生成自己的类时,Set需要维护元素的存储顺序,因此要实现Comparable接口并定义compareTo()方法.
HashSet是一个只有key的HashMap.
4.4.3 类TreeSet
保持次序的Set,底层为树结构.使用它可以从Set中提取有序的序列.
4.4.4 类LinkedHashSet
LinkedHashSet扩展HashSet,具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入的次序).于是在使用迭代器遍历Set时,迭代器按照元素的插入顺序来访问各个元素.它提供了一个可以快速访问各个元素的有序集合.同时,它也增加了实现的代价,因为哈希表元中的各个元素是通过双重链接式列表链接在一起的.
(1) LinkedHashSet(): 构建一个空的链接式哈希集
(2) LinkedHashSet(Collection c): 构建一个链接式哈希集,并且添加集合c中所有元素
(3) LinkedHashSet(int initialCapacity): 构建一个拥有特定容量的空链接式哈希集
(4) LinkedHashSet(int initialCapacity, float loadFactor): 构建一个拥有特定容量和加载因子的空链接式哈希集.LoadFactor是0.0至1.0之间的一个数.
4.4.5 三者之间的区别
(1) HashSet采用散列函数对元素进行排序,这是专门为快速查询而设计的.
(2) TreeSet采用红黑树的数据结构进行排序元素.
(3) LinkedHashSet内部使用散列以加快查询速度,同时使用链表维护元素的次序,使得看起来元素是以插入的顺序保存的.
5. 接口Map
Map接口不是Collection接口的继承.Map接口用于维护键/值对(key/value pairs).该接口描述了从不重复的键到值的映射.
(1) 添加、删除操作:
Object put(Object key, Object value): 将互相关联的一个关键字与一个值放入该映像.如果该关键字已经存在,那么与此关键字相关的新值将取代旧值.方法返回关键字的旧值,如果关键字原先并不存在,则返回null
Object remove(Object key): 从映像中删除与key相关的映射
void putAll(Map t): 将来自特定映像的所有元素添加给该映像
void clear(): 从映像中删除所有映射
键和值都可以为null.但是,您不能把Map作为一个键或值添加给自身.
(2) 查询操作:
Object get(Object key): 获得与关键字key相关的值,并且返回与关键字key相关的对象,如果没有在该映像中找到该关键字,则返回null
boolean containsKey(Object key): 判断映像中是否存在关键字key
boolean containsValue(Object value): 判断映像中是否存在值value
int size(): 返回当前映像中映射的数量
boolean isEmpty():判断映像中是否有任何映射
(3) 视图操作:处理映像中键/值对组
Set keySet(): 返回映像中所有关键字的视图集
因为映射中键的集合必须是唯一的,您用Set支持.你还可以从视图中删除元素,同时,关键字和它相关的值将从源映像中被删除,但是你不能添加任何元素.
Collection values():返回映像中所有值的视图集
因为映射中值的集合不是唯一的,您用Collection支持.你还可以从视图中删除元素,同时,值和它的关键字将从源映像中被删除,但是你不能添加任何元素.
Set entrySet(): 返回Map.Entry对象的视图集,即映像中的关键字/值对
因为映射是唯一的,您用Set支持.你还可以从视图中删除元素,同时,这些元素将从源映像中被删除,但是你不能添加任何元素.
5.1 接口Map.Entry
Map的entrySet()方法返回一个实现Map.Entry接口的对象集合.集合中每个对象都是底层Map中一个特定的键/值对.
通过这个集合的迭代器,您可以获得每一个条目(唯一获取方式)的键或值,并对值进行更改.当条目通过迭代器返回后,除非是迭代器自身的remove()方法或者迭代器返回的条目的setValue()方法,其余对源Map外部的修改都会导致此条目集变得无效,同时产生条目行为未定义.
(1) Object getKey(): 返回条目的关键字
(2) Object getValue(): 返回条目的值
(3) Object setValue(Object value): 将相关映像中的值改为value,并且返回旧值
5.2 接口SortedMap
“集合框架”提供了个特殊的Map接口:SortedMap,它用来保持键的有序顺序.
SortedMap接口为映像的视图(子集),包括两个端点提供了访问方法.除了排序是作用于映射的键以外,处理SortedMap和处理SortedSet一样.
添加到SortedMap实现类的元素必须实现Comparable接口,否则您必须给它的构造函数提供一个Comparator接口的实现.TreeMap类是它的唯一一份实现.
因为对于映射来说,每个键只能对应一个值,如果在添加一个键/值对时比较两个键产生了0返回值(通过Comparable的compareTo()方法或通过Comparator的compare()方法),那么,原始键对应值被新的值替代.如果两个元素相等,那还好.但如果不相等,那么您就应该修改比较方法,让比较方法和 equals() 的效果一致.
(1) Comparator comparator(): 返回对关键字进行排序时使用的比较器,如果使用Comparable接口的compareTo()方法对关键字进行比较,则返回null
(2) Object firstKey(): 返回映像中第一个(最低)关键字
(3) Object lastKey(): 返回映像中最后一个(最高)关键字
(4) SortedMap subMap(Object fromKey, Object toKey): 返回从fromKey(包括)至toKey(不包括)范围内元素的SortedMap视图(子集)
(5) SortedMap headMap(Object toKey): 返回SortedMap的一个视图,其内各元素的key皆小于toKey
(6) SortedSet tailMap(Object fromKey): 返回SortedMap的一个视图,其内各元素的key皆大于或等于fromKey
5.3 抽象类AbstractMap
和其它抽象集合实现相似,AbstractMap 类覆盖了equals()和hashCode()方法以确保两个相等映射返回相同的哈希码.如果两个映射大小相等、包含同样的键且每个键在这两个映射中对应的值都相同,则这两个映射相等.映射的哈希码是映射元素哈希码的总和,其中每个元素是Map.Entry接口的一个实现.因此,不论映射内部顺序如何,两个相等映射会报告相同的哈希码.
5.4 类HashMap
Map基于散列表的实现,取代了Hashtable.插入和查询label/value的开销是固定的,并且可以通过构造器设置容量和负载因子,以调整容器的性能.
使用散列的目的:想要使用一个对象来查找另一个对象.使用TreeSet或TreeMap也能实现此目的.另外,还可以自己实现一个Map,此时,必须提供Map.entrySet()方法来生成Map.Entry对象的Set.
使用散列的价值:速度,散列使得查询可以快速进行.散列将label保存在数组中方便快速查询,因为存储一组元素最快的数据结构是数组,用它来表示label的信息(后面有信息的描述),而不是label本身.通过label对象计算得到一个数字,作为数组的下标,这个数字就是散列码(即前面所述的信息).该散列码具体是通过定义在基类Object中,可能由程序员自定义的类覆盖的hashCode()方法,即散列函数生成.为了解决数组容量带来的限制,可以使不同的label生成相同的下标,保存在一个链表list中,每一个链表就是数组的一个元素.查询label时就可以通过对list中的信息进行查找,当散列函数比较好,数组的每个位置中的list长度较短,则可以快速查找到数组元素list中的某个位置,提高了整体速度.
散列表中的slot通常称为bucket,为了使散列分步均匀,bucket的值一般取质数.但事实证明,质数实际上并不是散列bucket的理想容量,近来Java散列实现都使用2的幂,具体如何验证以后再续.
为了优化HashMap空间的使用,您可以调优初始容量和负载因子.
(1) HashMap(): 构建一个空的哈希映像
(2) HashMap(Map m): 构建一个哈希映像,并且添加映像m的所有映射
(3) HashMap(int initialCapacity): 构建一个拥有特定容量的空的哈希映像
(4) HashMap(int initialCapacity, float loadFactor): 构建一个拥有特定容量和加载因子的空的哈希映像
5.4.1 hashCode()
当使用标准库中的类Integer 作为HashMap的label时,程序能够正常运行,但是使用自己创建的类作为HashMap的label时,通常犯一个错误.
在HashMap中通过label查找value时,实际上是计算label对象地址的散列码来确定value的.一般情况下,我们是使用基类Object的方法hashCode()来生成散列码,它默认是使用对象的地址来计算的,因此由第一个对象new Apple(5)和第二个对象new Apple(5)生成的散列码是不同的,不能完成正确的查找.通常,我们可以编写自己的hashCode()方法来覆盖基类的原始方法,但与此同时,我们必须同时实现equals()方法来判断当前的label是否与表中存在的label相同.
正确的equals()方法满足五个条件:
(1) 自反性.对于任意的x,x.equals(x)一定返回true.
(2) 对称性.对于任意的x和y,如果y.equals(x)返回true,则x.equals(y)也返回true.
(3) 传递性.对于任意的x、y、z,如果有x.equals(y)返回true,y.equals(z)返回true,则x.equals(z)一定返回true.
(4) 一致性.对于任意的x和y,如果对象中用于等价比较的信息没有改变,那么无论调用x.equals(y)多少次,返回的结果应该保持一致,要么一直是true,要么一直是false.
(5) 对任何不是null的x,x.equals(null)一定返回false.
Equals()比较的是对象的地址,如果要使用自己的类作为HashMap的label,必须同时重载hashCode()和equals()方法.
5.4.2 HashMap的性能因子
容量(capacity): 散列表中bucket的数量.
初始化容量(initial capacity): 创建散列表时bucket的数量.可以在构造方法中指定HashMap和HashSet的初始化容量.
尺寸(size): 散列表中记录的数量.(数组的元素个数,非list中元素总和)
负载因子(load factor): 尺寸/容量.负载因子为0,表示空的散列表,0.5表示半满的散列表.轻负载的散列表具有冲突少,适宜插入与查询的特点,但是使用迭代器遍历会比较慢.较高的负载会减少所需空间大小.当负载达到指定值时,容器会自动成倍地增加容量,并将原有的对象重新分配,存入新的bucket中,这个过程称为“重散列”.
5.4.3 重写hashCode()的关键
(1) 对同一个对象调用hashCode()都应该生成同样的值.
(2) hashCode()方法不要依赖于对象中易变的数据,当数据发生变化时,hashCode()就会生成一个不同的散列码,即产生了一个不同的label.
(3) hashCode()不应依赖于具有唯一性的对象信息,例如对象地址.
(4) 散列码应该更关心速度,而不是唯一性,因为散列码不必是唯一的.
(5) 好的hashCode()应该产生分步均匀的散列码.
5.4.4 HashMap的深度分析
HashMap可谓JDK的一大实用工具,把各个Object映射起来,实现了“键--值”对应的快速存取.但实际里面做了些什么呢?
在这之前,先介绍一下负载因子和容量的属性.大家都知道其实一个 HashMap 的实际容量等于因子*容量,其默认值是 16×0.75=12; 这个很重要,对效率很一定影响!当存入HashMap的对象超过这个容量时,HashMap 就会重新构造存取表.这就是一个大问题,我后面慢慢介绍,反正,如果你已经知道你大概要存放多少个对象,最好设为该实际容量的能接受的数字.
两个关键的方法,put和get:
先有这样一个概念,HashMap是声明了 Map,Cloneable, Serializable 接口,和继承了 AbstractMap 类,里面的 Iterator 其实主要都是其内部类HashIterator 和其他几个 iterator 类实现,当然还有一个很重要的继承了Map.Entry 的 Entry 内部类,由于大家都有源代码,大家有兴趣可以看看这部分,我主要想说明的是 Entry 内部类.它包含了hash,value,key 和next 这四个属性,很重要.put的源码如下
public Object put(Object key, Object value) {
//这个就是判断键值是否为空,如果为空,它会返回一个static Object 作为键值
//这就是为什么HashMap允许空键值的原因
Object k = maskNull(key);
/*
hash 通过 key 这个Object的 hashcode 进行 hash,然后通过 indexFor 获得在Object table的索引值.
table?不要惊讶,其实HashMap也神不到哪里去,它就是用 table 来放的.最牛的就是用 hash 能正确的返回索引.
*/
int hash = hash(k);
int i = indexFor(hash, table.length);
/*
不知道大家有没有留意 put 其实是一个有返回的方法,它会把相同键值的 put 覆盖掉并返回旧的值!如下方法彻底说明了 HashMap 的结构,其实就是一个表加上在相应位置的Entry的链表:
for (Entry e = table[i]; e != null; e = e.next) {
if (e.hash == hash && eq(k, e.key)) {
Object oldvalue = e.value;
e.value = value; //把新的值赋予给对应键值.
e.recordAcces