文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > Java中的哈希表
侵权投诉

Java中的哈希表

Java中的哈希表

我们可以看到在hashmap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合,所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表。

所以我们首先想到的就是把hashcode对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,能不能找一种更快速,消耗更小的方式那?java中时这样做的: /**

* Returns index for hash code h.

*/

static int indexFor(int h, int length) {

return h & (length-1);

}

首先算得key得hashcode值,然后跟数组的长度-1做一次“与”运算(&)。看上去很简单,其实比较有玄机。比如数组的长度是2的4次方,那么hashcode就会和24-1做“与”运算。很多人都有这个疑问,为什么hashmap的数组初始化大小都是2的次方大小时,hashmap的效率最高,我以2的4次方举例,来解释一下为什么数组大小为2的幂时hashmap访问的性能最高。

看下图,左边两组是数组长度为16(2的4次方),右边两组是数组长度为15。两组的hashcode均为8和9,但是很明显,当它们和1110“与”的时候,产生了相同的结果,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,8和9会被放到同一个链表上,那么查询的时候就需要遍历这个链表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为15的时候,hashcode的值会与14

Java中的哈希表

(1110)进行“与”,那么最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!

所以说,当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。

所以,在存储大容量数据的时候,最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话,也会以大于且最接近指定值大小的2次幂来初始化的,代码如下(HashMap的构造方法中): public HashMap(int initialCapacity, float loadFactor) {

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal initial capacity: " +

initialCapacity);

if (initialCapacity > MAXIMUM_CAPACITY)

initialCapacity = MAXIMUM_CAPACITY;

if (loadFactor <= 0 || Float.isNaN(loadFactor))

上一页第3页

你可能喜欢

热门文档

相关文档

  • JAVA哈希表

    一般认为从元素查找元素 所对应的存储位置最快方式是采用哈希表。 2. 哈希表类 Java.util.Hashtable 实例对象的元素主要由关键字与 值两部分组成 (这里关键字与...

  • java中hashcode()和equals()的详解

    于是,Java 采用了哈希表的原理。哈希(Hash)实际上 是个人名,由于他提出一哈希算法的概念,所以就以他的名字命名了。哈希算法 也称为散列算法,是将数据依特定算法...

  • JAVA哈希表操作

    import java.util.*; /** * Title: 哈希表操作 * Description: 这是一个权限认证的例子,使用了哈希表作为数据的存储 * Copyright: Copyright (c) 2003 * F...

  • Java编程中的Hash表类

    Java编程程序中默认的类加... 2页 免费 Java编程进阶类 2页 免费喜欢此文档的还喜欢 Java中的哈希表 7页 1财富值 Hash表分析以及Java实现 12页 免费 JAVA...

  • java中hashcode()和equals()的详解

    于是,Java 采用了哈希表的原理。哈希(Hash)实际 上是个人名,由于他提出一哈希算法的概念,所以就以他的名字命名了。哈希算 法也称为散列算法,是将数据依特定算法...

  • Java中hashCode的作用

    支持该方法是为哈希表提供一些优点,例如, java.util.Hashtable 提供的哈希表。 2. 3. hashCode 的常规协定是: 4. 在 Java 应用程序执行期间, 在同一对象上...

  • java中的hashCode方法

    在线互动式文档分享平台,在这里,您可以和千万网友分享自己手中的文档,全文阅读其他用户的文档,同时,也可以利用分享文档获取的积分下载文档

  • java中的hashtable的实例讲解

    java中的hashtable的实例讲解_IT/计算机_专业资料。f91 Java中的Hashtable的...每次给哈希表添加一个新的条目时,计数就被更新,当计数超过临界值时,表被重新...

  • java中的hashCode方法

    在线互动式文档分享平台,在这里,您可以和千万网友分享自己手中的文档,全文阅读其他用户的文档,同时,也可以利用分享文档获取的积分下载文档

  • Java中HashSet的一般用法

    在线互动式文档分享平台,在这里,您可以和千万网友分享自己手中的文档,全文阅读其他用户的文档,同时,也可以利用分享文档获取的积分下载文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email