Java 集合之一 —HashMap(一)

简介: Java 集合之一 —HashMap

深入浅出学 Java——HashMap

哈希表(hash table)

也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如 memcached)的核心其实就是在内存中维护一张大的哈希表,本文会对 java 集合框架中 HashMap 的实现原理进行讲解,并对 JDK7 的 HashMap 源码进行分析。

一、什么是哈希表

在讨论哈希表之前,我们先大概了解下其他数据结构在新增,查找等基础操作执行性能

数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为 O (1);通过给定值进行查找,需要遍历数组,逐一比对给定关键字和数组元素,时间复杂度为 O (n),当然,对于有序数组,则可采用二分查找,插值查找,斐波那契查找等方式,可将查找复杂度提高为 O (logn);对于一般的插入删除操作,涉及到数组元素的移动,其平均复杂度也为 O (n)

线性链表:对于链表的新增,删除等操作(在找到指定操作位置后),仅需处理结点间的引用即可,时间复杂度为 O (1),而查找操作需要遍历链表逐一进行比对,复杂度为 O (n)

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

哈希表:相比上述几种数据结构,在哈希表中进行添加,删除,查找等操作,性能十分之高,不考虑哈希冲突的情况下(后面会探讨下哈希冲突的情况),仅需一次定位即可完成,时间复杂度为 O (1),接下来我们就来看看哈希表是如何实现达到惊艳的常数阶 O (1) 的。

我们知道,数据结构的物理存储结构只有两种:顺序存储结构链式存储结构(像栈,队列,树,图等是从逻辑结构去抽象的,映射到内存中,也这两种物理组织形式),而在上面我们提到过,在数组中根据下标查找某个元素,一次定位就可以达到,哈希表利用了这种特性,哈希表的主干就是数组

比如我们要新增或查找某个元素,我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置,通过数组下标一次定位就可完成操作。


这个函数可以简单描述为:存储位置 = f (关键字) ,这个函数 f 一般称为哈希函数,这个函数的设计好坏会直接影响到哈希表的优劣。举个例子,比如我们要在哈希表中执行插入操作:

插入过程如下图所示

查找操作同理,先通过哈希函数计算出实际存储地址,然后从数组中对应地址取出即可。

哈希冲突

然而万事无完美,如果两个不同的元素,通过哈希函数得出的实际存储地址相同怎么办?也就是说,当我们对某个元素进行哈希运算,得到一个存储地址,然后要进行插入的时候,发现已经被其他元素占用了,其实这就是所谓的哈希冲突,也叫哈希碰撞。前面我们提到过,哈希函数的设计至关重要,好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是,我们需要清楚的是,数组是一块连续的固定长度的内存空间,再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢?哈希冲突的解决方案有多种:开放定址法(发生冲突,继续寻找下一块未被占用的存储地址),再散列函数法,链地址法,而 HashMap 即是采用了链地址法,也就是数组 + 链表的方式。

二、HashMap 的实现原理

HashMap 的主干是一个 Entry 数组。Entry 是 HashMap 的基本组成单元,每一个 Entry 包含一个 key-value 键值对。(其实所谓 Map 其实就是保存了两个对象之间的映射关系的一种集合)

//HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂。
//至于为什么这么做,后面会有详细分析。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Entry 是 HashMap 中的一个静态内部类。代码如下

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
        int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算
        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

所以,HashMap 的总体结构如下:

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

其他几个重要字段

/**实际存储的key-value键值对的个数*/
transient int size;
/**阈值,当table == {}时,该值为初始容量(初始容量默认为16);当table被填充了,也就是为table分配内存空间后,
threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold,后面会详细谈到*/
int threshold;
/**负载因子,代表了table的填充度有多少,默认是0.75
加载因子存在的原因,还是因为减缓哈希冲突,如果初始桶为16,等到满16个元素才扩容,某些桶里可能就有不止一个元素了。
所以加载因子默认为0.75,也就是说大小为16的HashMap,到了第13个元素,就会扩容成32。
*/
final float loadFactor;
/**HashMap被改变的次数,由于HashMap非线程安全,在对HashMap进行迭代时,
如果期间其他线程的参与导致HashMap的结构发生变化了(比如put,remove等操作),
需要抛出异常ConcurrentModificationException*/
transient int modCount;

