Hash表的基本原理及其应用 |
您所在的位置：网站首页 › Hash表是什么 › Hash表的基本原理及其应用 |
Hash表的基本原理及其应用
|
内容：Hash表的基本原理及概念，常见的Hash函数及处理冲突的方法，Hash表的应用场景 文章目录 Hash表是什么？Hash表的基本原理为什么Hash表无序，且不可重复常见的Hash函数1. 直接定址法2. 除留余数法3. 数字分析法4. 平方取中法5.Java8中的Hash函数 常见的处理冲突的方法1. 开放定址法1.1 线性探测法1.2 平方探测法1.3 再散列法1.4 伪随机法 2.拉链法 用上述解释实际问题1. 为什么HashSet感觉是有序的2. Hash表优化程序性能3. Redis中的Hash应用 Hash表是什么？Hash表也叫散列表，就是一组数据集合，像List一样，就是存储一组数据，但是它有自己独特的方式。比如在Java中，HashSet与ArrayList一样，都是Collection集合的子类。 Hash表的基本原理假设现在有一组数据 61，12，46，13，17，28，19，70如果我们想找里面是否包含28的话，可以将其放入ArrayList中，然后从第一个开始遍历，判断每一项是否与28相等。 那有没有什么方法，不用遍历，瞬间就可以知道这个集合中是否包含28呢。使用Hash表可以解决这个问题。 假设有一个Mod，它的作用是取余 Mod(x) = x % 10我们初始化一个大小为10数组arr，初始值都为0 01234567890000000000此时，我们对于上面的数字，先进行取余操作，然后根据余数，将其放入对应数组下标中。如： Mod(61) = 61%10 = 1所以应该放在61放在arr[1]中。将上述所有数据放入数组中，则如下图所示 0123456789706112130046172819此时，如果要查询28是否在这个集合中，则只需要先对28取余，得到8，然后判断arr[8]是否等于28即可。这样就是就是实现了快速查找。时间复杂度仅为O(1)。 上述描述中，Mod函数被称为 Hash函数，也叫散列函数 假设现在又来了一个数字，为38，取余后，也得8，但是此时arr[8]已经被占用了。那么这种现象就称为冲突。 Hash表要解决的最大的两个问题就是： 如何选择Hash函数，原则是：尽可能等概率，均匀分布，减少冲突如何解决冲突 为什么Hash表无序，且不可重复为什么无序： 对于无序，通过上面的基本原理，应该已经可以理解了。对于数据存放在数组中的什么位置，并不是按照先后顺序来得。而是由Hash函数决定的，所以取不同的Hash函数，最终数据就会有不同的顺序。对于复杂的Hash函数，用户也很难预估最终的的顺序，而且没必要 为什么不可重复：上述例子中，Hash表中存储的是数字，但实际应用中，通常存入Hash表的数据比较复杂，比如存入Hash表的是学生信息，在计算Hash值时，不会对整个学生信息进行Hash，而是选用学生信息的关键字，求该关键字的Hash值。在Java中，一般使用hashcode作为关键字。这样的话，两条记录的关键字一定不同，若相同，则会覆盖。假设若不覆盖，而是都存下来，这样在查找的时候，就不知道该返回哪个了。 常见的Hash函数 1. 直接定址法直接取关键字作为Hash值，或进行线性变换后的值作为Hash值 H(key) = key 或 H(Key) = a × key + b这种方法实现简单，不会产生冲突。但是会造成空间的极大浪费。 2. 除留余数法假定表长为m，取一个不大于m，且接近m的质数p，然后对p求余。 H(key) = key % p 3. 数字分析法分析要被散列的集合，取相对随机的部分作为散列结果。如，要散列的数据的关键字为身份证号： 412314199607207598 // 6位地区+8位生日+4位随机数 4. 平方取中法将关键字平方后，取中间几位作为散列地址。具体取多少，视情况而定。这样的好处是，散列地址与关键字每位都有关系，所以分布相对比较均匀。 5.Java8中的Hash函数 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } 常见的处理冲突的方法 1. 开放定址法计算hash地址后，发现该地址已经被占用了，那么就找其他的，不属于它的位置，然后放进去。比如：hash函数为对8取余。那 hash(1) =1 和hash(9) = 1，假设先来后到，1先来，那么9就冲突了，那么9就可以放在其他位置，比如放在2位置。 对于放在哪个位置，又可以有下面几种方法： 1.1 线性探测法就是依次往后探测，直到找到一个可以存放的位置。比如，hash(9)=1, 但是1位置已经被占了，那就看看2有没有，如果2也被占了，那就看3，依次类推。 缺点是会出现大量元素在相邻的散列地址上“聚集”，造成查找效率低下 1.2 平方探测法探测的顺序为 0 2 , 1 2 , − 1 2 , 2 2 , − 2 2 ， ⋯ 0^2, 1^2,-1^2,2^2,-2^2，\cdots 02,12,−12,22,−22，⋯ 假设数组长度为20，目前10位置冲突了，那么往后找的时候，分别找 11,9,14,6，依次类推。 优点为可以避免堆积，缺点为不能探测Hash表上的所有位置 1.3 再散列法用另一个Hash函数求出探测时的增量 1.4 伪随机法增量使用随机数 2.拉链法如果Hash地址一样，那么就依次往后排，按先来后到的方式。就像这个样子。可以使用数组，也可以使用链表。
https://blog.csdn.net/zhaohongfei_358/article/details/108639236 2. Hash表优化程序性能假设目前有一个业务，需要两层或更多层for循环，在最里层需要对某个集合进行contains操作，判断是否包含。 private static void contains(Collection e, Object value) { int cycleNumber = 1000; // 双层for循环查找value值 for (int j = 0; j < cycleNumber; j++) { for (int i = 0; i < cycleNumber; i++) { e.contains(value); } } }这个时候，若传过来的Collection是HashSet或ArrayList，则执行效率会大不相同。 当Collection数据为1w时，两层for循环(1000*1000)，所消耗的时间。若数据更大，则消耗时间则是指数级增长。 HashSet查找所耗费的时间：15ms ArrayrList查找所耗费的时间：11943ms 3. Redis中的Hash应用都说Redis快，一问为什么快。基本上都会回答，Redis是基于内存的等等。但这些都是次要的。但Redis快的根本原因是因为它的数据存储方式是Hash表。 Redis有16383个Hash槽（Hash地址）。当进行get操作时，Redis会首先对Key进行Hash，求出这个Key是存放在哪个槽中的。然后直接到那个槽中去取。这样，get操作的时间复杂度就是O(1)。所以可以做到对一个key的瞬间存取。 |
Jdk1.7中采用的就是拉链法【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |