基础算法

数组的特点：下标和随机访问，缺点插入和删除很慢时间复杂度O(n)，数组下标为什么从0开始，因为数组的内存地址是连续的，可以通过起始地址+数组下标方便的获取对应数组下标的数据；二维数组n[i][j]的寻址公式：(i * length) + j

斐波那契

递归优化：

• 使用非递归：所有递归代码理论上一定可转换成非递归
• 加入缓存：把中间运算结果保存起来，这样就可把递归降至为o(n)
• 尾递归：调用函数一定出现在末尾，没有任何其他操作，编译器在编译代码时，若发现函数末尾已经没有操作了，这时候就不会创建新的栈，且覆盖到前面去。倒着算，每次会把中间结果带下去，不需要再回溯

public static int fab(int n) { // 时间复杂度和空间复杂度都是：O(2^n)
    if (n <= 2) {
        return 1; // 递归的终止条件
    }
    return fab(n - 1) + fab(n - 2); // 继续递归的过程
}
public static int noFab(int n) { // 不用递归 O(n)
    if (n <= 2)
        return 1;
    int a = 1;
    int b = 1;
    int c = 0;
    for (int i = 3; i <= n; i++) { // 循环
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}
public static int fab2(int n) { // 用数组来做缓存，时间复杂度降为O(n)，空间也降至为O(n)
    if (n <= 2)
        return 1; // 递归的终止条件
    if (data[n] > 0) {
        return data[n];
    }
    int res = fab2(n - 1) + fab2(n - 2); // 继续递归的过程
    data[n] = res;
    return res;
}
/**
 * n    - 是肯定有的
 * res  - 上一次运算出来结果
 * pre  - 上上一次运算出来的结果
 */
public static int tailfab(int pre, int res, int n) { // 时间复杂度和空间复杂度都是：O(n)
    if (n <= 2) {
        return res; // 递归的终止条件
    }
    return tailfab(res, pre + res, n - 1); // JDK源码
}

public static int fac(int n) { // 求N的阶乘 用普通递归怎么写 5=5*4*3*2*1=> f(n) =
    if (n <= 1) {
        return 1;
    }
    return n * fac(n - 1);
}
public static int tailFac(int n, int res) { // 尾递归 传结果，res就是我们每次保存的结果
    System.out.println(n + ":" + res);      // 这个地方打印出来的值是怎么样的？
    if (n <= 1) {
        return res;
    }
    return tailFac(n - 1, n * res);         //倒着算
}

2的整数次幂

// 获取数据二进制的最高位，低位全部置0，获取小于等于i的最接近的2的整数次幂的数
public static int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}
// 获取大于等于cap的最接近的2的幂的数作为数组的容量
static final int tableSizeFor(int cap) { 
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

Hash

Hash应用

加密如MD5哈希算法、判断数据重复MD5、相似性检测如论文检测、指纹算法，把每个论文计算出一个指纹，使用汉明距离，负载均衡策略如Nginx可根据ip计算hash值，分布式系统数据分库分表问题。一致性Hash即哈希环。

开放寻址

开放寻址法核心思想是，若出现散列冲突就重新探测一个空闲位置将其插入，当往散列表中插入数据时，若某个数据经过散列函数散列之后，存储位置已经被占用了，就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。

缺点：删除需要特殊处理，若插入数据过多会导致散列表很多冲突查找可能会退化成遍历

链路地址

使用链表，链表法是一种更加常用的散列冲突解决办法，相比开放寻址法，它要简单很多，在散列表中，每个key会对应一条链表，所有散列值相同的元素都放到相同槽位对应的链表中。

常用hash算法

以下三个Hash散列算法，可将算出的Hash值比较均匀分布到不同的段

public int hash_1(String key) {
    int hash = 0;
    int i;
    for (i = 0; i < key.length(); ++i) {
        hash = 33 * hash + key.charAt(i);
    }
    return Math.abs(hash) % size;
}
public int hash_2(String key) {
    final int p = 16777619;
    int hash = (int) 2166136261L;
    for (int i = 0; i < key.length(); i++) {
        hash = (hash ^ key.charAt(i)) * p;
    }
    hash += hash << 13;
    hash ^= hash >> 7;
    hash += hash << 3;
    hash ^= hash >> 17;
    hash += hash << 5;
    return Math.abs(hash) % size;
}
public int hash_3(String key) {
    int hash, i;
    for (hash = 0, i = 0; i < key.length(); ++i) {
        hash += key.charAt(i);
        hash += hash << 10;
        hash ^= hash >> 6;
    }
    hash += hash << 3;
    hash ^= hash >> 11;
    hash += hash << 15;
    return Math.abs(hash) % size;
}

JDK8中ConcurrentHashMap中因为数组大小限制导致高位在索引计算中一直用不到，故在spread方法中将hash的高16位利用起来进行异或转换，最后与HASH_BITS相与的目的是让得到的hash值总是正数，保证正数的目的是，因为hash值为-1表示哈希表正在扩容中，该哈希桶已经被迁移到了新的临时hash表，此时节点为ForwardingNode类型。

static final int HASH_BITS = 0x7fffffff;
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

BitMap

public class BitMap {
    byte[] bits;        // 若为byte那就一个只能存8个数
    int max;            // 表示最大的那个数
    public BitMap(int max) {
        this.max = max;
        bits = new byte[(max >> 3) + 1];        //max/8 + 1
    }
    public void add(int n) {    // 往bitmap里面添加数字
        if (n > max) {
            throw new IllegalArgumentException();
        }
        int bitsIndex = n >> 3; // 除以8就可知道byte数组下标
        int loc = n & 7;        // 用&运算，获取bit位
        bits[bitsIndex] |= 1 << loc; // 把bit数组中bisIndex下标的byte里面第loc个bit位置为1
    }
    public boolean find(int n) {
        if (n > max) {
            throw new IllegalArgumentException();
        }
        int bitsIndex = n >> 3; // 除以8就可知道byte数组下标
        int loc = n & 7;        // 这里其实还可以用&运算
        int flag = bits[bitsIndex] & 1 << loc; // 若原来那个位置是0 那肯定就是0 只有那个位置是1 才行
        return flag != 0;
    }
    public void delete(int n) {
        if (n > max) {
            throw new IllegalArgumentException();
        }
        int index = n >> 3;     // 除以8就可知道byte数组下标
        int loc = n & 7;        // 这里其实还可以用&运算
        bits[index] &= ~(1 << loc);
    }
    public static void main(String[] args) {
        BitMap bitMap = new BitMap(200000001); // 10亿
        bitMap.add(2);
        bitMap.add(3);
        bitMap.add(4);
        bitMap.add(63);
        bitMap.add(65);
        System.out.println(bitMap.find(3));
        System.out.println(bitMap.find(64));
        bitMap.delete(3);
        System.out.println(bitMap.find(3));
    }
}

BloomFilter

public class BloomFilter {
    int size;
    BitSet bits; // bit数组,bitMap long /64 %34
    // 00000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111
    public BloomFilter(int size) {
        this.size = size;
        bits = new BitSet(size);
    }
    public void add(String key) {    // O(1)
        int hash1 = hash_1(key);
        int hash2 = hash_2(key);
        int hash3 = hash_3(key);

        bits.set(hash1, true);
        bits.set(hash2, true);
        bits.set(hash3, true);
    }
    public boolean find(String key) {
        int hash1 = hash_1(key);
        if (!bits.get(hash1)) {
            return false;
        }
        int hash2 = hash_2(key);
        if (!bits.get(hash2)) {
            return false;
        }
        int hash3 = hash_3(key);
        if (!bits.get(hash3)) {
            return false;
        }
        return true;
    }
    public int hash_1(String key) {
        int hash = 0;
        int i;
        for (i = 0; i < key.length(); ++i) {
            hash = 33 * hash + key.charAt(i);
        }
        return Math.abs(hash) % size;
    }
    public int hash_2(String key) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++) {
            hash = (hash ^ key.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return Math.abs(hash) % size;
    }
    public int hash_3(String key) {
        int hash, i;
        for (hash = 0, i = 0; i < key.length(); ++i) {
            hash += key.charAt(i);
            hash += hash << 10;
            hash ^= hash >> 6;
        }
        hash += hash << 3;
        hash ^= hash >> 11;
        hash += hash << 15;
        return Math.abs(hash) % size;
    }
    public static void main(String... args) {
        // O(1000000000) 8bit= 1byte
        BloomFilter bloomFilter = new BloomFilter(Integer.MAX_VALUE); // 21亿
        System.out.println(bloomFilter.hash_1("1"));
        System.out.println(bloomFilter.hash_2("1"));
        System.out.println(bloomFilter.hash_3("1"));
        bloomFilter.add("1111");
        bloomFilter.add("1123");
        bloomFilter.add("11323");
        System.out.println(bloomFilter.find("1"));
        System.out.println(bloomFilter.find("1123"));
    }
}

LRU缓存实现

public class LRUCache<K, V> {
    private int cacheCapacity;
    private Map<K, CacheNode> existNodeMap;
    private CacheNode head;
    private CacheNode tail;
    public LRUCache(int capacity) {
        this.cacheCapacity = capacity;
        existNodeMap = new HashMap<>(this.cacheCapacity);
    }
    public void put(K key, V value) {
        CacheNode node = existNodeMap.get(key);
        if (node == null) {
            if (this.existNodeMap.size() >= this.cacheCapacity) {
                this.existNodeMap.remove(tail.key);
                removeLast();
            }
            node = new CacheNode();
            node.key = key;
        }
        node.value = value;
        moveToFirst(node);
        existNodeMap.put(key, node);
    }
    public Object get(K key) {
        CacheNode node = existNodeMap.get(key);
        if (node == null) {
            return null;
        }
        moveToFirst(node); // 将当前节点移动到链表头
        return node;
    }
    public void removeLast() {
        if (tail != null) { // 若链表尾部不为空
            tail = tail.prev;
            if (tail == null) {
                head = null;
            } else {
                tail.next = null;
            }
        }
    }
    public Object remove(K key) {
        CacheNode node = existNodeMap.get(key);
        if (node == null) {
            return null;
        }
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        if (node == head) {
            head = node.next;
        }
        if (node == tail) {
            tail = node.prev;
        }
        return existNodeMap.remove(key);
    }
    public void clear() {
        this.cacheCapacity = 0;
        this.existNodeMap.clear();
    }
    private void moveToFirst(CacheNode node) {
        if (node == head) {
            return; // 若为头结点，则不需要做任何操作
        }
        if (head == null || tail == null) {
            head = tail = node;
            return; // 若链表为空
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node == tail) {
            tail = node.prev;
        }
        node.next = head;
        head.prev = node;
        head = node;
        head.prev = null;
    }
}
public class CacheNode {
    public CacheNode prev;
    public CacheNode next;
    public Object key;
    public Object value;
}