Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1969447
  • 博文数量: 606
  • 博客积分: 9991
  • 博客等级: 中将
  • 技术积分: 5725
  • 用 户 组: 普通用户
  • 注册时间: 2008-07-17 19:07
文章分类

全部博文(606)

文章存档

2011年(10)

2010年(67)

2009年(155)

2008年(386)

分类:

2008-11-18 20:18:02

使用LinkedList制作队列

LinkedList提供了方法以支持队列的行为,由此可以用来制作Queue

import com.bruceeckel.simpletest.*;
import java.util.*;

public class Queue {
  private static Test monitor = new Test();
  private LinkedList list = new LinkedList();
  public void
put(Object v) { list.addFirst(v); }
  public Object get() { return list.removeLast(); }
  public boolean isEmpty() { return list.isEmpty(); }
  public static void main(String[] args) {
    Queue queue = new Queue();
    for(int i = 0; i < 10; i++)
      queue.put(Integer.toString(i));
    while(!queue.isEmpty())
      System.out.println(queue.get());
    monitor.expect(new String[] {
      "0",
      "1",
      "2",
      "3",
      "4",
      "5",
      "6",
      "7",
      "8",
      "9"
    });
  }
} ///:~

Set的功能方法

    Set具有与C哦来了提哦那完全一样的接口,因此没有任何而外的功能。实际上Set就是Collection,只是行为不同。

   TreeSet采用红黑树的数据结构排序元素,HashSet则采用散列函数,这是专门为快速程序而设计的。LinkedHashSet内部使用散列以加快查询速度,同时使用链表维护元素的次序,使得看起来元素是以传入的顺序保存的。

SortedSet

   使用SortedSetTreeSet是器现阶段的唯一实现),可以确保元素处于排序状态,还可以使用SortedSet接口提供的附加功能。SortedSet的意思是按对象的比较函数对元素排序,而不是元素传入的次序

import com.bruceeckel.simpletest.*;
import java.util.*;

public class SortedSetDemo {
  private static Test monitor = new Test();
  public static void main(String[] args) {
    SortedSet sortedSet = new TreeSet(Arrays.asList(
    "one two three four five six seven eight".split(" ")));
   
System.out.println(sortedSet);
    Object
      low = sortedSet.first(),
      high = sortedSet.last();
    System.out.println(low);
    System.out.println(high);
    Iterator it = sortedSet.iterator();
    for(int i = 0; i <= 6; i++) {
      if(i == 3) low = it.next();
      if(i == 6) high = it.next();
      else it.next();
    }
    System.out.println(low);
    System.out.println(high);
    System.out.println(sortedSet.subSet(low, high));
    System.out.println(sortedSet.headSet(high));
    System.out.println(sortedSet.tailSet(low));
    monitor.expect(new String[] {
      "[
eight, five, four, one, seven, six, three, two]",
      "eight",
      "two",
      "one",
      "two",
      "[one, seven, six, three]",
      "[eight, five, four, one, seven, six, three]",
      "[one, seven, six, three, two]"
    });
  }
} ///:~

Map的功能方法

    性能是映射中的一个大问题。看看get()要做那些事,就会明白为什么在ArrayList中搜索相当慢的;而这正是HashMap提高速度的地方。HashMap使用了特殊的值,称作散列码,来取代对的缓慢搜索。散列码是相对唯一的、用以代表对象的int值,它是通过讲该对象的某个信息进行转换而生成。所有Java对象都能产生散类码,因为hash Code()是定义在基类Object中的方法。HashMap就是使用对的hashCode()进行快速查询的。此方法能够显著的提高性能。

import java.util.*;

class Counter {

  int i = 1;

  public String toString() { return Integer.toString(i); }

}

public class Statistics {

  private static Random rand = new Random();

  public static void main(String[] args) {

    Map hm = new HashMap();

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

      // Produce a number between 0 and 20:

      Integer r = new Integer(rand.nextInt(20));

      if(hm.containsKey(r))

        ((Counter)hm.get(r)).i++;

      else

        hm.put(r, new Counter());

    }

