[2014-08-25 22:05:45 ERROR XXXX.util.ImageUtil:175] cutJPG is error,input:/home/q/www/crm.fs.qunar.com/mfs-fs/image/2f/fd/new_2ffd34d0edf5dcc7807107dd9e745d2b.jpg
javax.imageio.IIOException: Not a JPEG file: starts with 0x89 0x50
at com.sun.imageio.plugins.jpeg.JPEGImageReader.readImageHeader(Native Method)

//根据文件后缀获取Reader
Iterator<ImageReader> it = ImageIO.getImageReadersByFormatName(StringUtil.getFileSuffix(input));
ImageReader reader = it.next();
...
//获取图片读取需要的参数
ImageReadParam param = reader.getDefaultReadParam();
...
//读取图片
BufferedImage bi = reader.read(0, param);

at com.sun.imageio.plugins.jpeg.JPEGImageReader.readImageHeader(Native Method) ~[na:1.7.0_45]
at com.sun.imageio.plugins.jpeg.JPEGImageReader.readNativeHeader(JPEGImageReader.java:604) ~[na:1.7.0_45]
at com.sun.imageio.plugins.jpeg.JPEGImageReader.checkTablesOnly(JPEGImageReader.java:342) ~[na:1.7.0_45]
at com.sun.imageio.plugins.jpeg.JPEGImageReader.gotoImage(JPEGImageReader.java:476) ~[na:1.7.0_45]
at com.sun.imageio.plugins.jpeg.JPEGImageReader.readHeader(JPEGImageReader.java:597) ~[na:1.7.0_45]
at com.sun.imageio.plugins.jpeg.JPEGImageReader.readInternal(JPEGImageReader.java:1054) ~[na:1.7.0_45]
at com.sun.imageio.plugins.jpeg.JPEGImageReader.read(JPEGImageReader.java:1034) ~[na:1.7.0_45]

xiaobaoqiu@xiaobaoqiu:~/Picture$ hexdump -C 1.jpg -n 10
00000000  ff d8 ff e0 00 10 4a 46  49 46                    |......JFIF|
0000000a
xiaobaoqiu@xiaobaoqiu:~/Picture$ hexdump -C ticket.png -n 10
00000000  89 50 4e 47 0d 0a 1a 0a  00 00                    |.PNG......|
0000000a
xiaobaoqiu@xiaobaoqiu:~/Picture$ hexdump -C rtree.gif -n 10
00000000  47 49 46 38 39 61 37 02  8b 02                    |GIF89a7...|
0000000a

public class UnionFind extends AbstractUnionFind {

    /**
     * ctor
     * @param size
     */
    public UnionFind(int size) {
        assert(size > 0);

        value = new int[size];
        init();
    }

    /**
     * 初始化数据
     */
    private void init() {
        assert (value != null && value.length > 0);
        for (int i = 0; i < value.length; i++) {
            value[i] = DEFAULT_PARENT;  //DEFAULT_PARENT为-1
        }
    }

    /**
     * 合并根节点为rx 和 根节点为ry的树
     * 这里rx 和 ry为下标
     *
     * @param rx
     * @param ry
     */
    @Override
    public void Union(int rx, int ry) {
        assert (rx >= 0 && rx < value.length);
        assert (ry >= 0 && ry < value.length);

        //找到两个节点的根节点
        int px = Find(rx);
        int py = Find(ry);

        //将px设置为py的子树
        value[px] = py;
    }

    /**
     * 查找节点x的根节点
     *
     * @param x
     * @return
     */
    @Override
    public int Find(int x) {
        while(isRoot(x) == false) {
            x = value[x];
        }

        return x;
    }

    /**
     * 判断节点是否为根节点
     *
     * @param rx
     * @return
     */
    private boolean isRoot(int rx) {
        assert (rx >= 0 && rx < value.length);

        return value[rx] == DEFAULT_PARENT; //DEFAULT_PARENT为-1
    }
}

/**
 * 合并根节点为rx 和 根节点为ry的树
 * 这里rx 和 ry为下标
 *
 * @param rx
 * @param ry
 */
