Java集合框架及散列的深入分析

Java集合框架及散列的深入分析

Java集合框架由几个相关的组件构成：接口、抽象类以及完全定义的类，其中，每个完全定义的类继承了一个或多个抽象类，并实现一个或多个接口。

1.       java集合框架接口

java集合框架的接口主要有：Collection接口、List接口、ListIterator接口、set接口、Map接口，现一一简析如下：

1.1   Collection接口

 Collection是java集合框架中最基本的接口，一个Collection代表一组对象（Object）,Java SDK中没有提供直接继承自Collection有类，但是提供了继承自Collection的子接口（List

和set接口）;

所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后一个构造函数允许用户复制一个Collection。如要遍历Collection中的元素，可以采用迭代的方法，即iterator()方法，该方法返回一个迭代器，使用该迭代器一一访问Collection中的元素。如下所示：

Iterator it=collection.iterrator();

While(it.hasNext())

{Object obj=it.next();

}

由Collection接口派生了两个重要接口，即List和Set.

1.2.List接口

List接口最大的特点就是有序，并允许有相同的元素，因了List接口继承自Collection接口，所以遍历List同样可以用迭代器的方法，另外List还提供了一个listIterator()方法，该方法返回的是ListIterator接口，和Iterator接口不同的是，该接口增加了添加，删除，设定元素的方法，也可以向前或者向后遍历。

1.2   ListIterator接口

  ListIterator接口继承了Iterator接口，同时增加了一些新的方法，如元素的添加、删除等方法，元素的添加的位置在next方法返回的元素之前，而在previous方法之后 。

1.3set接口

Set接口继承自Collection接口，set接口中的元素不包含重复的元素，所有set的构造函数有一个约束条件，就是传入的Collection参数不能包含重复的元素。遍历set中的元素同样可以用迭代的方法。

1.4Map接口

和List接口及set接口不同的是map接口不继承自Collection接口，也不继承别的接口，它提供的是key到value的映射，一个map中不能包含相同的key，每个 key只能映射一个value..map接口中提供的方法有：

Void clear();//清除该map中的所有映射;

Boolean containsKey(Object key);//如果该指定的键存在映射，则返回true

Boolean ContainsValue(Object Value);//如果该map中有一个或者多个键与传入的value形成映射，则返回真，就是用来查询有没有键已经与映射到了这个键。

Public Set entrySet();//返回一个该map中包含的集合

说明：set依靠map支持，因此对map的改变瘵会反映到set中,反之亦然。如果在对set进行迭代的时候，Map被修改了，该迭代的结果就是未定义的，Set支持元素的删除，即通过Iterator.remove、Set.remove、emoveAll、returnAll和Clearr操作，将相应的映射从Map中删除。

Object get(Object key);//通过key查找该key所映射的value，如果该key对应的value不存在，即不存在该映射，则返回null.当然返回null不一定就不存在该映射，有可能Map将该键映射到了null.

Boolean isEmpty();//判断该Map中是否包含着key-value的映射，如果不存在这样的映射。则返回true;

Public Set keySet();//返回该Map中包含的所有键，并放入集合Set中

Object put(Object key,Object value);//这个操作Map最常用的方法，就是建立键-值的映射，这里有几个注意点:

a.       所有实现map接口的类都必须实现该方法；

b.       如果Map中不允许空键，则传入的参数key不能为null;

c.       如果传入的key在Map中已经映射了相应的value，则以前的该key重新和新的value进行映射，旧的value会被替换

Void putAll(Map t);//把t中所有的映射关系复制到该map中

Object remove(Object key);//移除指定key对应的映射，如果该键对应的映射不存在，返回null;

Int size();//得到该Map中所有映射的数目

Pulic Collection values();//

刚刚介绍了Map接口所有定义的方法，这些方法的介绍应该在API中才能找到，这儿只是我的理解+我不怎么专业的英文翻译而来的。

在Map接口中还有一个很重要的接口，即Entry接口

如果要取得Map中的所有映射信息，我们最常用的办法就是先迭代得到Map中键的集合Set,然后通过遍历该Set,再得到每个键对应的value,具体代码如下：

