哈希拉链法

﹏ヽ暗。殇╰゛Y 2022-05-09 14:33 201阅读 0赞

# [哈希拉链法][Link 1] #

## 前言 ##

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

## 散列表(Hash table) ##

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

## 哈希函数 ##

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

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

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

## 哈希冲突 ##

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

### 拉链法 ###

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

![yYv2uuU.jpg_web][]

实现步骤

*  得到一个 `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);
            }
    }

### 线性探测 ###

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

![UbAj2iQ.jpg_web][]

实现步骤

*  得到 `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秒)

![QBjMJr.jpg_web][]

[Link 1]: https://www.cnblogs.com/sanjianghuiliu/p/6524895.html
[yYv2uuU.jpg_web]: http://img0.tuicool.com/yYv2uuU.jpg!web
[UbAj2iQ.jpg_web]: http://img2.tuicool.com/UbAj2iQ.jpg!web
[QBjMJr.jpg_web]: http://img0.tuicool.com/QBjMJr.jpg!web