浅谈hashmap为什么查询时间复杂度为O(1)

网友投稿 1734 2022-12-23

浅谈hashmap为什么查询时间复杂度为O(1)

浅谈hashmap为什么查询时间复杂度为O(1)

hashmap为什么查询时间复杂度为O(1)

Hashmap是java里面一种类字典式数据结构类,能达到O(1)级别的查询复杂度,那么到底是什么保证了这一特性呢,这个就要从hashmap的底层存储结构说起

下来看一张图:

上面就是hashmap的底层存储示意图,要想FJyvZrMU查看一个键值对应的值,首先根据该键值的hash值找到该键的hash桶位置,即是tab[2]还是tab[1]等,计算某个键对应的哈希桶位置很简单,就是

int pos = (n - 1) & hash,也就是hash%n,因为位运算效率高所以在hashmap实现时使用的是位运算这种方式,需要注意的是哈希桶的数量必须是2^n,所以hashmap一旦扩容必定是哈希桶数量翻番。

通过上面的描述,我们可以知道,根据键值找到哈希桶的位置时间复杂度为O(1),使用的就是数组的高效查询。但是仅仅有这个是无法满足整个hashmap查询时间复杂度为O(1)的。hashmap在处理哈希冲突的方式如上图所示的拉链法,在冲突数据没有达到8个以前该哈希桶内部存储使用的是链表的方式,当某个哈希桶的数据超过8个的情况下,

有下面两种处理方式:

1、哈希桶的数量是没有超过64个,那么此时哈希桶数量double,然后数据迁移

2、哈希桶的数量超过了64个,将该哈希桶内部数据进行红黑树化处理

所以我们可以看到如果所有哈希桶内部数据都是链表存储的,那么每个哈希桶的数据量不会超过8个,这样当定位到某个哈希桶时,在该哈希桶继续查找也可以在O(1)时间内完成,下面看一种极端情况,所有的数据都在同一个桶里面(这种情况只在所有键值hash值相同的情况下,这种情况下查询的时间复杂度为O(lgn),比如下面给出的一个类,所有我们在设置hashmap的键值时需要特别注意),在hashmap的文档里面有这么一段描述,每个哈希桶中元素数量是成泊松分布的,

listSize = (exp(-0.5) * pow(0.5, k) / * factorial(k)),

不同数量出现的概率如下:

* 0:    0.60653066

* 1:  http://  0.30326533

* 2:    0.07581633

* 3:    0.01263606

* 4:    0.00157952

* 5:    0.00015795

* 6:    0.00001316

* 7:    0.00000094

* 8:    0.00000006

大于8: <千万分之1

通过上面的统计来看,hashmap的键值正常(不同对象的hash值不同的情况),哈希桶数量超过8个概率低于千万分之一,所以我们通常认为hashmap的查询时间复杂度为O(1)

PS:

1、哈希冲突百分百的类

/**

测试哈希冲突的类,所有的对象都返回同样的hash值

**/

public static class Student{

phttp://rivate String name;

Student(String name){

this.name = name;

}

@Override

public int hashCode(){

return 1;

}

@Override

public boolean equals(Object obj){

if(this == obj){

return true;

}

if(obj == null){

return false;

}

return this.name.equals(((Student)obj).name);

}

}

2、我们在实际使用hashmap时需要确保实现hashcode方法以及equals方法,否则不能作为hashmap的键值

3、在设置hashmap的键值hashcode方法时尽量保证较好的离散型

4、hashmap的键值需保证equals方法返回true时,hashcode必须相同,所以在实际中经常使用的键值类string,重写了equals以及hashcode方法

HashMap时间复杂度问题

HashMap底层采用了hash算法

根据 key 获得 hashCode 值

HashMap 初始有很多个类似于“桶”的数据结构,比如说预设了 10 个桶,通过 hashCode 经过一定的算法(这个算法必须是快速的)

得到这个 hashCode 应存在哪个桶中,然后内部生成 Map.Entry 对象将 key 和 value 存到桶中去。

所以一般情况下HashMap的插入和查找的时间复杂度都是O(1);

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:关于webrtc音视频开发的信息
下一篇:全国一体化政务服务平台(全国一体化政务服务平台查询)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~