，实现了可变大小的数组，随机访问和遍历元素时，提供更好的性能。...)访问元素，并索列表中的元素 List实现类：ArrayList，Vector，LinkedList 1.ArrayList是底层用数组实现的List 特点：查询效率高,增删效率低, 线程不安全...ArrayList不是线程安全的，内部采用动态数组实现 1、可随机访问，按照索引访问效率高 2、除非数组已排序，否则按照内容查找元素效率低，性能与数组长度成正比 3、添加N个元素效率为O(N)，N...为数组长度 4、插入和删除元素效率低，因为需要移动元素，具体为O(N) LinkedList内部是双向链表实现，每个元素在内存都是单独存放 1、按需分配空间 2、不可以随机访问，按照索引访问效率低...>=2，则将m加入元素个数少的堆中，然后从元素个数多的堆将根节点移除并赋值给m 迭代器 遍历一个集合中的元素，例如，显示集合中的每个元素 ；一般遍历数组都是采用for循环或者增强for，这两个方法也可以用在集合框架
HashMap之所以在每个数组元素存储的是一个链表，是为了解决hash冲突问题，当两个对象的hash值相等时，那么一个位置肯定是放不下两个值的，于是hashmap采用链表来解决这种冲突，hash值相等的两个元素会形成一个链表...Segment对象内部有一个HashEntry数组，于是每个Segment可以守护若干个桶(HashEntry),每个桶又有可能是一个HashEntry连接起来的链表，存储发生碰撞的元素。...什么时候更适合用Array？ Array可以容纳基本类型和对象，而ArrayList只能容纳对象。 Array是指定大小的，而ArrayList大小是固定的 27.哪些集合类提供对元素的随机访问？...ArrayList、HashMap、TreeMap和HashTable类提供对元素的随机访问。 28.HashSet的底层实现是什么?...一般情况下，不必指定排序模式，其迭代顺序即为默认为插入顺序。 30.LinkedList和ArrayList的区别是什么?
那么为什么要引入红黑树来替代链表呢？虽然链表的插入性能是O(1)，但查询性能确是O(n)，当哈希冲突元素非常多时，这种查询性能是难以接受的。...答案是，为了提高计算与存储效率，使每个元素对应hash值能够准确落入哈希桶数组给定的范围区间内。确定数组下标采用的算法是 hash & (n - 1)，n即为哈希桶数组的大小。...简单说下，考虑到CPU与主存之间速度的巨大差异，在CPU中引入了L1、L2、L3多级缓存，缓存中的存储单位是缓存行，缓存行大小为2的整数次幂字节，32-256个字节不等，最常见的是64字节。...这里限制的意义在于，真实并发度是由CPU核心来决定，当counterCells容量与CPU核心数量相等时，理想情况下就算所有CPU核心在同时运行不同的计数线程时，都不应该出现冲突，每个线程选择各自的cell...// 这里限制的意义在于，并发度是由CPU核心来决定，当counterCells容量与CPU核心数量相等时，理论上讲就算所有CPU核心都在同时运行不同的计数线程时，都不应该出现冲突，每个线程选择各自的cell
比如，有一个 int array[100] 的数组，当载入 array[0] 时，由于这个数组元素的大小在内存只占 4 字节，不足 64 字节，CPU 就会顺序加载数组元素到 array[15]，意味着...之所以有这么大的差距，是因为二维数组 array 所占用的内存是连续的，比如长度 N 的指是 2 的话，那么内存中的数组元素的布局顺序是这样的： 形式一用 array[i][j] 访问数组元素的顺序，...当 CPU 访问 array[0][0] 时，由于该数据不在 Cache 中，于是会「顺序」把跟随其后的 3 个元素从内存中加载到 CPU Cache，这样当 CPU 访问后面的 3 个数组元素时，就能在...我们以一个例子来看看，有一个元素为 0 到 100 之间随机数字组成的一维数组： 接下来，对这个数组做两个操作： 第一个操作，循环遍历数组，把小于 50 的数组元素置为 0； 第二个操作，将数组排序；...当数组中的元素是随机的，分支预测就无法有效工作，而当数组元素都是顺序的，分支预测器会动态地根据历史命中数据对未来进行预测，这样命中率就会很高。
），查询慢增删快，它是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的顺序所以遍历的时候会按照添加时的顺序来访问。...扩容翻转时顺序不一致使用头插法会产生死循环，导致cpu100% JDK1.8 HashMap： 底层数据结构上采用了数组＋链表＋红黑树；当链表⻓度⼤于阈值（默认为 8-泊松分布），数组的⻓度大于 64时...在表的左右进行跳跃式探测，直到找出一个空单元或查遍全表 di=1^2，-1^2，2^2，-2^2，…，k^2，-k^2 ( k<=m/2 ) 伪随机探测再散列 建立一个伪随机数发生器，并给一个随机数作为起点...具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。 优点 容易序列化 若可预知数据总数，可以创建完美哈希数列 缺点 占空间很大。...原因：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集 合在被遍历期间如果内容发生变化，就会改变modCount的值。
STL 中有哪些常见的容器 STL 中容器分为顺序容器、关联式容器、容器适配器三种类型，三种类型容器特性分别如下： 1....顺序容器 容器并非排序的，元素的插入位置同元素的值无关，包含 vector、deque、list vector：动态数组 元素在内存连续存放。随机存取任何元素都能在常数时间完成。...list： 插入和删除元素效率高，因为只需要修改相邻节点的指针。 随机访问： vector： 支持随机访问，可以通过下标快速访问元素。...list： 不支持随机访问，只能通过迭代器顺序访问元素。 空间和内存分配： vector： vector 一次性分配好内存，不够时才进行扩容。...扩容以后它的内存地址会发生改变 迭代器失效原因，有哪些情况 迭代器失效是指迭代器在遍历容器过程中，由于容器的结构发生改变而导致迭代器指向的元素不再有效。
为什么使用for循环 在JavaScript中，就像在其他编程语言中一样，我们使用循环来读取或访问集合中的项。这个集合可以是一个数组或一个对象。...PHP" // "2: Python" // "3: Java" 在循环中，我们呈现每个数组元素的索引和值。...比如，你可能想向控制台或HTML元素打印一个对象的属性和它的值。在这种情况下，for...in循环是一个不错的选择。 当使用for…in循环调试对象以及对象的值时，你应该始终记住，迭代是没有顺序的。...也就是说，迭代的顺序是随机的。所以，访问属性的顺序可能与预期不同。 不使用for…in循环的情形 现在让我们来看看for...in循环不是最佳选择的情况。...「回调函数」是你传递给另一个方法或函数的函数，作为该方法或函数执行的一部分而被执行。当涉及到JavaScript中的forEach时，它意味着回调函数将在每个迭代中执行，接收迭代中的当前项作为参数。
一种是再哈希法，当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。hashmap就是采用拉链法这种方式用链表存储解决hash碰撞的。...hashmap初始化容量时候，对容量大小做的处理，保证初始化容量为最近的2的幂次方，因为当数组长度为2的幂次方时，可以使用位运算来计算元素在数组中的下标，提高运算效率，除此之外还可以增加hash值的随机性...当负载因子为0.75,代入到泊松分布公式，计算出来长度为8时，概率=0.00000006，概率很小了，这也是为什么上面我们提到的当链表长度为8时才会转红黑树的原因。...第二个是当并发执行扩容操作时会造成环形链和数据丢失的情况，开多个线程不断进行put操作，当旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，就是因为头插法，所以最后的结果打乱了插入的顺序...，就有可能发生环形链和数据丢失的问题，引起死循环，导致CPU利用率接近100%。
在这里，我只比较两个基本解析器类型的区别： 顺序访问解析器（Sequential access parser） 随机访问解析器（Random access parser） 顺序访问意思是解析器解析数据，...顺序访问解析器只能让你在文档流中访问刚解析过的“窗口”或“事件”，而随机访问解析器允许你按照想要的方式访问遍历。 设计概要 我这里介绍的解析器设计属于随机访问变种。...随机访问解析器实现总是比顺序访问解析器慢一些，这是因为它们一般建立在某种已解析数据对象树上，数据处理器能访问上述数据。创建对象树实际上在CPU时钟上是慢的，并且耗费大量内存。...下面小节将从设计的不同方面更详细地进行介绍。 数据缓存 数据缓存是含有原始数据的一种字节或字符缓存。令牌缓存和元素缓存持有数据缓存的索引。 为了随机访问解析过了的数据，内存表示上述信息的机制是必要的。...基于读者的意见，我现在已经扩大了基准，基于四种不同的模式来测算GSON： 1、访问JSON文件所有元素，但不做任何数据处理。 2、访问JSON文件所有元素，并建立一个JSONObject。
ArrayList 是一个动态数组队列，随机访问效率高，随机插入、删除效率低。...ArrayList 底层由数组实现，允许元素随机访问，但是向 ArrayList 列表中间插入删除元素需要移位复制速度略慢；LinkList 底层由双向链表实现，适合频繁向列表中插入删除元素，随机访问需要遍历所以速度略慢...链表：LinkedList 是用双向链表实现的，HashMap 中映射到同一个链表数组的键值对是通过单向链表链接起来的，LinkedHashMap 中每个元素还加入到了一个双向链表中以维护插入或访问顺序...当 key 为 null 时 HashMap 特殊处理总是放在 Entry[] 数组的第一个元素。...LinkedHashMap 支持插入顺序或者访问顺序，LRU 算法其实就要用到它访问顺序的特性，即对一个键执行 get、put 操作后其对应的键值对会移到链表末尾，所以最末尾的是最近访问的，最开始的最久没被访问的
池分配器收到分配请求时，就会把自由链表的下一个元素取出，并传回该元素。释放元素之时，只需简单地把元素插回自由链表中。分配和释放都是O(1)的操作。...（P206 last） 避免缓存命中失败：避免数据缓存命中失败的最佳办法就是，把数据编排进连续的内存块中，尺寸越小越好，并且要顺序访问这些数据。这样便可以把数据缓存命中失败的次数减至最少。...并且，当顺序存取数据时（即不会在连续的内存块中“跳来跳去”)，便能造成最少次缓存命中失败，因为CPU不需要把相同区域的内存重载入缓存线。 链接器通用规则：1、单个函数的机器码几乎总是置于连续的内存。...容器操作：插入、移除、顺序访问/迭代、随机访问、查找、排序。 迭代器：迭代器是一种细小的类，它“知道”如何高效地访问某类容器中的元素。...迭代器像是数组索引或指针—每次它都会指向容器中某个元素，可以移至下一个元素，并能用某方式表示是否已访问容器中所有元素。
四、数组VS链表 1.插入、删除和随机访问的时间复杂度 数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。...4.如何选择 数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。...如果代码对内存的使用非常苛刻，那数组就更适合 CPU缓存机制指的是什么？为什么就数组更好了？ CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。...并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。...对于数组来说，存储空间是连续的，所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。
deque，双端队列，优点是支持快速随机访问、两端添加或删除元素很快，缺点是中间位置添加或删除元素较慢。 array，固定大小数组，与内置数组有些相似。...通常，使用 vector是最好的选择，除非你有很好的理由选择其他容器。当不确定使用那种容器时，可以在程序中只是用 vector和 list公共的操作：使用迭代器，不使用下标操作，避免随机访问。...迭代器范围通常是左闭合区间[begin, end)。迭代器范围是标准库的基础，无论是顺序容器，还是关联容器；无论是否支持随机访问的容器，对其元素的访问都可以通过迭代器完成。...使用一个容器的拷贝来创建另一个容器时，两个容器的类型及其元素类型必须当使用迭代器进行元素拷贝时，容器类型可以不同，元素类型也可以不同，只要能够进行转换即可。...而真正交换元素，则会发生元素类型的拷贝构造和析构，因此物理内存发生了改变，原来的迭代器也就失效了。
散列表是一种结合了散列函数和数组的数据结构，相当于借助散列函数对数组这种数据结构进行扩展，同时保持和利用了数组支持按照下标随机访问元素的特性。因此，可以说散列表是一种包含额外逻辑的数据结构。...其次，散列函数生成的散列值尽可能随机并且均匀分布。这样才能从散列函数角度来减少冲突的次数。即便发生了冲突，在采用链表法时，每个 slot 中的数据也会比较平均。...那么接下来我们来看一下为什么将它们放在一起使用？以及散列表和链表的联用是什么样的？ 在单纯使用链表实现 LRU 缓存淘汰算法时，我们是按照时间先后（最新访问的算是后）来维护链表结构。...由于缓存是有限的，所以链表的结点数量也是有限。因为当缓存空间不够的时候，需要淘汰一个数据的时候，那么直接将链表头部的节点删去就好。 当需要访问某个数据时，是先去缓存中查找的。...get 访问之后，顺序变为 2、1、3、5。
让我们通过一个简单的例子来看看这意味着什么：图片您可以在此图中看到，要构造最终的 8 个元素的排序数组，您只需要在 2 个 4 元素数组中迭代一次。...然后，您将另一个数组的其余元素放入 8 元素数组中。这是有效的，因为两个 4 元素数组都已排序，因此您不需要在这些数组中“返回”。现在我们已经理解了这个技巧，这是我的合并排序伪代码。...对于 CPU 成本，我应该计算每个操作，例如加法、“if 语句”、乘法、迭代……此外：每个高级代码操作都有特定数量的低级 CPU 操作。...很难给出一个数量级，因为它取决于您需要执行的操作：顺序访问（例如：全扫描）与随机访问（例如：按行 ID 访问），读与写以及数据库使用的磁盘类型：7.2k/10k/15k 转硬盘固态硬盘RAID 1/5/...换句话说，当表/索引的大小大于缓冲区的大小时会发生什么？使用此算法将删除缓存中所有先前的值，而来自全扫描的数据可能只使用一次。
数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。...即缓存的特点 缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要用到缓存淘汰策略。 3）什么是缓存淘汰策略？ 指的是当缓存被用满时清理数据的优先顺序。...6）数组实现LRU缓存淘汰策略 方式一：首位置保存最新访问数据，末尾位置优先清理 当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为...O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。...方式二：首位置优先清理，末尾位置保存最新访问数据 当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置
v2 v3 v4 访问顺序： 1 2 3 4 5 如上所示，向量v的元素是被顺序读取的，一个接一个，按照它们存储在内存中的顺序（为了方便，我们假设数组是从地址0开始的）。...因此，对于变量v，函数有很好的空间局部性，但是时间局部性很差，因为每个向量元素只被访问一次。 步长为1的引用模式为顺序引用模式（ sequential reference pattern）。...一般而言，随着步长的增加，空间局部性下降。 如下的函数 sumarrayrows，它对一个二维数组的元素求和。双重嵌套循环按照行优先顺序（row major order）读数组的元素。...也就是，内层循环读第一行的元素，然后读第二行，依此类推。函数 sumarrayrows具有良好的空间局部性，因为它按照数组被存储的行优先顺序来访问这个数组。...当发生缓存不命中时，第k层的缓存从第k+1层缓存中取出包含d的那个块，如果第k层的缓存已经满了，可能就会覆盖现存的一个块。（缓存的替换策略：随机替换替换策略，最少被使用（LRU）替换策略）。
该迭代顺序可以是插入顺序或者是访问顺序，这个可以在初始化的时候确定，默认采用插入顺序来维持取出键值对的次序。...LRU即Least Recently Used，最近最少使用，也就是说，当缓存满了，会优先淘汰那些最近最不常访问的数据。...下面是一个最简单的LRU缓存的实现，当size超过maxElement时，每次新增一个元素时，就会移除最久远的元素。...默认情况下不保证访问者公平的访问队列，所谓公平访问队列是指阻塞的所有生产者线程或消费者线程，当队列可用时，可以按照阻塞的先后顺序访问队列，即先阻塞的生产者线程，可以先往队列里插入元素，先阻塞的消费者线程...第二行代码是让 CPU 自旋等待消费者消费元素。因为自旋会消耗 CPU，所以自旋一定的次数后使用 Thread.yield() 方法来暂停当前正在执行的线程，并执行其他线程。
我们理解了内存IO的内部实现过程，知道了内存的随机IO比顺序IO要慢，并对延迟时间进行了大概的估算。...那么我们今天来用代码的方式来实践一下，看看在我们的项目工程中，内存访问的在不同的访问场景下延时究竟是个什么表现。...内存IO发生较少，大部分都是高效的缓存IO，所以我这里看到的内存延时只有1ns左右，这其实只是虚拟地址转换+L1访问的延时。...我们假设它全部能命中高速缓存，所以暂且忽略它的影响。 随机实验场景：数组从32K到64M 图4 随机访问 这次的数组访问就没有步长的概念了，全部打乱，随机访问。...内存存在随机访问比顺序访问慢的多的情况，大概是4:1的关系。所以不要觉得内存很快，就用起来太随性了!
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
