hashmap的链表里存什么?
实际上是指HashMap中的链表节点。在Java中,HashMap使用链表来解决哈希冲突的问题。当多个键映射到同一个哈希桶时,这些键值对会以链表的形式存储在该桶中。
每个链表节点包含两个主要部分:键和值。键用于唯一标识每个键值对,而值则是与键相关联的数据。当我们向HashMap中插入一个键值对时,HashMap会根据键的哈希值找到对应的桶,然后将键值对作为一个链表节点插入到该桶中。
需要注意的是,由于Java 8引入了红黑树优化,当链表长度超过一定阈值时,链表会转换为红黑树,以提高查找效率。因此,在HashMap的链表中,可能存储的是普通的链表节点,也可能是红黑树节点。
为何主流语言中,无任何技巧下直接暴力遍历数组、链表,多数情况链表更快?
首先搞清楚数组和链表的差异。
数组是在一整块连续的内存中存储数据,每一项数组成员大小相同。保存数组需要记录数组的起始地址、数组成员占用内存大小、数组长度;数组成员中记录了数据、类型。
下面用一个便于理解的方式举个关于数组的例子:
某数组起始位置在内存地址0上,每个数组成员占10byte,那么[0]在内存地址0,[2]在内存地址20,遍历数组的方式是根据数组起始位置+索引*数组成员大小。
链表是存储不需要一整块连续的内存,保存链表只要记录链表表头地址即可;每一项链表成员中保存了数据、数据类型、下一个成员的地址,另双向链表还会保存上一个成员的地址。
下面用一个便于理解的方式举个关于链表的例子:
某链表的表头在内存地址1000,访问它可获得数据和下一项数据地址是1234,遍历链表的方式是依次访问每一链的数据和下一链的地址,下一链的地址是直接获取,不需要计算。
再来说说题主的问题,为什么通常只是遍历那么链表性能略好一些,因为遍历链表时少做了一个加法和一个乘法运算。
那么实际上为啥链表总得很少数组用得很多呢?
原因主要有2条:
一、按索引随机访问成员时数组的效率比链表高很多。即顺序访问链表性能略高于数组,随机访问数组性能远高于链表。整体性能数组胜出。
二、使用数组时数组是连续存储,产生的内存碎片的几率和数量比链表少很多。
最后:所有的编程语言都支持数组,有相当多的编程语言不直接支持链表。因为链表的功能和数组的功能重叠,综合性能略差,而且使用链表要直接接触内存地址,容易产生内存地址越界、数据不安全的情况。
Show me the code. 下结论前先要证明你的结论是对的。
据我所知,没有任何一个语言“只是遍历”的话,链表会比数组快。
链表是否连续生成的,不会影响遍历速度。