@Override
public void Union(int rx, int ry) {
    assert (rx >= 0 && rx < value.length);
    assert (ry >= 0 && ry < value.length);

    //找到两个节点的根节点
    int px = Find(rx);
    int py = Find(ry);

    // 将px设置为py的子树
    if (value[px] < value[py]) { // px为根节点的树高度更大, 应该将py树作为px的子树
        value[py] = px;
    } else if (value[py] < value[px]) {
        value[px] = py;
    } else { // 高度相同, 最终树的高度+1
        value[py] = px;
        value[px]--; // 数的高度+1
    }
}

/**
 * 判断节点是否为根节点
 *
 * @param rx
 * @return
 */
private boolean isRoot(int rx) {
    assert (rx >= 0 && rx < value.length);

    return value[rx] < 0;   //小于0的都表示是跟节点
}

    1
  /   \
 2     3
/ \   / \
   4   5  6  7
  / \ / \
 8  9 10 11    

import java.util.Arrays;

/**
 * 二叉堆 这里数据类型为Integer, 且堆为小顶堆
 * 几个重要的性质(具有完全二叉树的性质):
 * (1).父亲节点的下标为i,则左孩子节点下标2*i+1, 右孩子节点下标2*i+2;同理,下标为i的节点的父亲节点下标为(i-1)/2;
 * (2).n个节点的二叉堆,非叶子节点的数目为floor(n/2),如7个节点,则有3个非叶子节点;
 * (3).高度为h的完全二叉树,包含2^h到2^(h+1)-1个节点,即n个节点的二叉堆,高度为logn
 * 
 * @Author: baoqiu.xiao@qunar.com Date: 14-7-17 Time: 下午3:45
 * @Version: \$Id$
 */
public class PQueue {

    /**
     * 默认大小
     */
    private static final int DEFAULT_CAPACITY = 16;

    /**
     * 数据
     */
    private transient Integer[] queue;

    /**
     * 大小
     */
    private int size = 0;

    /**
     * ctor
     */
    public PQueue() {
        this(DEFAULT_CAPACITY);
    }

