哈希表

哈希表就是一种以键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。基本思想是在记录的存储地址和它的关键字之间建立一个确定的对应关系。这样，不经过比较，一次存取就能得到所需查找元素的查找方法。

哈希函数

将关键字映射为检索表中适当存储位置的函数h(key)。

哈希函数的构造方法：

直接定址法
数字分析法
平方取中法
折叠法
除留余数法
乘余取整法
随机数法

哈希地址

哈希函数h(key)的值为哈希地址

哈希地址冲突

对于两个不同关键字 key1 != key2, h(key1) == h(key2)，两个不同关键字需要同一个存储位置的现象。

处理冲突的方法：

开放定址法

就是把哈希表中的空位置向处理地址冲突开放。具体做法是，当发生地址冲突时，从发生冲突地址位置开始，使用某种方法在哈希表中行程一种探查序列，沿此序列逐个位置查看，知道找到一个空闲位置将记录插入。

产生探查序列的方法有：线性探查法、平方探查法、随机探查法
链地址法

链地址法是将哈希表地址相同的数据元素存储到同一个单链表中。

基于链表的哈希表：

public class MHashTable {
    MLinkList table[];

    /**
     * len是哈希表长度，如果len不是素数，则取大于len的最小素数作为哈希表的长度
     * @param len
     */
    public MHashTable(int len){
        int np;
        if (isPrime(len)) np = len;
        else {
            if (len % 2 == 0) len = len + 1;
            for (np = len; ; np++){
                if (isPrime(np))
                    break;
            }
        }
        table = new MLinkList[np];
        for (int i = 0; i < table.length; i++){
            table[i] = new MLinkList();
        }
    }

    // 哈希函数
    public int hashCode(T key){
        int hc = Math.abs(key.hashCode());
        return hc % table.length;
    }

    //插入
    public void add(T key){
        int ha = hashCode(key);
        table[ha].add(key);
    }

    //删除
    public void remove(T key){
        int ha = key.hashCode();
        table[ha].remove(key);
    }

    //查找
    public T search(T key){
        int ha = hashCode(key);
        return table[ha].search(key);
    }

    /**
     * 判断是否是素数
     * @param n
     * @return
     */
    public static boolean isPrime(int n){
        int m = (int) Math.sqrt(n);
        if (n < 2) return false;
        for (int i = 2; i <= m;="" ++i){="" if="" (n="" %="" i="=" 0)="" return="" false;="" }="" true;="" <="" code="">

哈希查找算法性能

对于哈希表查找，关键字比较的次数取决于产生冲突的次数，而影响冲突产生的因素有：

哈希函数是否均匀
处理冲突的方法
哈希表的装载因子，装载因子定义为：

α = 表中数据元素 / 表的长度

不同处理冲突方法的平均查找长度：

处理冲突方法	查找成功时	查找不成功时
线性探查法	(1/2)* (1 + 1/(1 - α))	（1 + 1 / (1 - α)^2） / 2
平方探查法	-ln(1+α) / α	1 / (1 - α)
链地址法	1 + α/2	α + e^(-α)

哈希映射

映射（Map）概念：Map 建立了两个不同类型数据集之间的一一对应关系，映射可以看成键值对的一个集合或者列表。

串匹配

串模式匹配算法即自串查找，s,p 是两个串，在主串 s 中查找子串的过程称为模式匹配。

简单的模式匹配算法

思路：首先将 s1 与 t1 比较，若不同，就将 s2 与 t1 比较，…,直到 s 的某一个字符 si 和 t1 相同，再将它们之后的字符串进行比较，若也相同，则继续比较，当 s 的某一个字符 si 与 t 的字符 tj 不同时，则 s 返回本趟开始字符的下一个字符，即 s(i-j+2), t 返回 t1，继续下一趟的比较。若 t 中的字符全部比较完毕，则说明本趟匹配成功，否则匹配失败。
BF算法：

/**
     * 简单模式匹配
     * @param s
     * @param p
     * @return
     */
    private int indexBF(char s[], char p[]){
        int i = 0, j = 0;
        while (i < s.length && j < p.length){
            if (s[i] == p[j]){
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 1;
            } // 回溯
        }
        if (j > p.length) return (i - p.length);
        else return -1;
    }

时间复杂度：

s 串长 n , p 串长 m

最好情况：

每趟不成功的匹配都发生在第一对字符比较时，设匹配成功在 si 处，则在前面 i-1 趟中比较了 i-1 次，第 i 次匹配成功比较 m 次, 总共比较 i - 1 + m 次。所有匹配成功的可能共有 n - m + 1 种，等概率 pi = 1 / (n - m + 1)。因此最好情况平均比较次数为：

∑pi * (i - 1 + m) = (n + m) / 2  （1 =< i <= n - m + 1）

复杂度： O(n+m)

最坏情况：

每趟不成功的匹配都发生在 p 的最后一个字符，前 i-1 趟比较 (i-1) m, 第 i 趟比较 m 次，总共比较 im 次，因此：

∑pi * (i * m) = m*(n - m + 2) / 2

复杂度：O（n*m）

KMP算法

复杂度：O（n*m）,一般情况下，实际执行时间是 O（n+m）。