Java中的HashMap浅析-阿里云开发者社区

开发者社区> 青衫无名> 正文

Java中的HashMap浅析

简介:
+关注继续查看
在Java的集合框架中,HashSet,HashMap是用的比较多的一种,顺序结构的ArrayList、LinkedList这种也比较多,而像那几个线程同步的容器就用的比较少,像Vector和HashTable,因为这两个线程同步的容器已经不被JDK推荐使用了,这是个比较老式的线程安全的容器,JDK比较推荐的是采用Collections里面的关于线程同步的方法。
    问题来源:
1.为什么要有HashMap?
    《Thinking In Java》里面有一个自己采用二维数组实现的保存key-value的demo,书上也说到性能问题,因为从数据结构的顺序结构的观点来看,常规的线性存储,你弱需要找到其中的某个元素,就需要遍历这个链表或者数组,而遍历的同时需要让链表中的每一个元素都和目标元素做比较,相等才返回,Java里面用equals或者==。这对性能是毁灭性的伤害。
    2.HashMap的优势是什么?
    Hash算法就是根据某个算法将一系列目标对象转换成地址,当要获取某个元素的时候,只需要将目标对象做相应的运算获得地址,直接获取。
    3.Java中的Hash?
    事实上Java的数据无非就三种,基本类型,引用类型(类似C里面的指针类型)和数组,有些地方说是2种类型,只有引用类型和数组。通过这三种数据类型可以构建出任何数据结构。在Java中,ArrayList这种底层就是用Objec数组来构建的,而HashMap也是用数组来构建,只不过数据数组的数据类型是一个叫做Entry的内部类来保存key、value、hash(不是hashCode)和next(也就是链表的下一个元素)。其实HashSet也是HashMap,只不过比较特殊,没有使用Entry的value而只用了key而已。看看HashSet的构造方法:
    public HashSet() {
    map = new HashMap<E,Object>();
    }
    所以从这个意义上来讲就没必要讨论HashSet了,他只不过是特殊的HashMap而已。
    HashMap详解:
    基调:由于通过hash算法产生的逻辑地址可能导致冲突,所以对于一个长度为length的数组,里面存放小于length个数据元素的时候就有可能出现冲突的现象,因为比如说要在长度为16的数组中存放字符串(也就是一个空的HashMap默认的长度),每个字符串通过调用自身的hashCode()方法会得到该字符串的hashCode,然后通过HashMap的这两个方法会算出在数组中的位置,也就是下面的 i。
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    任意字符串的hashCode通过上面2个方法都会得到一个i,这个i就是在数组中的位置,这里比较巧妙的设计就是indexFor(hash,table.length)这个方法:
    static int indexFor(int h, int length) {
    return h & (length-1);
    }
    这个方法里面的任意h与(length-1)做位运算之后得到的值始终都是在length之内的,也就是在数组table之内,因为拿任意一个数来和另一个数来做与运算,结果肯定是小于等于较小的哪一个数,我以前第一次看到这就比较震惊,为什么那些人能想出这么巧妙的计算在table中的位置的方法。与此同时,既然字符串调用hashCode()会得到一个值,那么就会出现不相同的字符串调用hashCode方法之后得到的值是一样的,这种可能性是存在的,而且几乎肯定是存在的。这时候就需要在数组的某个位置增加一个链表结构,用户存储相同的hashCode的字符串,而这个时候HashMap的size同样也会自增1,尽管这2个字符串只有一个存在于数组中。HashMap中的size变量有两个作用,第一是通过调用size()方法来返回map的长度,
    public int size() {
    return size;
    }
    第二个作用相当重要,就是解决hash算法的核心力量,解决冲突。在HashMap的构造方法中可以看出,hashmap的长度和底层数组table都是capacity,但是还有一个变量叫做threshold,极限值,阈值的意思,默认情况的构造方法:
    public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
    }