HashMap 有 4 个构造器,其他构造器如果用户没有传入 initialCapacity 和 loadFactor 这两个参数,会使用默认值

initialCapacity 默认为 16,loadFactory 默认为 0.75

我们看下其中一个

public HashMap(int initialCapacity, float loadFactor) {
     //此处对传入的初始容量进行校验,最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        threshold = initialCapacity;
     
        init();//init方法在HashMap中没有实际实现,不过在其子类如 linkedHashMap中就会有对应实现
    }

从上面这段代码我们可以看出,在常规构造器中,没有为数组 table 分配内存空间(有一个入参为指定 Map 的构造器例外),而是在执行 put 操作的时候才真正构建 table 数组

OK, 接下来我们来看看 put 操作的实现

public V put(K key, V value) {
        //如果table数组为空数组{},进行数组填充(为table分配实际内存空间),入参为threshold,
        //此时threshold为initialCapacity 默认是1<<4(24=16)
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
       //如果key为null,存储位置为table[0]或table[0]的冲突链上
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);//对key的hashcode进一步计算,确保散列均匀
        int i = indexFor(hash, table.length);//获取在table中的实际位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        //如果该对应数据已存在,执行覆盖操作。用新value替换旧value,并返回旧value
            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;
            }
        }
        modCount++;//保证并发访问时,若HashMap内部结构发生变化,快速响应失败
        addEntry(hash, key, value, i);//新增一个entry
        return null;
    }

inflateTable 这个方法用于为主干数组 table 在内存中分配存储空间,通过 roundUpToPowerOf2 (toSize) 可以确保 capacity 为大于或等于 toSize 的最接近 toSize 的二次幂,比如 toSize=13, 则 capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

