Java编程思想（十六）容器深入研究

作者: kaiker | 来源:发表于2022-06-26 16:51 被阅读0次

1、完整的容器分类法

容器关系

2、填充容器

Collections.fill()
Map.Entry对象之存储了它的索引而不是实际键和值。

3、Collection的功能方法

Collection的功能方法

4、可选操作

Arrays.asList()会生成一个List，它基于一个固定大小的数，仅支持哪些不会改变数组大小的操作。
应该把Arrays.asList()结果作为构造器的参数传递给任何Collection，这样可以生成允许使用所有方法的普通容器。

5、Set和存储顺序

Set

对于没有重新定义hashCode()方法的setType或TreeType，如果将它们放置到任何散列实现中都会产生重复值。

SortedSet

可以保证元素处于排序状态

6、队列

优先队列

默认是小顶堆
但可以自己实现Comparable

class ToDoList extends PriorityQueue<ToDoList.ToDoItem> {
  static class ToDoItem implements Comparable<ToDoItem> {
    private char primary;
    private int secondary;
    private String item;
    public ToDoItem(String td, char pri, int sec) {
      primary = pri;
      secondary = sec;
      item = td;
    }
    public int compareTo(ToDoItem arg) {
      if(primary > arg.primary)
        return +1;
      if(primary == arg.primary)
        if(secondary > arg.secondary)
          return +1;
        else if(secondary == arg.secondary)
          return 0;
      return -1;
    }
    public String toString() {
      return Character.toString(primary) +
        secondary + ": " + item;
    }
  }
  public void add(String td, char pri, int sec) {
    super.add(new ToDoItem(td, pri, sec));
  }
  public static void main(String[] args) {
    ToDoList toDoList = new ToDoList();
    toDoList.add("Empty trash", 'C', 4);
    toDoList.add("Feed dog", 'A', 2);
    toDoList.add("Feed bird", 'B', 7);
    toDoList.add("Mow lawn", 'C', 3);
    toDoList.add("Water lawn", 'A', 1);
    toDoList.add("Feed cat", 'B', 1);
    while(!toDoList.isEmpty())
      System.out.println(toDoList.remove());
  }
} /* Output:
A1: Water lawn
A2: Feed dog
B1: Feed cat
B7: Feed bird
C3: Mow lawn
C4: Empty trash
*///:~

双向队列

在LinkedList中包含支持双向队列的方法。

public class Deque<T> {
  private LinkedList<T> deque = new LinkedList<T>();
  public void addFirst(T e) { deque.addFirst(e); }
  public void addLast(T e) { deque.addLast(e); }
  public T getFirst() { return deque.getFirst(); }
  public T getLast() { return deque.getLast(); }
  public T removeFirst() { return deque.removeFirst(); }
  public T removeLast() { return deque.removeLast(); }
  public int size() { return deque.size(); }
  public String toString() { return deque.toString(); }
  // And other methods as necessary...
} ///:~

7、理解Map

一个简单的模仿实现

public class AssociativeArray<K,V> {
  private Object[][] pairs;
  private int index;
  public AssociativeArray(int length) {
    pairs = new Object[length][2];
  }
  public void put(K key, V value) {
    if(index >= pairs.length)
      throw new ArrayIndexOutOfBoundsException();
    pairs[index++] = new Object[]{ key, value };
  }
  @SuppressWarnings("unchecked")
  public V get(K key) {
    for(int i = 0; i < index; i++)
      if(key.equals(pairs[i][0]))
        return (V)pairs[i][1];
    return null; // Did not find key
  }
  public String toString() {
    StringBuilder result = new StringBuilder();
    for(int i = 0; i < index; i++) {
      result.append(pairs[i][0].toString());
      result.append(" : ");
      result.append(pairs[i][1].toString());
      if(i < index - 1)
        result.append("\n");
    }
    return result.toString();
  }
  public static void main(String[] args) {
    AssociativeArray<String,String> map =
      new AssociativeArray<String,String>(6);
    map.put("sky", "blue");
    map.put("grass", "green");
    map.put("ocean", "dancing");
    map.put("tree", "tall");
    map.put("earth", "brown");
    map.put("sun", "warm");
    try {
      map.put("extra", "object"); // Past the end
    } catch(ArrayIndexOutOfBoundsException e) {
      print("Too many objects!");
    }
    print(map);
    print(map.get("ocean"));
  }
} /* Output:
Too many objects!
sky : blue
grass : green
ocean : dancing
tree : tall
earth : brown
sun : warm
dancing
*///:~

性能

当在get中使用线性搜索时，执行速度会很慢。
HashMap使用了散列码来取代对键的缓慢搜索。散列码是相对唯一的，用以代表对象的int值。

各种map

SortedMap

确保键处于排序状态

LinkedHashMap

在遍历键值对时，以元素的插入顺序返回键值对。
可以在构造器中设定LinkedHashMap，使之采用基于最近最少使用算法，没被访问的元素就会出现在队列前面。

8、散列与散列码