    System.out.println(hm);

  }

} ///:~

HashMaptoString()方法会遍历所有的键值对,并对每一个键值对调用toString()Integer.toString()是预先定义好的,而且还可以看到CountertoString()方法。程序的输出为:

{ 15=529,4=488,…………..}

SortMap

SortMapTreeMap是其现阶段的唯一实现),可以确保“键”处于排序状态。

LinkedHashMap

LinkedHashMap散列化所有的元素,但是在遍历“键值对”时,却又以元素的插入顺序返回“键值对”(println()会迭代遍历该映射,由此可以看到遍历的结果)。此外,可以在构造器中设定LinkedHashMap,使之采用给予访问的“最近最少使用”(LRU)算法,于是没有被访问过的(可以看作需要删除的)元素就会出现在队列的前面。对于需要定期清理元素以节省空间的程序来说,此功能使得程序很容易得以实现。

import com.bruceeckel.simpletest.*;

import com.bruceeckel.util.*;

import java.util.*;

public class LinkedHashMapDemo {

  private static Test monitor = new Test();

  public static void main(String[] args) {

    LinkedHashMap linkedMap = new LinkedHashMap();

    Collections2.fill(

      linkedMap, SimplePairGenerator.gen, 10);

    System.out.println(linkedMap);

    // Least-recently used order:

    linkedMap = new LinkedHashMap(16, 0.75f, true);

    Collections2.fill(

      linkedMap, SimplePairGenerator.gen, 10);

    System.out.println(linkedMap);

    for(int i = 0; i < 7; i++) // Cause accesses:

      linkedMap.get(SimplePairGenerator.gen.items[i].key);

    System.out.println(linkedMap);

    linkedMap.get(SimplePairGenerator.gen.items[0].key);

    System.out.println(linkedMap);

    monitor.expect(new String[] {

      "{one=A, two=B, three=C, four=D, five=E, " +

       "six=F, seven=G, eight=H, nine=I, ten=J}",

      "{one=A, two=B, three=C, four=D, five=E, " +

"six=F, seven=G, eight=H, nine=I, ten=J}",

      "{eight=H, nine=I, ten=J, one=A, two=B, " +

       "three=C, four=D, five=E, six=F, seven=G}",

      "{eight=H, nine=I, ten=J, two=B, three=C, " +

       "four=D, five=E, six=F, seven=G, one=A}"

    });

  }

} ///:~

“键值对”是以插入的顺序进行遍历的,甚至LRU算法的版本也是如此。在(只)访问过前面的七个元素后,最后三个元素一道了队列前面。然后在一次访问元素“one”时,它就被移到队列后端了。

散列码与散列法

Statics.java中,标准类库中的类(Integer)被用作HashMap的“键”。它用得很好,因为它具备了“键”所需的全部性质。但是,如果自己创建类作为HashMap的“键”使用,通常会犯一个错误。

import com.bruceeckel.simpletest.*;

import java.util.*;

import java.lang.reflect.*;

public class SpringDetector {

  private static Test monitor = new Test();

  // Uses a Groundhog or class derived from Groundhog:

  public static void

  detectSpring(Class groundHogClass) throws Exception {

    Constructor ghog = groundHogClass.getConstructor(

      new Class[] {int.class});

    Map map = new HashMap();

    for(int i = 0; i < 10; i++)

      map.put(ghog.newInstance(

new Object[]{ new Integer(i) }), new Prediction());

    System.out.println("map = " + map + "\n");

    Groundhog gh = (Groundhog)

ghog.newInstance(new Object[]{ new Integer(3) });

    System.out.println("Looking up prediction for " + gh);

    if(map.containsKey(gh))

      System.out.println((Prediction)map.get(gh));

    else

      System.out.println("Key not found: " + gh);

  }

