当前位置 博文首页 > 梦梦~~的博客:面试高频知识点整理——HashMap底层数据结构以及
????????在面试中,集合是大概率都会被问到的一个技术点,尤其是HashMap,无论你是应届生面试还是有个三五年的工作经验的,有工作经验的问的就会深一点,可能会被问到底层吧,不过小编就是个应届生而已,上次面试的时候就被问到底层了,呜呜呜呜呜呜呜呜。回到家,我百度查资料整理了一份关于HashMap的知识点。
????????回答:在jdk1.8之前,HashMap的底层数据结构是数组+链表,也称为哈希表。
???????????????????jdk1.8以及1.8之后,HashMap的底层数据结构是数组+链表+红黑树,也称为哈希表。
????????关于这个面试题,我真的很想吐槽一下,我一个应届生,就问我这个问题,害,当时觉得真的太难为我了吧。其实后来回到家想了想,其实也不是他们为难我,他们可能在用这个问题来衡量我学习能力的强弱吧。面试之前我是真的没有看过底层,当时我只能无奈都说没了解过,最后也没应聘上。后来我就开始借助一些视频来辅助我看底层。
????????首先可以先给大家看一个图,这个图不是我自己画的,是看视频的时候觉得挺不错的,就截下来了。
????????
????????上面说了那么多,其实总结HashMap的存储过程就一句话:HashMap内部维护了一个存储数据的Entry[]或者Node[]数组,采用链表来解决哈希冲突,每一个Entry或者Node节点其实都是一个单向链表。
????????
????????回答:可以,但是依旧遵循“key唯一”这一规则。
????????1,HashMap继承的父类AbstractMap已经实现类Map接口,可是HashMap集合自己又实现了一次Map接口,重复操作, 集合的创始人也承认这是一个多余的操作。
????????2,HashMap底层的一些重要属性:
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 这是要赋值给数组的长度
static final int MAXIMUM_CAPACITY = 1 << 30; //定义了一个很大很大的数
static final float DEFAULT_LOAD_FACTOR = 0.75f; //定义了一个浮点类型数值:0.75,也称负载因子,加载因子
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; //底层主数组
transient int size; //数组中实际添加的数量
int threshold; //定义了一个变量,没赋值,默认为0。表示底层数组扩容时的界限值,边界
final float loadFactor; //用来操作、接收加载因子
*
回答:
????????如果装填因子设置大的话为1:空间利用率得到了很大的满足,但是呢,容易发生碰撞,产生链表,从而大致查询效率低。
????????如果装填因子设置小的话为0.5:碰撞率低,不容易产生链表,查询效率高,但是空间利用率减低了
????????所以负载因子就取了一个中间值,在空间和时间上一个折中。
回答:
????????原因1:h & (length-1) 等效 h%length的操作 等效的前提就是:length的长度必须是2的整数倍。
????????原因2:防止哈希值冲突,位置冲突。
????????