Data Structure in Java

[caipengbo]

几种常用的 Java 数据结构（集合） List , Set, Map都是接口，前两个继承至Collection接口，Map为独立接口 Set下有HashSet，LinkedHashSet，TreeSet List下有ArrayList，Vector，LinkedList Map下有Hashtable，LinkedHashMap，HashMap，TreeMap Collection接口下还有个Queue接口，有PriorityQueue类

HashTable已经弃用所以不包含在内

[caipengbo]

Map

是 Key -Value 结构，有Map.Entry作为基本单元组成

HashMap

HashMap由数组+链表组成的，HashMap中的链表出现越少，性能才会越好。

HashMap保证键的唯一性必须要让键的元素所在的类（Key）去重写 hashCode()和 equals()方法，hashCode是用于查找使用的，而equals是用于比较两个对象的是否相等的

因为自定义的类的hashcode()方法继承于Object类，其hashcode码为默认的内存地址，这样即便有相同含义的两个对象，比较也是不相等的

HashMap的原理如下：

1. 利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
2. 存储时，如果出现hash值相同的key，此时有两种情况。(1)如果key相同，则覆盖原始值；(2)如果key不同（出现冲突），则将当前的key-value放入链表中
3. 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题，核心就是使用了数组的存储方式，然后将冲突的key的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。

重写 hashCode 和 equals

@Override
public int hashCode() {
    // Pair的一种写法
    //  31 有个很好的性能，即用移位和减法来代替乘法，可以得到更好的性能：
    //  31 * i == (i << 5）- i， 现代的 VM 可以自动完成这种优化。
    int hash = 7;
    // x, y是自定义类的两个字段
    hash = 31 * hash + (x != null ? x.hashCode() : 0);
    hash = 31 * hash + (y != null ? y.hashCode() : 0);
    return hash;
}

@Override
public boolean equals(Object obj) {
    if (this == obj) return true;
    if (obj instanceof Key) {
        Key key = (Key)obj;
        return x.equals(key.x) && y.equals(key.y);
    }
    return false;
}

[caipengbo]

LinkedHashMap

LinkedHashMap继承于HashMap。

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

对于 HashMap而言，输出（遍历）结果并不是有序的，LinkedHashMap 是有序的，且默认为插入顺序。 LinkedHashMap 添加了一些指针，来进行排序

[caipengbo]

TreeMap

底层是红黑树，有序的。 Map接口定义了使用equals()判定key是否相等，SortedMap却使用compareTo()来判断key是否相等(key.compareTo(anther)==0时相等)，而TreeMap是一种SortedMap，

[caipengbo]

PriorityQueue

堆的正确使用是取出来堆顶（添加新元素），然后堆自动去调整时间复杂度为O(K)

K是堆的大小

求Top K问题

for (int value : array) {
    if (maxHeap.size() < k) {
        maxHeap.add(value);
    } else if (maxHeap.peek() > value) {
        maxHeap.poll();
        maxHeap.add(value);
    }
}