这个阈值就是数组长度和加载因子的乘积,这东西有什么用呢,假设都按照默认情况来看,默认构造方法构造出来的hashmap长度为16,底层数组长度也为16,而阈值
    threshold长度为12,因为默认加载因子是0.75。也就是说当箱map中存放12个元素是,map的结构没什么变化,但是当存储第13个的时候,table就需要扩容了,扩大为原来的2倍。这时候是什么结局呢,如果加载因子是1,那么map中存放16个的时候他是不会扩容的,table.length = 16,而为0.75的时候存放16个数据的时候table.length = 32。那么同样是存放16个数据,分别在长度为16的数组和32的数组中存放,出现冲突的几率一般来说16的数组要大一些,那为什么会大一些呢,因为某个数据存放进入数组的位置是根据
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    这两个方法算出来的,其中就包括table.length,换句话说,位置i跟hash和table.length是相关的,也就是说位置i与table.length是联动的,换个角度,存放的16个数据假设是固定的,而得出hashCode的算法也是固定的,那么位置i就只跟length的大小有关联了,一般来说length越大,数据的冲突几率就低一些,在map.getValue(key)的时候需要在链表中比较的次数就少一些,性能就高一些。这就是Java中hashmap的性能因素,一般来说加载因子factor大,同样个数的数据所占用空间就越小,table.length就越小,冲突几率就越大,反之空间利用率低,性能高,类比一下,比如你地上放了10个碗,你手里面握了10颗大米,你撒下去,前提是必须10颗米都要撒进碗里,你是不是会发现有些碗里面装了两颗三颗,而有些碗是空的,接下来,你在地上摆20个碗,还是撒10颗米下去,依然是所有的米都要进碗,依然还是会出现有些晚是空的,有些是一颗两颗三颗这种现象,但是很明显一般来讲20个碗的时候每个碗里面装不止一颗的情况要比10个碗的情况要少,当然也不一定完全是这样,但是一般来说是这样,这就是hash算法,如果设计的好的情况下我们希望每个碗里面都最多放一颗进去,但是这种情况比较少见,但不管怎么说,按照普遍情况来看,20个碗的装多颗的情况是比10个碗装多颗的情况要少一点。从数据结构的角度来说叫做用空间换时间的策略,以空间换时间何止hash算法,双向链表也是用空间换时间的策略。至于说为什么默认是0.75,我估计这个是前辈们和科学家们总结出来的一个这种的办法,空间利用率比较不错的同时性能比较令人接受吧。
    顺便说一下啊,当我们不断的往一个hashmap里面添加数据的时候,如果超过某个阈值,他就会扩容,扩容的同时会让之前的所有元素重新生成地址,并且把原来的数组里面的数据迁移到新的数组中(新的数组容量是原来的两倍长度)。顺便说下,这个数据迁移其实对性能损耗还是相当大的,毕竟你是要复制数组,同时要重新构建每个元素的在table中的位置,因此我们可以在使用hashMap之前大概的估算一下这个hashMap里面大概会存多少个元素,这样就可以在new hashmap的时候就给定他的容量,这样数据迁移的次数相对就少一些,性能就更好一点。
    接下来从JDK的源码来看看HashMap。
    1.构造出一个空的HashMap。默认长度16,底层Entry数组也是16的默认长度。默认加载因子default_factor为0.75。阈值16*0.75=12。key和value都存在与Entry这个类型里面。
    public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
    }
    2.调用put方法。
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

    首先是判断key是否为空,如果为空,那么调用下面这个方法,这个方法说明,HashMap的null的key始终是存放在table的table[0]位置的,不管table[0]位置有没有冲突都是这样。
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}

    如果不为空,那么继续,这里,如果算出来的位置i出已经有元素了,说明冲突了,那么遍历冲突链表,如果发现key相等,那么直接用新的value替换掉就的value并且返回旧的value。这里只判断相等的情况而不判断不相等的情况,也就是这里不做添加操作。
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

    接下来,上面的步骤说明,新添加的数据在位置i处不是key相等的情况,就真正的添加数据了。调用addEntry(hash, key, value, i)方法。
    void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
    resize(2 * table.length);
    }
    此时把新的添加进table[i]位置,而原来的数据(可能是null也可能是一个链表)的引用直接存放进新的数据的next中。形成新的链表。
    接下来就是调用map的get(key)方法了。这个过程和put方法是逆向的。
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

    首先判断key == null, 如过为true,那么调用getForNullKey()方法。遍历table[0]出的链表,因为空key是存在table[0]处的。前面说到。
    private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
    if (e.key == null)
    return e.value;
    }
    return null;
    }
    如果key == null 为false,那么上面get方法的下半部分,通过hashCode算出hash,通过hash和table.length算出位置i,遍历table[i]处的链表,ken相等,取出数据。
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;

    这里还有一个Java里面的规定,就是2个对象的equals相等,那么hashCode也必须相等。但是hashCode相等equals不一定相等。这是hashmap存在于Java里面的依据,同时这就是为什么会有冲突的原因了,两个不一样的对象计算出来的hashCode相等的原因。如果2个对象equals相等,但是hashcode不想等,那就说明这2个元素都能存进hashmap,但是很明显hashmap里面的key是唯一的,直接就推翻了hashmap。
    写得比较粗糙,HashMap里面的很多细节都没写,主要是因为一来我们只需要用HashMap就行了,二来是细节源码里面都有,看一下就知道了。


最新内容请见作者的GitHub页:http://qaseven.github.io/

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10089 0
使用OpenApi弹性释放和设置云服务器ECS释放
云服务器ECS的一个重要特性就是按需创建资源。您可以在业务高峰期按需弹性的自定义规则进行资源创建,在完成业务计算的时候释放资源。本篇将提供几个Tips帮助您更加容易和自动化的完成云服务器的释放和弹性设置。
12077 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13892 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
9161 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
4660 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
4508 0
+关注
3598
文章
840
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载