    public PQueue(int initialCapacity) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Integer[initialCapacity];
    }

    public PQueue(Integer[] array) {
        this(array.length);
        queue = Arrays.copyOf(array, array.length);
        size = array.length;

        heapify();
    }

    /**
     * 堆内元素个数, O(1)
     * 
     * @return
     */
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 取堆顶元素(这里为最小元素),但不移除堆顶元素, O(1)
     * 
     * @return
     */
    public Integer peek() {
        if (size == 0)
            return null;

        return queue[0];
    }

    /**
     * 弹出堆顶元素并返回, O(logn)
     * 
     * @return
     */
    public Integer pop() {
        if (size == 0)
            return null;

        Integer result = queue[0];
        queue[0] = queue[--size]; // 数组尾部元素放到堆顶
        queue[size] = null;
        if (size > 0) {
            shiftDown(0);
        }

        return result;
    }

    /**
     * 往堆里面插入一个元素, O(logn)
     * 
     * @param newValue
     */
    public boolean add(Integer newValue) {
        if (newValue == null)
            throw new NullPointerException();

        // 需要增长内存
        int oldSize = size;
        if (oldSize >= queue.length) {
            grow(oldSize + 1);
        }

        size = oldSize + 1;
        queue[oldSize] = newValue;
        if (oldSize > 0) {
            shiftUp(oldSize);
        }

        return true;
    }

    /**
     * 内存增长,保证能容纳 minCapacity 个元素
     * 
     * @param minCapacity
     */
    private void grow(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();

        // 这里成倍增长
        int oldCapacity = queue.length;
        int newCapacity = oldCapacity << 1;

        // 校验
        if (newCapacity < 0)
            newCapacity = Integer.MAX_VALUE;
        if (newCapacity < minCapacity)
            newCapacity = minCapacity;

        // 数据拷贝
        queue = Arrays.copyOf(this.queue, newCapacity);
    }

    /**
     * 将数组最小堆化 从最后一个非叶子节点,依次往前调整,使得每个子树都满足堆的性质
     * 根据下标为i的节点的父亲节点下标为(i-1)/2, 最大下标为size-1, 因此非根节点的最大下标为(size-2)/2, 即size/2 -1
     *
     * 直观是O(nlogn), 记得算法导论分析的均摊时间应该是O(n), 忘了怎么分析的
     */
    private void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            shiftDown(i);
    }

    /**
     * 向下调整下标为index的节点为根节点的子树, 使其满足堆的性质
     * 父亲节点的下标为i,则左孩子节点下标2*i+1, 右孩子节点下标2*i+2
     * O(logn)
     * 
     * @param index
     */
    private void shiftDown(int index) {
        //到达叶子节点了
        if(index > ((size >>> 1) - 1) )
            return;

        //左右孩子中较小的节点candidate
        int left = (index << 1) + 1, right = left + 1;
        int candidate = left;
        if(right < size && queue[right] < queue[left]){
            candidate = right;
        }

        //父节点大于子节点, 则交换父子节点, 并递归调整candide为根节点的子树
        if (queue[index] > queue[candidate]) {
            swap(index, candidate);
            shiftDown(candidate);
        }
    }

    /**
     * 向上调整下标为index的节点的数据, 保证其到根节点的路径上都满足堆的性质
     * 节点下标为i, 则父节点下标为(i-1)/2
     * O(logn)
     *
     * @param index
     */
    private void shiftUp(int index) {
        //达到根节点了
        if(index <= 0)
            return;

        int parent = (index-1)>>>1;

        //父亲节点 > 当前节点,需要交换
        if(parent >= 0 && queue[parent] > queue[index]) {
            swap(parent, index);
            shiftUp(parent);
        }
    }

    /**
     * 交换数组中 i 和 j 的元素
     * 
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        Integer tmp = queue[i];
        queue[i] = queue[j];
        queue[j] = tmp;
    }

    public static void main(String[] args) {
        PQueue queue = new PQueue();
        queue.add(6);
        queue.add(8);
        queue.add(2);
        queue.add(4);
        queue.add(5);
        queue.add(7);
        queue.add(1);

        while (!queue.isEmpty()) {
            System.out.println(queue.pop());    //1 2 4 5 6 7 8
        }
    }
}

transient volatile Set<K>        keySet = null;
transient volatile Collection<V> values = null;

//默认容量
static final int DEFAULT_INITIAL_CAPACITY = 16;

//默认装载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//长度必须为2的幂次方
transient Entry[] table;

//阈值, = capacity * load factor, 当size达到这个值的时候需要搬家
int threshold;

//装载因子
final float loadFactor;

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
}

//hash函数, h为key.hashCode()值
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

//通过hash()的返回值,获取在桶中的下标
static int indexFor(int h, int length) {
    return h & (length-1);
}

public Hashtable() {
    this(11, 0.75f);
}

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

public synchronized V get(Object key) {
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
        return e.value;
        }
    }
    return null;
}

public synchronized V put(K key, V value) {
    ...
}

public boolean containsKey(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
    while (true) {
        Object item = tab[i];
        if (item == k)  //判断键值相等
            return true;
        if (item == null)
            return false;
        i = nextKeyIndex(i, len);
    }
}

IdentityHashMap<String,Object> map =newIdentityHashMap<String,Object>();

//这两个entry会同时存在, 因为两次new String("xx")地址不一样
map.put(new String("xx"),"first");
map.put(new String("xx"),"second");

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    private transient E[] elements;

    private transient int head;

    private transient int tail;
}

public ArrayDeque() {
        elements = (E[]) new Object[16];
}

private void allocateElements(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY; //MIN_INITIAL_CAPACITY = 8
        // 能容纳numElements个元素的最小的2的幂次方
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        elements = (E[]) new Object[initialCapacity];
    }

private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;    // 当前容量大小
        int r = n - p;              // p右侧元素个数
        int newCapacity = n << 1;   // 新容量大小
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r); // 数据拷贝
        System.arraycopy(elements, 0, a, r, p);
        elements = (E[])a;
        head = 0;
        tail = n;
    }

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
    private transient Object[] queue;

    private final Comparator<? super E> comparator; //比较器

    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);   //DEFAULT_INITIAL_CAPACITY = 11
    }
}

    1
  /   \
 2     3
/ \   / \
   4   5  6  7
  / \ / \
 8  9 10 11