Set keys = map.keySet( );if(keys != null) {Iterator iterator = keys.iterator( );while(iterator.hasNext( )) {Object key = iterator.next( );Object value = map.get(key);;....;}} 

尽管这个方法可以达到我们的目的，但是这个过程是很费时的，因为从Map中取得关键字后，我们必须重复返回到Map中取得相对应的值。而使用Map.entry

会相对简单些：

Map类提供了一个称为entrySet()的方法，这个方法返回一个Map.Entry实例化后的对象集。接着，Map.Entry类提供了一个getKey()方法和一个getValue()方法，因此，上面的代码可以被组织得更符合逻辑。举例如下：

Set entries = map.entrySet( );if(entries != null) {Iterator iterator = entries.iterator( );while(iterator.hasNext( )) {Map.Entry entry =iterator.next( );Object key = entry.getKey( );Object value = entry.getValue();;....}} 

尽管增加了一行代码，我们却省略了许多对Map不必要的“get”调用。同时，提供给开发人员一个同时保持了关键字和其对应的值的类。Map.Entry同时也提供了一个setValue（）方法，程序员可以使用它修改map里面的值。

到此，已经介绍了java集合框架中的重要接口，并对Map接口作了较详细的分析，接下来介绍的java集合框架中的类，其中要详细分析的是HashMap类。

2.      java集合框架的类

集合框架中的类都是实现了java集合框架中的接口的，主要有：

ArrayList类、LinkedList类、TreeSet类、TreeMap类、HashSet类、HashMap类。

2.1ArrayList类

可以说ArrayList对象是数组的改良版本，但是ArrayList还是不能完全替代数组的，尽管在ArrayList相对数组来说长度可以在程序执行的过程中自动进行调整，并且ArrayList对象具有在任何索引位置插入或删除元素的方法，而在数组中插入或删除元素就得编写代码增加或减少存储空间，但是数组作为一种常用的数据结构，有其自身的特点：一般来说数组的执行效果要高于ArrayList的，所以在一般情况下，还是要尽量使用数组。

ArrayList是一个对象，并实现了List接口的，所以它有的属性和方法，最常见的属性有两个：ArrayList对象中每个元素的相对位置利用索引来表示;ArrayList的大小可以根据程序执行自动调整。

ArrayList常见的方法有：

Public boolean add(object o);

Public Int size();

Public object get(int index);

Public Object set(int index,Object element);

这些方法完全可以望文生义，通过传入的参数及方法名便可得知它是用来干什么的，所以就不再多说了。

2.2LinkedList类

类似于ArrayList类，LinkedList类也实现了List接口，但是这两个类还是有重要区别的：

首先，LinkedList类并不具有带一个初始容量参数的构造函数，因为LinkedList对象根据需要进行扩展或者缩减。另外LinkedList类具有6个ArrayList类所没有的方法。

1.      public boolean addFirst(Object element);

2.      public boolean addLast(Object element);

3.      public object getFirst();

4.      public Object getLast();

5.      public Object removeFirst();

6.      Public ojectvremoveLast();

LinkedList还有个特点就在于其迭代器，和其它迭代器不同的是LinkedList迭代是双向的，可以正向也可以是反向，定义迭代器的类是ListItr。ListItr是实现了ListIterator接口的，是LinkedList的一个私有类，因此要创建一Listltr对象，必须利用LinkedList类的方法来创建ListItr对象。由于这次要说的重点是HashMap,所以LinkedList类不再说了。

2.3关于散列

散列是一种神奇的技术，通过散列可以实现在平均不变的时间内完成检索以及插入和删除，如果了解了散列的工作原理，便会很容易实现HashMap的相关方法。

对于我们已经了解过的几种数据结构，各有各的特点，比如数组的特点就是执行查找简单并且效率很高，但执行删除和插入就会显得很不方便，而另一种数据结构链表插入和删除元素很方便，但查找元素效率较低，那么如果我们要求插入、删除和查找都能高效的执行，我们就得定义一种新的数据结构，hash表就是这样一个神圣使者。那么hash表是如何做到的呢？这里面的关键就是散列的设计。所以接下来我要从我的理解出发讲清散列的工作原理并实现HashMap中的相关的几个常见方法。

