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

我不是女神ヾ 2023-07-12 09:17 13阅读 0赞

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70][]

上面就是hashmap的底层存储示意图，要想查看一个键值对应的值，首先根据该键值的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:    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{
            private 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方法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200308102010685.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pvaG4xMzM3,size_16,color_FFFFFF,t_70