  public static void main(String[] args) throws Exception {

    detectSpring(Groundhog.class);

    monitor.expect(new String[] {

      "%% map = \\{(Groundhog #\\d=" +

      "(Early Spring!|Six more weeks of Winter!)" +

      "(, )?){10}\\}",

      "",

      "Looking up prediction for Groundhog #3",

      "Key not found: Groundhog #3"

    });

    }

} ///:~

问题出在Groundhog继承自Object。所以这里是使用Object hashCode()方法生成散列码,而它默认是使用对象的地址计算散列码。因此,由Groundhog(3)生成的第一个实例的散列码与由Groundhog(3)生成的第二个实例的散列码是不同的,而我们正是使用后者进行查找的。

如果只编写hashCode()方法的覆盖版本,仍然无法正常运行,除非同时覆盖equals()方法,它也是Object的一部分。

默认的Object.equals()只是比较对象的地址,如果要使用自己类作为HashMap的“键”,必须同时重载hashCode()equals()

public class Groundhog2 extends Groundhog {

  public Groundhog2(int n) { super(n); }

  public int hashCode() { return number; }

  public boolean equals(Object o) {

return (o instanceof Groundhog2)

&& (number == ((Groundhog2)o).number);

}

} ///:~

 HashMap速度快的原因

散列将“键”保存在某处,以便能够很快找到。因为数组的速度很快,所以用它来保存“键”的信息(而不是“键”本身)。解决数组容量固定对保存“键”信息影响的问题,数组保存通过“键”对象生成的一个数字,将其作为数组的下标。这个数字就是散列码,由定义在Object中的、且可能由你的覆盖的hashCode()(散列函数)方法生成,不同的“键”可以产生相同的下标。也就是说,可能会由冲突。因此,数组多大就不重要了,每个“键”总能在数组中找到它的位置。

于是查询一个“值”的过程首先就是计算散列码,然后使用散列码查询数组。如果能够保证没有冲突(如果“值”的数量是固定的,那么就由可能),那可就由一个完美的散列函数,但是这种情况只是特例。通常,冲突由“外部链接”处理:数组并不直接保存“值”,而是保存“值”的list。然后对list中的“值”使用equals()方法进行线性查询。这部分的查询自然会比较慢,但是,如果散列函数好的化,数组的每个位置就只有较少的“值”。因此,不是查询这个list,而是快速地跳到数组的某个位置,只对很少的元素进行比较。

import java.util.*;

import com.bruceeckel.util.*;

public class SimpleHashMap extends AbstractMap {

  // Choose a prime number for the hash table

  // size, to achieve a uniform distribution:

  private static final int SZ = 997;

  private LinkedList[] bucket = new LinkedList[SZ];

  public Object put(Object key, Object value) {

    Object result = null;

    int index = key.hashCode() % SZ;

    if(index < 0) index = -index;

    if(bucket[index] == null)

      bucket[index] = new LinkedList();

    LinkedList pairs = bucket[index];

    MPair pair = new MPair(key, value);

    ListIterator it = pairs.listIterator();

    boolean found = false;

    while(it.hasNext()) {

      Object iPair = it.next();

      if(iPair.equals(pair)) {

result = ((MPair)iPair).getValue();

it.set(pair); // Replace old with new

        found = true;

        break;

      }

    }

    if(!found)

      bucket[index].add(pair);

    return result;

  }

  public Object get(Object key) {

    int index = key.hashCode() % SZ;

    if(index < 0) index = -index;

    if(bucket[index] == null) return null;

    LinkedList pairs = bucket[index];

    MPair match = new MPair(key, null);

    ListIterator it = pairs.listIterator();

    while(it.hasNext()) {

      Object iPair = it.next();

      if(iPair.equals(match))

        return ((MPair)iPair).getValue();

    }

    return null;

  }

  public Set entrySet() {

    Set entries = new HashSet();

    for(int i = 0; i < bucket.length; i++) {

      if(bucket[i] == null) continue;

      Iterator it = bucket[i].iterator();

      while(it.hasNext())

        entries.add(it.next());

    }

    return entries;

  }

  public static void main(String[] args) {

    SimpleHashMap m = new SimpleHashMap();

    Collections2.fill(m, Collections2.geography, 25);

    System.out.println(m);

  }

} ///:~

