网站建设资金投入分析,企业管理网站建设,wordpress文件上传,平面设计模板一.什么是散列 散列使用一个散列函数#xff0c;将一个键映射到一个索引上。散列非常高效。使用散列将耗费O(1)时间来查找、插入、及删除一个元素。 映射表是一种用散列实现的数据结构#xff0c;映射表是一种存储条目的容器#xff0c;每个条目包含两个部分#xff1a;一个…一.什么是散列 散列使用一个散列函数将一个键映射到一个索引上。散列非常高效。使用散列将耗费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使用linkedListjava.util.TreeMap使用红黑树。 二.散列函数和散列码 1.散列函数将键映射到散列表的索引上的函数称为散列函数hash function。理想的将每个搜索的键映射到散列表中的不同索引上这样的函数称为完美散列函数。然而很难找到一个完美的散列函数当两个或更多的键映射到一个散列值上的时候我们称之为产生了一个冲突(collision)。 典型的散列函数首先将搜索键转换成为一个整数值称之为散列码。然后将散列码压缩为散列表中的索引。 2.equals和hashCodeJava的根类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^(key32)); 对于double类型的搜索键首先使用Double.doubleToLongBits方法转为long值再执行折叠操作。 4.字符串类型的散列码一个比较直观的方法是将所有字符的unicode求和作为字符串的散列码。这个方法可能有较大的冲突也无法区分dog与dgo。一个更好的方法是考虑字符的位置然后产生散列码 这里Si为s.charAt(i)这个方法被称为多项式散列码。计算时对于长的字符串会导致溢出但Java中会忽略溢出。要最小化冲突关键是选择合适的b实验显示b较好的取值为3133,37,3941。 java.lang.String.java中的多项式散列实现 /*** Returns a hash code for this string. The hash code for a* {code String} object is computed as* blockquotepre* 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* ii/ith 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^(h20)^(h12);return h^(h7)^(h4);
} 完整的散列函数 h(hashCode) supplementalHash(hashCode)%N 这个式子与下面式子一样 h(hashCode) supplementalHash(hashCode) (N-1) 三. 开放地址法 当两个键映射到散列表中的同一个索引冲突发送通常有2种方法处理冲突开放地址法与链地址法。开放地址法有以下几个变体。1.线性探测线性探测法在发生冲突时按顺序找到下一个可用的位置。连续冲突时继续按序检查直到找到可用位置。当探测到表的终点时则返回表的起点。因此散列表被当成是循环的。 线性探测法容易导致散列表中连续的单元组被占用。这样的每个组称为一个簇(cluster)。 2.二次探测线性探测法从索引k的位置检查连续单元二次探测法则从索引为(kj^2)%N位置开始检查其中j0。二次探测法避免了线性的成簇问题但有自己本身的成簇问题称为二次成簇即产生冲突的条目将采用同样的探测序列。 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 130.*/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://www.cnblogs.com/GGGong/p/11048259.html
