数据结构

HashMap简介 HashMap核心数据结构Hash表 = 数组 + 线性链表 + 红黑树 为什么初始容量是2的指数幂?如果创建HashMap时指定的大小不是2的指数就会报错吗? 1Map map = new HashMap<>(13); 这行代码在编译的时候也不会报错,那为什么说初始容量是2的指数呢? 看一下HashMap的构造器 1234567891011121314151617181920212223public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if ( ...

HashMap的最大容量是多少.首先, HashMap底层是数组+链表, 所以HashMap的容量约等于 数组长度 * 链表长度.因为链表长度不固定,甚至可能链表会是树结构, 所以我们主要讨论数组长度. 那么, 数组的最大长度是多长呢? 仔细想想, 好像这么多年也没去看过数组的源码(笑). 1234567一是规范隐含的限制。Java数组的length必须是非负的int，所以它的理论最大值就是java.lang.Integer.MAX_VALUE = 2^31-1 = 2147483647。二是具体的实现带来的限制。这会使得实际的JVM不一定能支持上面说的理论上的最大length。例如说如果有JVM使用uint32_t来记录对象大小的话，那可以允许的最大的数组长度（按元素的个数计算）就会是：(uint32_t的最大值 - 数组对象的对象头大小) / 数组元素大小 嗯..数组长度理论上可以达到 2^31-1 这么长, 那么HashMap的最大长度也是这么了? 不, 在HashMap中规定HashMap底层数组的元素最大为 1<<30 1static final int M ...

数据结构简介前言数据结构是为实现对计算机数据有效使用的各种数据组织形式，服务于各类计算机操作。不同的数据结构具有各自对应的适用场景，旨在降低各种算法计算的时间与空间复杂度，达到最佳的任务执行效率。 如下图所示，常见的数据结构可分为「线性数据结构」与「非线性数据结构」，具体为：「数组」、「链表」、「栈」、「队列」、「树」、「图」、「散列表」、「堆」。 从零开始学习算法的同学对数据结构的使用方法可能尚不熟悉，本节将初步介绍各数据结构的基本特点，与 Python3 , Java , C++ 语言中各数据结构的初始化与构建方法。 代码运行可使用本地 IDE 或 力扣 PlayGround 。 数组数组是将相同类型的元素存储于连续内存空间的数据结构，其长度不可变。 如下图所示，构建此数组需要在初始化时给定长度，并对数组每个索引元素赋值，代码如下： 12345678// 初始化一个长度为 5 的数组 arrayint[] array = new int[5];// 元素赋值array[0] = 2;array[1] = 3;array[2] = 1;array[3] = 0;array[4] ...