注意:为了能够自动处理冲突,使用了一个LinkedList数组;每一个元素只是直接添加到list的末尾。

如果指定的“键”已经存在于list中了,那么put()将返回于此“键”相关联的旧“值”,否则返回null

HashMap的性能因子

容量(capacity):散列标中桶的数量。

初始化容量(initial capacity):创建散列标时桶的数量。

尺寸(size):当前散列表中记录的数量。

负载因子(load factor):等于“尺寸/容量”。轻伏在的散列表具有冲突少、适宜插入与查询的特点(但是使用迭代器会变慢)。当负载达到指定值时,容器会自动成倍的增加容量(桶的数量),并将原有的对象重新分配,存入新的桶内(这称为“重散列”)。

    如果知道HashMap中会由很多基类,载创建的时候就使用较大的初始化容量,可以避免自动重散列的开销。

    覆盖hashCode()

设计hashCode()时最重要的因素就是:无论何时,对同一个对象调用hashCode()都应该生成同样的值。

此外,也不应该使hashCode()依赖于具体唯一性的对象信息,尤其是使用this的值,这只能产生很糟糕的hashCode()

import com.bruceeckel.simpletest.*;

public class StringHashCode {

  private static Test monitor = new Test();

  public static void main(String[] args) {

    System.out.println("Hello".hashCode());

    System.out.println("Hello".hashCode());

    monitor.expect(new String[] {

      "69609650",

"69609650"

    });

  }

} ///:~

对于String而言,hashCode()明显是给予String的内容的。

散列码不必是独一无二的(应该更关注生成速度,而不是唯一性),但是通过hashCode()equals(),必须能够完全确定对象的身份。

好的hashCode()应该产生分布均匀的散列码。

Effective Java对于hashCode()的基本指导:

1)  int变量result赋予某个非零值常量,例如17

2)  为对象内每个由意义的字段f(即每个可以做equals()操作的字段)计算处一个int散列码c

3)  合并计算得到的散列码:

result =  37 * result + c;

    4) 返回result

    5)检查hashCode()最后是产生的结果,确保相同的对象有相同的散列码。

import com.bruceeckel.simpletest.*;

import java.util.*;

public class CountedString {

  private static Test monitor = new Test();

  private static List created = new ArrayList();

  private String s;

  private int id = 0;

  public CountedString(String str) {

    s = str;

    created.add(s);

    Iterator it = created.iterator();

    // Id is the total number of instances

    // of this string in use by CountedString:

    while(it.hasNext())

      if(it.next().equals(s))

        id++;

  }

  public String toString() {

    return "String: " + s + " id: " + id +

      " hashCode(): " + hashCode();

  }

  public int hashCode() {

    // Very simple approach:

// return s.hashCode() * id;

Using Joshua Bloch's recipe:

result = 17;

ult = 37*result + s.hashCode();

sult = 37*result + id;

    return result;

  }

  public boolean equals(Object o) {

    return (o instanceof CountedString)

      && s.equals(((CountedString)o).s)

      && id == ((CountedString)o).id;

  }