理解hashCode()

如果不正确地覆盖hashCode()和equals，那么使用散列的数据结构就无法正确处理你的键。
散列的目的是用一个对象来查找另一个对象。
Map.EntrySet()必须产生一个Map.Entry对象集。Map.Entry是一个接口，用来描述依赖于实现的结构。

public class MapEntry<K,V> implements Map.Entry<K,V> {
  private K key;
  private V value;
  public MapEntry(K key, V value) {
    this.key = key;
    this.value = value;
  }
  public K getKey() { return key; }
  public V getValue() { return value; }
  public V setValue(V v) {
    V result = value;
    value = v;
    return result;
  }
  public int hashCode() {
    return (key==null ? 0 : key.hashCode()) ^
      (value==null ? 0 : value.hashCode());
  }
  public boolean equals(Object o) {
    if(!(o instanceof MapEntry)) return false;
    MapEntry me = (MapEntry)o;
    return
      (key == null ?
       me.getKey() == null : key.equals(me.getKey())) &&
      (value == null ?
       me.getValue()== null : value.equals(me.getValue()));
  }
  public String toString() { return key + "=" + value; }
} ///:~

为速度而散列

存储一组元素最快的数据结构是数组
数组不保存键本身，而是通过键对象生成一个数字，将其作为数组的下标，这个下标就是散列码。
于是查询一个值的过程首先就是计算散列码，然后使用散列码查询数组。
数组不直接保存值，而是保存值list。

public class SimpleHashMap<K,V> extends AbstractMap<K,V> {
  // Choose a prime number for the hash table
  // size, to achieve a uniform distribution:
  static final int SIZE = 997;
  // You can't have a physical array of generics,
  // but you can upcast to one:
  @SuppressWarnings("unchecked")
  LinkedList<MapEntry<K,V>>[] buckets =
    new LinkedList[SIZE];
  public V put(K key, V value) {
    V oldValue = null;
    int index = Math.abs(key.hashCode()) % SIZE;
    if(buckets[index] == null)
      buckets[index] = new LinkedList<MapEntry<K,V>>();
    LinkedList<MapEntry<K,V>> bucket = buckets[index];
    MapEntry<K,V> pair = new MapEntry<K,V>(key, value);
    boolean found = false;
    ListIterator<MapEntry<K,V>> it = bucket.listIterator();
    while(it.hasNext()) {
      MapEntry<K,V> iPair = it.next();
      if(iPair.getKey().equals(key)) {
        oldValue = iPair.getValue();
        it.set(pair); // Replace old with new
        found = true;
        break;
      }
    }
    if(!found)
      buckets[index].add(pair);
    return oldValue;
  }
  public V get(Object key) {
    int index = Math.abs(key.hashCode()) % SIZE;
    if(buckets[index] == null) return null;
    for(MapEntry<K,V> iPair : buckets[index])
      if(iPair.getKey().equals(key))
        return iPair.getValue();
    return null;
  }
  public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> set= new HashSet<Map.Entry<K,V>>();
    for(LinkedList<MapEntry<K,V>> bucket : buckets) {
      if(bucket == null) continue;
      for(MapEntry<K,V> mpair : bucket)
        set.add(mpair);
    }
    return set;
  }
  public static void main(String[] args) {
    SimpleHashMap<String,String> m =
      new SimpleHashMap<String,String>();
    m.putAll(Countries.capitals(25));
    System.out.println(m);
    System.out.println(m.get("ERITREA"));
    System.out.println(m.entrySet());
  }
} /* Output:
{CAMEROON=Yaounde, CONGO=Brazzaville, CHAD=N'djamena, COTE D'IVOIR (IVORY COAST)=Yamoussoukro, CENTRAL AFRICAN REPUBLIC=Bangui, GUINEA=Conakry, BOTSWANA=Gaberone, BISSAU=Bissau, EGYPT=Cairo, ANGOLA=Luanda, BURKINA FASO=Ouagadougou, ERITREA=Asmara, THE GAMBIA=Banjul, KENYA=Nairobi, GABON=Libreville, CAPE VERDE=Praia, ALGERIA=Algiers, COMOROS=Moroni, EQUATORIAL GUINEA=Malabo, BURUNDI=Bujumbura, BENIN=Porto-Novo, BULGARIA=Sofia, GHANA=Accra, DJIBOUTI=Dijibouti, ETHIOPIA=Addis Ababa}
Asmara
[CAMEROON=Yaounde, CONGO=Brazzaville, CHAD=N'djamena, COTE D'IVOIR (IVORY COAST)=Yamoussoukro, CENTRAL AFRICAN REPUBLIC=Bangui, GUINEA=Conakry, BOTSWANA=Gaberone, BISSAU=Bissau, EGYPT=Cairo, ANGOLA=Luanda, BURKINA FASO=Ouagadougou, ERITREA=Asmara, THE GAMBIA=Banjul, KENYA=Nairobi, GABON=Libreville, CAPE VERDE=Praia, ALGERIA=Algiers, COMOROS=Moroni, EQUATORIAL GUINEA=Malabo, BURUNDI=Bujumbura, BENIN=Porto-Novo, BULGARIA=Sofia, GHANA=Accra, DJIBOUTI=Dijibouti, ETHIOPIA=Addis Ababa]
*///:~

