DataStructure

Linear Data Structure

Queue

BFS 的主要类型结构 —— 都是O(1)

Stack

DFS 的主要类型结构 Push(), Peek(), Top()都是O(1)

Hash

Hash Table => 支持多线程, 多线程安全

Hash Map

Hash Set

Hash Function 对于任意的key得到一个固定的，无规律的，介于0 ~ capacity - 1的整数

• MD5
• SHA - 1
• SHA - 2

解决冲突的方式:

• Closest Hashing 占下一个坑
• Open Hashing (存链表) 记得自己实现下

Hash 表不够大 ？=> Rehashing

如果想要存 x 数，hash表最好有10 * x个坑位

自己实现Hash Map; 做下 LRU cache的问题

自己的HashMap

public class myOwnHash {
    private static final int SIZE = 16;
    private Entry table[] = new Entry[SIZE];
    class Entry {
        final String key;
        String value;
        Entry next;
        Entry(String k, String v) {
            key = k;
            value = v;
        }
        public String getValue() {
            return value;
        }
        public void setValue(String value) {
            this.value = value;
        }
        public String getKey() {
            return key;
        }
    }

    public Entry get(String k) {
        int hash = k.hashCode() % SIZE;
        Entry e = table[hash];
        while (e != null) {
            if (e.key.equals(k)) {
                return e;
            }
            e = e.next;
        }
        return null;
    }

    public void put(String k, String v) {
        int hash = k.hashCode() % SIZE;
        Entry e = table[hash];
        // E != null 查看是否需要覆盖
        if (e != null) {
            while (e.next != null) {
                if (e.key.equals(k)) {
                    e.value = v;
                    return;
                }
                e = e.next;
            }
            Entry newE = new Entry(k, v);
            e.next = newE;
        }
        else {
            Entry newE = new Entry(k, v);
            table[hash] = newE;
        }
    }

    public static void main(String[] args) {
        myOwnHash xiao = new myOwnHash();
        xiao.put("cx", "sv");
        System.out.print(xiao.get("cx").getValue());
    }
}

---

Tree

一定记得认真研究一下Trie结构，基本是Google家必面的一个数据结构

---

Heap

O(logN) add / O(logN) delete / O(1) get min or get max