Note.Markdown MachineLearning Algorithm Skill Tool Other From Easy On, Just Do It

Java 高级操作 since 2013-07- 7

Java 语法的高级操作

LinkedHashMap 有序哈系表

Jdk中的MAP容器主要有三种实现： 1. HashMap 2. TreeMap 3. LinkedHashMap

  1. HashMap 其key是完全无序的
  2. TreeMap 允许用户定义key的比较函数(compare函数)，因此其key是根据比较函数排序的
  3. LinkedHashMap 在HashMap基础上，设定了key的迭代顺序，默认按照插入顺序，也可以设定按照更新顺序

这里主要介绍一下LinkedHashMap，首先看看其参数最多的构造函数：

/**
 * Constructs an empty <tt>LinkedHashMap</tt> instance with the
 * specified initial capacity, load factor and ordering mode.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @param  accessOrder     the ordering mode - <tt>true</tt> for
 *         access-order, <tt>false</tt> for insertion-order
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

注意到，accessOrder参数就是用来设定key的排序方式

LinkedHashMap按照key排序的机制实现是非常简单的，就是在HashMap的基础上，在每个Entry上添加了两个‘指针’，分别指向前后两个元素:

/**
 * LinkedHashMap entry.
 */
private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    Entry<K,V> before, after;
    ...

String.intern()

String.intern()方法的主要作用在于缩减字符串的存储空间，比如有很多一样的字符串，可以共用intern()方法获取常量池中的字符串对象

由于String的equals方法先比较两个字符串的引用地址是否相同，所以str1.intern().equals(str2.intern())将会十分高效

TODO more more

优先队列

逆序优先队列 

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(initCapacity, Collections.reverseOrder());

内部类做Comparater的有限队列:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(10,
    new Comparator<Integer>(){
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);//ascend order
        }
});

Shuffle

java.util.Collections中提供了随机重排数组的方法shuffle(List<?> list)

随机重排算法要求每个元素出现在每个位置的概率相等，随机过程很简单：逆序遍历数组，每次从前n个元素中随机选取一个和第n个交换位置

for (int i=size; i>1; i--)
  swap(list, i-1, rnd.nextInt(i));

但这里要考虑list是不是可以随机访问的，如果是LinkedList，则需要先转化为ArrayList，否则上面的算法需要O(n^2)的时间复杂度，完整代码如下：

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}
TOP