散列_散列通复方对乙酰氨基酚片

散列_散列通复方对乙酰氨基酚片一.什么是散列 散列使用一个散列函数,将一个键映射到一个索引上。散列非常高效。使用散列将耗费O(1)时间来查找、插入、及删除一个元素。 映射表是一种用散列实现的数据结构,映射表是一种存储条目的容器,每个条目包含两个部分:一个键(key)和一个值(value)。键又称为搜索键用于查找对应的值。映射表(

一.什么是散列

散列使用一个散列函数,将一个键映射到一个索引上。
散列非常高效。使用散列将耗费O(1)时间来查找、插入、及删除一个元素。

映射表是一种用散列实现的数据结构,映射表是一种存储条目的容器,每个条目包含两个部分:一个键(key)和一个值(value)。键又称为搜索键用于查找对应的值。
映射表(map)又称为字典(dictionary)、散列表(hash table)或者关联数组(associate array)。

Java合集框架定义了java.util.Map接口,三个具体的的实现为java.util.HashMap、java.util.linkedHashMap以及java.util.TreeMap。java.util.HashMap使用散列实现,java.util.linkedHashMap使用linkedList,java.util.TreeMap使用红黑树。

 

二.散列函数和散列码

1.散列函数
将键映射到散列表的索引上的函数称为散列函数(hash function)。理想的,将每个搜索的键映射到散列表中的不同索引上,这样的函数称为完美散列函数。然而,很难找到一个完美的散列函数,当两个或更多的键映射到一个散列值上的时候,我们称之为产生了一个冲突(collision)。

典型的散列函数首先将搜索键转换成为一个整数值,称之为散列码。然后将散列码压缩为散列表中的索引。

2.equals和hashCode
Java的根类Object具有hashCode方法,返回一个整数的散列码。默认的,该返回值是一个该对象的内存地址。hashCode一般有如下约定:
1)当equals方法被重写时,应该重写hashCode方法,以保证两个相等的对象返回同样的散列码。
2)程序执行中,如果对象的数据没有被修改,则多次调用hashCode将返回同样的整数。
3)两个不相等的对象可能具有同样的散列码,但是应该在实现hashCode方法时避免太多这样的情形出现。

3.基本数据类型的散列码
对于byte、short、int、char类型,简单讲它们转为int,这些类型中的任何一个不同的搜索键将有不同的散列吗。
对于float,使用Float.floatToIntBits(key)作为散列码,方法返回一个int值。该值得比特表示和浮点数f的比特表示相同。

对于long类型的搜索键,简单地转为int不是很好的选择,因为无法反应前面32高位的不同。考虑到这种情况,将64比特分为两部分,并执行异或操作将两部分结合,这个过程称为折叠(folding)。
一个long类型键的散列码为:

int hashCode=(int)(key^(key>>32));

对于double类型的搜索键,首先使用Double.doubleToLongBits方法转为long值,再执行折叠操作。

4.字符串类型的散列码
一个比较直观的方法是将所有字符的unicode求和作为字符串的散列码。这个方法可能有较大的冲突,也无法区分dog与dgo。
一个更好的方法是考虑字符的位置,然后产生散列码:

散列_散列通复方对乙酰氨基酚片

这里Si为s.charAt(i),这个方法被称为多项式散列码。计算时,对于长的字符串会导致溢出,但Java中会忽略溢出。要最小化冲突,关键是选择合适的b,实验显示,b较好的取值为31,33,37,39,41。

java.lang.String.java中的多项式散列实现:

/** * Returns a hash code for this string. The hash code for a * {@code String} object is computed as * <blockquote><pre> * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] * </pre></blockquote> * using {@code int} arithmetic, where {@code s[i]} is the * <i>i</i>th character of the string, {@code n} is the length of * the string, and {@code ^} indicates exponentiation. * (The hash value of the empty string is zero.) * * @return a hash code value for this object. */
    public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; }

5.压缩散列码
键的散列码可能是一个很大的整数,超过了散列表索引的范围,因此需要将它缩小。假设散列表的索引处于0到N-1之间,常用的压缩做法是:
h(hashCode)=hashCode%N

保证索引均匀扩展,选择N大于2的素数。

上面的式子等价于:
h(hashCode)=hashCode&(N-1)

为保证散列是均匀分布的,java.util.HashMap的实现中采用了补充的散列函数与主散列函数一起使用:

private static int supplementalHash(int h){ h^=(h>>>20)^(h>>>12); return h^(h>>>7)^(h>>>4); }

完整的散列函数:

h(hashCode)= supplementalHash(hashCode)%N

这个式子与下面式子一样:

h(hashCode)= supplementalHash(hashCode) &(N-1)

 

三. 开放地址法

当两个键映射到散列表中的同一个索引,冲突发送,通常有2种方法处理冲突:开放地址法与链地址法

开放地址法有以下几个变体。
1.线性探测
线性探测法在发生冲突时,按顺序找到下一个可用的位置。连续冲突时继续按序检查,直到找到可用位置。
当探测到表的终点时,则返回表的起点。因此,散列表被当成是循环的。
散列_散列通复方对乙酰氨基酚片

线性探测法容易导致散列表中连续的单元组被占用。这样的每个组称为一个簇(cluster)。

2.二次探测
线性探测法从索引k的位置检查连续单元,二次探测法则从索引为(k+j^2)%N位置开始检查,其中j>=0。
散列_散列通复方对乙酰氨基酚片
二次探测法避免了线性的成簇问题,但有自己本身的成簇问题,称为二次成簇,即产生冲突的条目将采用同样的探测序列。

3.再哈希法
避免成簇问题的另一个方法是再哈希法。

 

 

四. 链地址法
链地址法将具有相同的散列索引的条目都放在一个位置,每个位置使用一个桶来放置这些条目。
散列_散列通复方对乙酰氨基酚片

 

链地址法是种广泛使用的方法。
(在JDK中有不少基于此方法的实现,如jdk1.7的hasMap实现方案,在多线程环境中发生链循环等错误,jdk1.8中重写了链的处理,修正了此错误等故事。)

 

五. 装填因子和再散列
装填因子(load factor)衡量一个散列表有多满。如果装填因子超出,则增加散列表的大小,并重新装载条目到一个新的更大的散列表中,这称为再散列。
装填因子=条目数n/容量N,如果散列表满了,装填因子=1
当装填因子接近1时,冲突的可能性就增大。一般对于开发地址法,装填因子需要控制在0.5下,链地址法通常维持在0.9下。

在java.util.HashMap的实现中,采用了装填因子0.75的阈值。一旦超过阈值,就需要增加散列表的大小,并进行再散列。再散列的代价比较大,为避免频繁的再散列,一旦扩容时应该至少将散列表的大小翻倍。

/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
    static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

 

今天的文章散列_散列通复方对乙酰氨基酚片分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/46902.html

(0)
编程小号编程小号
上一篇 2023-09-05
下一篇 2023-09-05

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注