散列是将键-值对中的键转换为索引的过程。转换首先将给定键作为参数，调用hashcode()方法，键类可以自己定义hashcode()方法，也可以从它的祖先那里继承hashcode方法，该方法的作用中通过对传入的键值进行简单的计算，返回一个int型数，即为散列值，然后在将这个值进行转换成数组索引，当然这一步不是hashcode()方法完成的。Hash算法的特点是用有较小的数组空间来存储数量比已经定义的数组空间大的值空间，和值对应的就是键，也就是键值对，所以当所有合法键的数目比数组索引空间大时，就一定会产生冲突，即某个键会映射到同一个索引位置。散列要做的不仅是把键转换成数组索引，更重要的是对冲突的处理。

先研究将键转换成数组的索引，然后再研究如何处理冲突。整个转换过程是：

 
            键hashcode()   散列值
 
  
  
   
   
   
   
   
   
   
   
   
   
   
   
  
  
  
 
  
  
  
 
  
 
 
数组索引

键转换为散列值是通过hashcode()方法进行的，如果键本身是Integer类型的，则hashcode方法简单的返回int类型整数，如果键是String类型的，要通过处理得到int型的散列值，下面是一个简单的处理方法。

Public int hashCode(){

Int h=0;//初始化要返回的散列值

Char val[]=value;//定义存放String类键的数组

Int a=0;数组中第一个字符的索引值

Int len=0;//字符串长度

for(int i=0;i<len;i++){

h=30*h+val[a++];

return h;

}

}

如何明智的选择hashCode()方法在于使用者，有一种叫做折叠法的方法能够很好的工作大hashcode（）方法上，即使用位操作对键的比特序列进行与或操作。

如何将散列值转换为数组的索引呢？最常用的方法是：

Index=hash%table.length;//table为已经定义好长度的数组

通过以上转换，将得到一个取值范围在0-table.length-1之间的索引，如果散列值是一个负数，可以通过取绝对值的方法得到其对应的正数，还有一种办法就是将散列值与最大的int类型数进行相与操作，这样如果散列值是负数，将会得到其取绝对值对应的负数，如果是正数，相与操作后其值不改变，所以散列值的转换过程可改为：

Index=(hash&0x7FFFFFFF)%table.length;

在HashMap类中，通过链来高效的解决冲突方法。

因为键通过hashcode()方法转化为散列值，再将散列值转换为数组索引，这个过程会产生冲突，即多个键值通过两步转换后可能得到了同一个索引位置，所谓链技术就是把转换后具有相同索引的元素存入一个单向链表中，然后再将该单向链表放入键转换后的索引位置中，也就是该单向链表中的元素具有同一个索引值。那么这儿又出现了一个问题，就是该如何构造这个链表呢？Map中有个内置对象Entry,它有四个属性：

Int hash;//用来存放通过hashcode方法返回的散列值，避免重新计算

Object key;//键

Object value//值

Entry next;//指向下一个Entry，构成链表结构

看的出来这个Entry对象完全能满足要求，也就是说在数组的每个索引位置存放的是Entry对象，所以构建数组时构建的是Entry型数组。分析到这儿，哈希算法所要求的都已经具备了，现在只差具体实现了，接下来就自己写代码具体实现哈希算法，具体表现在hashMap类的实现当中，其实呢HashMap类的源代码已经在java.util下包中存在了，并且已经很详细了，但毕竟那是别人写的，通过自己的理解实现的代码才是自己的，所以我还是再自己实现一下HashMap类中我们常用的添加方法。

首先自己构建Entry对象：

package hashMap;

//重新构建的Entry对象

public class Entry {

private int hash;

private Object key;

private Object value;

Entry next;

public int getHash() {

    return hash;

}

public void setHash(int hash) {

    this.hash = hash;

}

public Object getKey() {

    return key;

}

public void setKey(Object key) {

    this.key = key;

}

public Object getValue() {

    return value;

}

public void setValue(Object value) {

    this.value = value;

}

public Entry getNext() {

    return next;

}

public void setNext(Entry next) {

    this.next = next;

}

}

下面是HashMap类

package hashMap;

 

a