覆盖hashcode

设计hashCode()时最重要的因素就是，无论何时，对同一个对象调用hashCode()都应该产生同样的值。
String 如果值相同，那么这些String对象都映射到同一块内存区域，hashCode生成同样同样的结果。
一个设计hashCode的指导。

hashCode

9、选择接口的不同实现

容器之间的区别通常归结为由什么在背后支持他们。
对于List，ArrayList通常是访问最快的，LinkedList在表大小较大时将会有明显的访问时间增加。但是对于插入ArrayList支持不如LinkedList。
对于Set，HashSet的性能基本上总是比TreeSet好，特别是在添加和查询元素时。LinkedHashSet比HashSet多维护链表，插入代价更高。
对于Map，所有Map插入都会随Map尺寸变大而变慢，除了IdentityHashMap。TreeMap通常比HashMap慢。LinkedHashMap在插入时比HashMap慢一点，额外维护的链表。IdentityHashMap因为使用==而不是equals所以在get上快。
HashMap的性能因子：容量，表中的桶位数，初识容量，表再创建时拥有的桶位数；尺寸，表中当前存储的项数；负载因子，尺寸、容量。默认的负载因子是0.75，达到了负载因子会再散列。

10、实用方法

singleton

快速报错

Java容器有保护机制，能够防止多个进程同时修改同一个容器内容。如果在迭代遍历某个容器过程中，另一个进程接入其中，修改对象就会出现问题。

public class FailFast {
  public static void main(String[] args) {
    Collection<String> c = new ArrayList<String>();
    Iterator<String> it = c.iterator();
    c.add("An object");
    try {
      String s = it.next();
    } catch(ConcurrentModificationException e) {
      System.out.println(e);
    }
  }
} /* Output:
java.util.ConcurrentModificationException
*///:~

11、持有引用

对象是可获得的，是指此对象可在程序中的某处找到。
你在栈中有一个普通的引用，而它正指向此对象，也可能是你的引用指向某个对象，而那个对象含有另一个引用指向正在讨论的对象；也可能有更多中间链接。
如果一个对象是可获得的，垃圾回收器就不能释放他。
如果想继续持有某个对象引用，但也希望允许垃圾回收器释放，就应该使用Reference对象，内存耗尽时允许释放对象。
以Reference对象作为与普通引用之间的媒介。
SoftReference、WeakReference、PhantomReference由强到弱排列，对应不同级别的可获得性。
WeakHashMap，在这种映射中，每个值值保存一份实例以节省存储空间。当程序需要哪个值的时候，便在映射中查找现有对象，然后使用它。WeakHashMap允许垃圾回收器自动清理键和值。

class Element {
  private String ident;
  public Element(String id) { ident = id; }
  public String toString() { return ident; }
  public int hashCode() { return ident.hashCode(); }
  public boolean equals(Object r) {
    return r instanceof Element &&
      ident.equals(((Element)r).ident);
  }
  protected void finalize() {
    System.out.println("Finalizing " +
      getClass().getSimpleName() + " " + ident);
  }
}

class Key extends Element {
  public Key(String id) { super(id); }
}

class Value extends Element {
  public Value(String id) { super(id); }
}

public class CanonicalMapping {
  public static void main(String[] args) {
    int size = 1000;
    // Or, choose size via the command line:
    if(args.length > 0)
      size = new Integer(args[0]);
    Key[] keys = new Key[size];
    WeakHashMap<Key,Value> map =
      new WeakHashMap<Key,Value>();
    for(int i = 0; i < size; i++) {
      Key k = new Key(Integer.toString(i));
      Value v = new Value(Integer.toString(i));
      if(i % 3 == 0)
        keys[i] = k; // Save as "real" references
      map.put(k, v);
    }
    System.gc();
  }
} /* (Execute to see output) *///:~

Java编程思想（十六）容器深入研究

1、完整的容器分类法

2、填充容器

3、Collection的功能方法

4、可选操作

5、Set和存储顺序

SortedSet

6、队列

优先队列

双向队列

7、理解Map

性能

SortedMap

LinkedHashMap

8、散列与散列码

理解hashCode()

为速度而散列

覆盖hashcode

9、选择接口的不同实现

10、实用方法

快速报错

11、持有引用

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Java编程思想（十六） 容器深入研究

1、完整的容器分类法

2、填充容器

3、Collection的功能方法

4、可选操作

5、Set和存储顺序

SortedSet

6、队列

优先队列

双向队列

7、理解Map

性能

SortedMap

LinkedHashMap

8、散列与散列码

理解hashCode()

为速度而散列

覆盖hashcode

9、选择接口的不同实现

10、实用方法

快速报错

11、持有引用

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

Java编程思想（十六）容器深入研究