转载

用拉链法和线性探测法解决哈希冲突

前言

前面学习到的几种算法比如 红黑树 ， 二叉搜索树 ，查找插入 时间复杂度 最快也只能到 O(logn) .现在介绍一种算法可以使查找插入 时间复杂度 达到常数级别。

散列表(Hash table)

也称为 哈希表 。是字典的一种抽象。比如说你要查一个字，通过这个字的拼音首字母，找到这个字的页码，然后翻到那页找就行了。这种方法直接把查找 时间复杂度 降到了常数。但是要牺牲一定的计算索引的时间。计算索引的那个函数称为 哈希函数 ( 散列函数``)。如果两个不同的 key`算出了同一个索引，此时就要用到一定的方法来解决哈希冲突。

哈希函数

哈希函数 一般具有如下特点。

相等的 key 产生相等的 哈希值
计算简单方便
哈希值 均匀分布。(若过度集中，则容易使效率降低到 o(n) )

构造 哈希函数 有多种方法，这里不详细讲解。

哈希冲突

若两个不相等的 key 产生了相等的 哈希值 ，这时则需要采用 哈希冲突 。

拉链法

Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单，将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

用拉链法和线性探测法解决哈希冲突

实现步骤

得到一个 key
计算 key 的 hashValue
根据 hashValue 值定位到 data[hashValue] 。( data[hashValue] 是一条链表)
若 data[hashValue] 为空则直接插入
不然则添加到链表末尾

这里需要注意的是， 哈希函数 必须保证 哈希值 的 均匀分布 ，若全部集中在一条链表中，则 时间复杂度 和顺序链表相同。

还有一点则是数组的大小，若你能估计数据的大小，则直接指定即可，否则就需要 动态扩充 数组。

实现

public class SeparateChainingHashST<Key,Value> {
        //这里的M需要根据实际情况调整
        public SeparateChainingHashST(int M) {
            this.M = M;
            st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
            for (int i=0;i<M;i++){
                st[i]=new SequentialSearchST<Key,Value>();
            }
        }

        private int hash(Key key){
            return (key.hashCode() & 0x7fffffff) % M;
        }
        public void put(Key k,Value v){
            int hashValue = hash(k);
            st[hashValue].put(k,v);
        }

        public Value get(Key k){
            int hashValue = hash(k);
            return st[hashValue].get(k);
        }
}

线性探测

线性探测 直接使用数组来存储数据。可以想象成一个停车问题。若当前车位已经有车，则你就继续往前开，直到找到下一个为空的车位。

用拉链法和线性探测法解决哈希冲突

实现步骤

得到 key
计算得 hashValue
若不冲突，则直接填入数组
若冲突，则使 hashValue++ ，也就是往后找，直到找到第一个 data[hashValue] 为空的情况,则填入。若到了尾部可循环到前面。

实现

public class LinearProbingHashST<Key,Value> {
    public LinearProbingHashST(int cap) {
        keys = (Key[]) new Object[cap];
        values = (Value[]) new Object[cap];
        M = cap;
    }

    private int hash(Key key){
        return (key.hashCode() & 0x7fffffff) % M;
    }
    public void put(Key key,Value value){
        //若当前数据含量超过了总容量的一半，则重新调整容量
        if(N>=M/2) resize(2*M);  
        int hashValue = hash(key);
        if (values[hashValue]==null){
            keys[hashValue] = key;
            values[hashValue] = value;
            N++;
        }
        else if(keys[hashValue].equals(key)){
            values[hashValue]=value;
        }
        else{
            while (values[hashValue] != null){
                hashValue = (hashValue+1)%M;
            }
            keys[hashValue] = key;
            values[hashValue] = value;
            N++;
        }
    }
    public Value get(Key key){
        int hashValue = hash(key);
        if (keys[hashValue]!=null&&!keys[hashValue].equals(key)){
            while (keys[hashValue]!=null &&keys[hashValue]!=key){
                hashValue = (hashValue+1)%M;
            }
        }
        return values[hashValue];
    }
}

性能比较

一般来说，使用 散列表 会比 红黑树 快很多。但具体还是要看 哈希函数 的计算效率。但是 散列表 无法保证顺序，所以如果你需要进行有关顺序的操作，应该使用 红黑树 或者 二叉搜索树 。

对于 线性探测 来说动态调整数组大小是必要的，不然会产生死循环。

拉链法 的删除操作比较方便，直接链表修改地址即可。而 线性探测 删除操作很复杂，而且 线性探测 耗费的内存比拉链法要多。

分别对四个文件进行插入搜索操作。

tale.txt (779kb)
顺序查找(7.143秒) 二分查找(0.46秒) 二叉搜索树 (0.191秒) 红黑树 (0.237秒) 拉链法 (0.124秒) 线性探测 (0.103秒)
leipzig100k.txt (12670kb)
顺序查找(无) 二分查找(13.911秒) 二叉搜索树 (1.389秒) 红黑树 (1.442秒)
拉链法 (0.707秒) 线性探测 (0.562秒)
leipzig300k.txt (37966kb)
顺序查找(无) 二分查找(60.222秒) 二叉搜索树 (2.742秒) 红黑树 (3.104秒)
拉链法 (1.839秒) 线性探测 (1.559秒)
leipzig1m.txt (126607kb)
顺序查找(无) 二分查找(无) 二叉搜索树 (3.016秒) 红黑树 (2.797秒)
拉链法 (3.938秒) 线性探测 (3.668秒)