系统化的学习技术、研究技术而不是使用技术

集合框架笔记--HashMap

更新于:2018/09/20 14:49:10 分类:Java技术

一、哈希表

在讨论哈希表之前, 先大概了解一下其他数据结构在插入、删除、查找等基础操作的执行性能。

数组 采用连续的物理单元存储数据,通过下标检索数据时,时间复杂度为O(1);通过给定值检索数据时,需要遍历整个数组,逐一比对数组元素,复杂度为O(n);如果是有序数组,可以通过算法进行查找,其复杂度可提高为O(log(n));对于数组的插入删除,涉及到平移元素,平均复杂度为O(n)。

线性链表 对于链表的插入删除,仅需要处理结点间的引用,复杂度为O(1);而查找元素需要遍历链表,复杂度为O(n)。

二叉树 对一棵相对平衡的有序二叉树,对其进行插入、删除、查找等操作,平均复杂度均为O(logn)。

哈希表 相比于前面几种结构,哈希表在处理插入、删除、查找等操作,性能非常高。在不考虑哈希冲突的情况下,仅需一次定位即可完成,时间复杂度为O(1)。

什么是哈希表(wikipedia)(需要翻墙)

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。哈希表的主干就是数组

哈希冲突 (也叫哈希碰撞),当两个不同的元素经过哈希函数计算后,得到了相同的存储地址,这样就发生了哈希冲突。好的哈希函数会尽可能地保证计算简单散列地址分布均匀,但是需要知道的是,数组是一块连续固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝不发生冲突。

哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而HashMap即是采用了链地址法,也就是数组+链表的方式。

哈希碰撞的文章可以看一下阮一峰老师的这篇文章,解释得通俗易懂。

二、HashMap实现原理

HashMap的主干是Entry数组,在HashMap中有一个静态类Entry(jdk1.8已经改为Node),实现了Map接口中定义的Entry接口,每一个Entry包含一个(key-value)键值对。

// JDK中的注释
// 该表在首次使用时初始化,并根据需要重新调整大小,分配时,长度始终时2的幂,允许长度为0
transient Node<K,V>[] table = (Node<K,V>[]) EMPTY_TABLE;

HashMap的结构如下图:

image

HashMap是由数组+链表组成的,数组是HashMap的主体,链表主要是为了解决哈希冲突而存在的。如果定位 到的数组位置不含链表(即当前Node的next指向Null),那么对于查找、添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过Key对象的equals方法逐一比对查找。所以,从性能考虑,HashMap中链表出现越少,性能才会越好。

三、重写equals方法时需同时重写hashCode方法

为什么重写equals方法之后,需要同时重写hashCode方法呢,我们来看一下HashMap的源码

注意:这是从JDK1.8源码HashMap类中拷贝出来的片段

 public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

这段代码是HashMap的get方法,从代码中可以看到,在匹配关键字(key)的时候,首先会比对hash(first.hash==hashe.hash==hash),也就是说如果关键字通过hashCode计算出的hash不一致的话,那么获取到的数据就是null。

四、为什么HashMap的数组长度一定是2的次幂

从二进制的角度考虑,减少哈希冲突。(只作参考)

五、红黑树

为了解决链表长度过长带来的性能问题,Java8引入了红黑树。当链表长度太长(默认超过8)时,链表就转换为红黑树,利用红黑树快速增删改查的特点提高HashMap的性能,其中会用到红黑树的插入、删除、查找等算法。

参考文章:HashMap实现原理及源码分析

留言(0)

给我留言