数据结构之散列表

需求场景

散列表一种经典的查找的算法，应用于在海量信息中进行高效检索。

简单需求

假设我们需要把10000000个字符串对象存放在数组中，使用什么存放策略能够快速定位某一个字符串的的数组位置，从而实现快速查找的效果?

暴力搜索

根据原始顺序存放，查找时遍历整个数组进行对比，返回匹配对象的下标

暴力搜索

这样的查找方式，最好的情况是第一次查询时就命中，最坏的情况时查询到数组最后的位置才能找到元素。如果数据量非常大，将会占用很长时间。时间复杂度O(N)

代码实现如下：

public class ViolentSerch {
    private int capcity;
    private String[] strs;

    public ViolentSerch() {
        this.capcity = 20000000;
        this.strs = new String[capcity];

        for (int i = 0; i < capcity/2; i++) {
            strs[i] = "str" + i;
        }
    }

    public int getIndex(String str) {
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].equals(str)) {
                return i;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        ViolentSerch search = new ViolentSerch();

        long startTime = System.currentTimeMillis();
        System.out.println("查询str8000000的位置：" + search.getIndex("str8000000"));
        long endTime = System.currentTimeMillis();
        System.out.println("查询消耗时间：" + (endTime - startTime) + "毫秒");

    }
}

这里一开始初始化了一个容量为两千万的String数组，然后往里面插入了一千万个字符串，然后我们查询一个位置靠后的字符串的时间信息如下。所用时间为108毫秒。

查询str8000000的位置：8000000
查询消耗时间：108毫秒

散列表查找

定义一个函数，传进一个对象会返回一个数组的下标，对象存放在这个这个下标位置，下次查找这个对象时，直接根据下标来快速定位到对象的数组位置。

在这里插入图片描述

查找元素则变成如下：

在这里插入图片描述

上述查询思路理论上查询一次就成功，时间复杂度O(1)
把上述代码改为哈希表查询时间如下：

public class HashSearch {
    private int capcity;
    private String[] strs;

    public HashSearch() {
        this.capcity = 20000000;
        this.strs = new String[capcity];

        for (int i = 0; i < capcity/2; i++) {
           String str = "str" + i;
           strs[hash(str)] = str;
        }
    }

    public int getIndex(String str) {
        int index = hash(str);

        if (null == strs[index] || !strs[index].equals(str)) {
            return -1;
        }

        return index;
    }

    private int hash(Object obj) {
        return (obj.hashCode() & 0x7fffffff) % this.capcity;
    }

    public static void main(String[] args) {
        HashSearch search = new HashSearch();

        long startTime = System.currentTimeMillis();
        System.out.println("查询str8000000的位置：" + search.getIndex("str8000000"));
        long endTime = System.currentTimeMillis();
        System.out.println("查询消耗时间：" + (endTime - startTime) + "毫秒");

    }
}

这里数组一开始往里面存的时候会通过hash()方法计算出该对象在数组的位置，然后存储，后面查询字符串的时候也会通过hash()方法计算出字段串的位置，然后比较对象是否相等，相等则返回该对象位置。我们在观察查询时间为1毫秒，对比暴力搜索，时间效率非常高。

查询str8000000的位置：16950247
查询消耗时间：1毫秒

如何实现一个散列表

1.定义一个散列函数，能将对象映射成散列值
2.根据散列值作为对象存放在数组的位置
3.解决散列值冲突

实现散列函数

散列函数的作用是计算出对象的散列值，散列值对应存储容器的索引。
一个散列函数应该满足一下三个条件：

1.一致性------等价的对象必然产生相同的散列值
2.高效性------计算简便
3.均匀性------均匀的散列所有的对象

在java中散列函数就是对应hashcode()方法，所有的类都有hashcode()方法，因为hashcode()方法在Object类定义。

解决散列冲突

散列函数的目标是对所有不同的对象生成不同的散列值，但是无法避免会出现不同的对象产生相同的散列值，即是散列冲突或者散列碰撞。这种情况会导致有不同的对象存储在
容器的同一个位置上。一般有两种方法来解决这个问题，链表法(又称拉链法)和开放寻址法。

1.拉链法
实现方式，如果发现对象的散列值的位置已经存放有元素，则在这个位置放置链表，同时存放相同的元素，下次查找这个索引位置时，在遍历一边数组内容

在这里插入图片描述

2.开放寻址法
当发现一个对象的散列值索引空间已经被占用时，我们直接查找散列表的下一个位置，找到一个没有存放的位置，存放该元素，下次查找时也使用该策略。

在这里插入图片描述

java 中散列表的应用

我们常用的java集合中的HashMap，HashSet的数据结构就是使用的散列表的原理。
java 1.8中HashMap使用的是数组加链表加红黑树的数据结构，当出现散列碰撞时，使用链表来存储碰撞对象，当链表的数据大于8时，为了解决查询性能，会将链表转化成红黑树的结构。

在这里插入图片描述

图片引用自csdn博客

从散列碰撞到java的hashCode()和equals()方法

当有两个不同的对象有相同散列值的时，如何在碰撞的集合中查到相同的对象。
在java中，比较两个对象是否相同用equals()方法，这时候引出java的约定。
如果a.equals(b),那么a.hashcode()必然和b.hashCode()的值一样，所以假设我们重写了个对象的equals()方法时，必须也要重写hashCode()方法。然而，如果a.hashCode()方法和b.hashCode()方法一样，a和b不一定相同，因为可能有hash碰撞的问题。

从散列表到布隆过滤器

前面我们遇到的业务场景是快速在海量数据中查找出某个数据的位置，现在我们遇到另一个业务场景，假设我们需要对全网url进行爬取，这里要考虑去重，对已经爬过的url不再进行处理，经过分析这里只需要查询出数据在不在一个集合里面，我们只需要结果返回是或者否就行了，那么我们可以使用一个boolean数组，前面的存储和查询就变为经过hash计算后在数组所以下面设置true或者false就行了，这样不需要存储对象本身，就大大减少了空间使用。这里的前提是，我们接受哈希碰撞，也就是说，我们接受一定的误判率，对于全网类型的数据采集，这里的碰撞时可以接受的。

布隆过滤器

布隆过滤器使用一个位（bit）数组和多个散列函数来存放数据，位数组初始化时所有位都是0，当需要插入一个元素时，将元素分别经过散列函数出响应索引，然后在对应数组位置设置为1，当需要查询一个元素是否在数组里面时，查询该元素经过散列函数计算后的位置都为1证明元素在里面，否则不存在该元素。

在这里插入图片描述

优缺点

这样我们就可以得出布隆过滤器的优点，因为不存储数据本身，而且只用位数组来存储，所以空间占用减少很多，并且因为不存储数据所以对数据保密。相应的，因为会有hash碰撞，会有误判的后果，同时，因为使用多个hash存储，而考虑会有哈希碰撞的问题，我们不能对里面的数据进行删除，否则会影响到其他数据判断。

使用场景

布隆过滤器适用于在大数据量下面判断元素是否存在，并且可以接受一定的误判了的场景，比如

搜索引擎爬虫爬取数据用于url去重
比特币使用布隆过滤器判断钱包是否同步
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是* 否垃圾邮箱（同理，垃圾短信）
解决缓存击穿，防止攻击

总结

散列表是一种高效的查找算法。