  public static void main(String[] args) {

    Map map = new HashMap();

    CountedString[] cs = new CountedString[10];

    for(int i = 0; i < cs.length; i++) {

      cs[i] = new CountedString("hi");

      map.put(cs[i], new Integer(i));

    }

    System.out.println(map);

    for(int i = 0; i < cs.length; i++) {

      System.out.println("Looking up " + cs[i]);

      System.out.println(map.get(cs[i]));

    }

    monitor.expect(new String[] {

      "{String: hi id: 4 hashCode(): 146450=3," +

      " String: hi id: 10 hashCode(): 146456=9," +

      " String: hi id: 6 hashCode(): 146452=5," +

      " String: hi id: 1 hashCode(): 146447=0," +

      " String: hi id: 9 hashCode(): 146455=8," +

      " String: hi id: 8 hashCode(): 146454=7," +

      " String: hi id: 3 hashCode(): 146449=2," +

      " String: hi id: 5 hashCode(): 146451=4," +

      " String: hi id: 7 hashCode(): 146453=6," +

      " String: hi id: 2 hashCode(): 146448=1}",

      "Looking up String: hi id: 1 hashCode(): 146447",

      "0",

      "Looking up String: hi id: 2 hashCode(): 146448",

      "1",

      "Looking up String: hi id: 3 hashCode(): 146449",

      "2",

      "Looking up String: hi id: 4 hashCode(): 146450",

      "3",

      "Looking up String: hi id: 5 hashCode(): 146451",

      "4",

      "Looking up String: hi id: 6 hashCode(): 146452",

      "5",

      "Looking up String: hi id: 7 hashCode(): 146453",

      "6",

      "Looking up String: hi id: 8 hashCode(): 146454",

      "7",

      "Looking up String: hi id: 9 hashCode(): 146455",

      "8",

      "Looking up String: hi id: 10 hashCode(): 146456",

      "9"

    });

  }

} ///:~

   选择接口的不同实现

HashSet是最常用的,查询速度最快;LinkedHashSet保持元素插入的次序;TreeSet给予TreeMap,生成一个总是处于排序状态的Set

List的选择

  一个例子的测试结果:

     ArrayList的开销对于LinkedList。(奇怪的是,对于迭代遍历操作,LinkedListArrayList要快,这一点有悖于直觉)。另以方面,从中间的位置插入和删除元素,LinkedList要比ArrayList快,特别是删除操作。Vector通常比ArrayList慢。

 Set的选择

    HashSet的性能总是比TreeSet好(特别是最常用的添加和查询元素操作)。TreeSet存在的唯一原因是它可以维持元素的排序状态。

    对于插入操作,LinkedHashSetHashSet略微慢一点;这是维护链表所带来的额外开销造成的。不过,因为有了链表,遍历LinkedHashSet会更快。 

    Map的选择

   Map的尺寸是影响性能的最重要因素。

    List的排序和查询

import com.bruceeckel.util.*;

import java.util.*;

public class ListSortSearch {

  public static void main(String[] args) {

    List list = new ArrayList();

    Collections2.fill(list, Collections2.capitals, 25);

    System.out.println(list + "\n");

    Collections.shuffle(list);

    System.out.println("After shuffling: " + list);

    Collections.sort(list);

    System.out.println(list + "\n");

    Object key = list.get(12);

    int index = Collections.binarySearch(list, key);

    System.out.println("Location of " + key +

      " is " + index + ", list.get(" +

      index + ") = " + list.get(index));

    AlphabeticComparator comp = new AlphabeticComparator();

Collections.sort(list, comp);

    System.out.println(list + "\n");

    key = list.get(12);

       index = Collections.binarySearch(list, key, comp);

    System.out.println("Location of " + key +

      " is " + index + ", list.get(" +

      index + ") = " + list.get(index));

  }

} ///:~

如果使用Comparator进行排序,那么binarySearch()必须使用相同的Comparator

   Collection类的一些实用方法:

    Collection Map的同步控制

import java.util.*;

public class Synchronization {

  public static void main(String[] args) {

    Collection c =

      Collections.synchronizedCollection(new ArrayList());

    List list =

      Collections.synchronizedList(new ArrayList());

    Set s = Collections.synchronizedSet(new HashSet());

    Map m = Collections.synchronizedMap(new HashMap());

  }

} ///:~

快速报错

Java容器有一种保护机制,能够防止多个进程同时修改同一个容器的内容。如果你正在迭代遍历某个容器,此时另一个进程介入其中,并且插入、删除或修改此容器内的某个对象,那么就会发生问题,抛出ConcurrentModificationException异常。

import java.util.*;

public class FailFast {

  public static void main(String[] args) {

    Collection c = new ArrayList();

    Iterator it = c.iterator();

    c.add("An object");

    // Causes an exception:

    String s = (String)it.next();

  }

} ///:~

阅读(1167) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~