private void inflateTable(int toSize) {
        int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
        /**此处为threshold赋值,取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值,
        capaticy一定不会超过MAXIMUM_CAPACITY,除非loadFactor大于1 */
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

roundUpToPowerOf2 中的这段处理使得数组长度一定为 2 的次幂,Integer.highestOneBit 是用来获取最左边的 bit(其他 bit 位为 0)所代表的数值.

private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

hash 函数

/**这是一个神奇的函数,用了很多的异或,移位等运算
对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀*/
final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

以上 hash 函数计算出的值,通过 indexFor 进一步处理来获取实际的存储位置

/**
     * 返回数组下标
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

h&(length-1)保证获取的 index 一定在数组范围内,举个例子,默认容量 16,length-1=15,h=18, 转换成二进制计算为 index=2。位运算对计算机来说,性能更高一些(HashMap 中有大量位运算)

所以最终存储位置的确定流程是这样的:

再来看看 addEntry 的实现:

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);//当size超过临界阈值threshold,并且即将发生哈希冲突时进行扩容
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

通过以上代码能够得知,当发生哈希冲突并且 size 大于阈值的时候,需要进行数组扩容,扩容时,需要新建一个长度为之前数组 2 倍的新的数组,然后将当前的 Entry 数组中的元素全部传输过去,扩容后的新数组长度为之前的 2 倍,所以扩容相对来说是个耗资源的操作。

相关文章
|
8天前
|
存储 安全 Java
Java 集合框架中的老炮与新秀:HashTable 和 HashMap 谁更胜一筹?
嗨,大家好,我是技术伙伴小米。今天通过讲故事的方式,详细介绍 Java 中 HashMap 和 HashTable 的区别。从版本、线程安全、null 值支持、性能及迭代器行为等方面对比,帮助你轻松应对面试中的经典问题。HashMap 更高效灵活,适合单线程或需手动处理线程安全的场景;HashTable 较古老,线程安全但性能不佳。现代项目推荐使用 ConcurrentHashMap。关注我的公众号“软件求生”,获取更多技术干货!
30 3
|
2月前
|
Java
Java之HashMap详解
本文介绍了Java中HashMap的源码实现(基于JDK 1.8)。HashMap是基于哈希表的Map接口实现,允许空值和空键,不同步且线程不安全。文章详细解析了HashMap的数据结构、主要方法(如初始化、put、get、resize等)的实现,以及树化和反树化的机制。此外,还对比了JDK 7和JDK 8中HashMap的主要差异,并提供了使用HashMap时的一些注意事项。
100 2
Java之HashMap详解
|
25天前
|
存储 缓存 安全
Java 集合江湖:底层数据结构的大揭秘!
小米是一位热爱技术分享的程序员,本文详细解析了Java面试中常见的List、Set、Map的区别。不仅介绍了它们的基本特性和实现类,还深入探讨了各自的使用场景和面试技巧,帮助读者更好地理解和应对相关问题。
42 5
|
2月前
|
存储 缓存 安全
Java 集合框架优化:从基础到高级应用
《Java集合框架优化:从基础到高级应用》深入解析Java集合框架的核心原理与优化技巧,涵盖列表、集合、映射等常用数据结构,结合实际案例,指导开发者高效使用和优化Java集合。
46 4
|
2月前
|
Java
Java 8 引入的 Streams 功能强大,提供了一种简洁高效的处理数据集合的方式
Java 8 引入的 Streams 功能强大,提供了一种简洁高效的处理数据集合的方式。本文介绍了 Streams 的基本概念和使用方法,包括创建 Streams、中间操作和终端操作,并通过多个案例详细解析了过滤、映射、归并、排序、分组和并行处理等操作,帮助读者更好地理解和掌握这一重要特性。
39 2
|
2月前
|
存储 Java
判断一个元素是否在 Java 中的 Set 集合中
【10月更文挑战第30天】使用`contains()`方法可以方便快捷地判断一个元素是否在Java中的`Set`集合中,但对于自定义对象,需要注意重写`equals()`方法以确保正确的判断结果,同时根据具体的性能需求选择合适的`Set`实现类。
|
2月前
|
安全 Java
Java多线程集合类
本文介绍了Java中线程安全的问题及解决方案。通过示例代码展示了使用`CopyOnWriteArrayList`、`CopyOnWriteArraySet`和`ConcurrentHashMap`来解决多线程环境下集合操作的线程安全问题。这些类通过不同的机制确保了线程安全,提高了并发性能。
|
2月前
|
存储 Java 开发者
在 Java 中,如何遍历一个 Set 集合?
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观,适用于大多数简单的遍历场景;迭代器则更加灵活,可在遍历过程中进行更多复杂的操作;而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
|
2月前
|
存储 Java 开发者
Java中的集合框架深入解析
【10月更文挑战第32天】本文旨在为读者揭开Java集合框架的神秘面纱,通过深入浅出的方式介绍其内部结构与运作机制。我们将从集合框架的设计哲学出发,探讨其如何影响我们的编程实践,并配以代码示例,展示如何在真实场景中应用这些知识。无论你是Java新手还是资深开发者,这篇文章都将为你提供新的视角和实用技巧。
37 0
|
5月前
|
存储 安全 Java
一天十道Java面试题----第二天(HashMap和hashTable的区别--------》sleep、wait、join)
这篇文章是关于Java面试的第二天笔记,涵盖了HashMap与HashTable的区别、ConcurrentHashMap的实现原理、IOC容器的实现方法、字节码的概念和作用、Java类加载器的类型、双亲委派模型、Java异常体系、GC如何判断对象可回收、线程的生命周期及状态,以及sleep、wait、join、yield的区别等十道面试题。
一天十道Java面试题----第二天(HashMap和hashTable的区别--------》sleep、wait、join)