散列之HashTable学习(转)

1,什么是散列?

 

 

举个例子,在日常生活中,你将日常用品都放在固定的位置,当你下次需要该东西时,直接去该地方取它。这个过程就相当于散列查找。

 

 

若将它们随意杂乱无章地存放,当需要某件东西时,只能一个地方一个地方地逐一查找,这就相当于顺序查找。

 

 

在数据结构中,数组就相当于一张散列表,因为可以根据数组下标索引直接取得该位置上的元素。

 

 

2,什么情况下用到散列?

 

 

由于散列查找相对于其它查找而言,理论上只需要O(1)时间就可以找到某元素,因此,当查找是主要的任务时,散列就是实现词典的一种很好的选择。

 

 

3,散列函数的理解

 

 

散列查找中,需要提供一个查找键,根据该查找键来寻找值---(KEY,VALUE)....而在实际应用中,查找键描述的是现实世界中对象的性质,它不合适直接用来作为Valu(值)的索引(索引一般是整数)。其次,查找键的范围可能很大,但是用来计算机的存储是有限的。基于以上两个原因,需要使用散列函数将查找键转化为某个元素的索引。对于一个典型的散列函数,执行以下两个步骤:

 

 

①     将查找键转换为一个称为散列码的整数-------解决索引问题

②将散列码压缩到散列表的索引范围------解决存储限制

 

 

4,在Java中,JDK类库String类的对象的hashCode是这样生成的:

 

 

对于字符串s而言,它的hashCode是基于每个字符unicode值乘以一个基于该字符在字符串中位置的因子g(其中 g=31)

 

 

如: s = u(0)u(1)……u(n-1)

 

 

散列码hash = u(0)*g^(n-1) + u(1)*g^(n-2)+……+u(n-2)*g+u(n-1),该多项式使用 Horner方法 可以写成一种等价的代数形式。该代数形式的多项式求值用程序表示如下:

int hash = 0;
        int n = s.length();
        for(int i = 0; i < n; i++)
            hash = g*hash + s.charAt(i);

 

 

5,JDK中对于64位long类型对象作为key的hashCode码按照如下方法生成:

int(key^(key>>32))

 

 

key一共有64位,首先将key右移32位(高32位补0),原来的key低32位的值被丢弃,再进行异或运算,就可以合并64位查找键的低32位的值和高32位的值(key中高32位的bit与低32位的bit异或),再运行强制类型转换,将结果转化成32位的值。这样就可以将一个64位的key结合它的每一位的值来获得一个32位的hashCode散列码。

 

 

6,散列表长度问题

 

 

散列表的长度不能为偶数,why?因为在将散列码压缩为散列表的索引时,通过是使用取模计算---c%n(c 为散列码,n 为散列表长度)

 

 

当 n 为偶数时,c%n 的奇偶性与 c 的奇偶性相同,若散列码偏奇数或者偶数(内存地址的散列码通常是偶数)这样得到的索引很难是均匀分布的。因此散列表的长度通常取奇数,最好取素数。

 

 

7,散列冲突的处理

 

 

这个知识点可以单独写一篇文章了。当在词典中插入元素时,若散列函数将查找键映射到一个已经使用的位置,则需要为该查找键相关联的值寻找另一个位置,有两种思路,一是使用散列表中的另一个位置。二是修改散列表的结构,使得散列表中的每个位置可以表示多个值。

 

 

这样列下散列冲突的处理类型分两种:

 

 

①开放定址法---对应第一种思路,总是为冲突的key在散列表中寻找下一个“未被使用”的位置。

②链地址法-----对应第二种思路,每个散列表中的位置可以指向一个链表,该链表称为桶。每个桶中则可以存放多个value。(将冲突的key对应的value插入到链表中)

 

 

开放定址法又分为三种情况:

 

 

❶线性探测开放定址----易产生一次聚集现象,即多个key问题被hash到同一个索引位置上。对于每个(key,value)只要表不满,总可以找到一个位置存放。

❷二次探测开放定址

❸再散列法---对冲突的key再进行一次hash。

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-28 10:16
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议