阿里面试90%以上会问到的数据结构;HashMap

简介: BAT面试必问;关于hashmap,你知道多少?你知道hashmap的工作原理吗?1.该问题很有深度2.能答出多少决定岗位和薪资.3.问题的方式多种多样一.首先我们了解下HashMap是什么HashMap是Java常用的用来储存键值对的数据结构,它是线程不安全的,可以储存null键值,这些大家经常用,也都知道,接下来根据源码分析一下HashMap的实现。

BAT面试必问;

关于hashmap,你知道多少?你知道hashmap的工作原理吗?

1.该问题很有深度

2.能答出多少决定岗位和薪资.

3.问题的方式多种多样

一.首先我们了解下HashMap是什么

HashMap是Java常用的用来储存键值对的数据结构,它是线程不安全的,可以储存null键值,这些大家经常用,也都知道,接下来根据源码分析一下HashMap的实现。

1、实现原理

HashMap采用数组散列+链表的方式来储存键值对,键值对的对象实现如下:

static class Entry<K,V> implements Map.Entry<K,V> { 
 final K key; 
 V value; 
 Entry<K,V> next; 
 final int hash; 
 …… 
} 

通过一个Entry的数组table就实现了多个对象的保存,使用哈希值和键值解决了在插入和查找时的冲突。

2、put方法,写入键值对

public V put(K key, V value){
 //如果 key 为 null,调用 putForNullKey 方法写入null键的值
 if (key == null){
 return putForNullKey(value);
}
//根据 key 的 keyCode 计算 Hash 值 
int hash = hash(key.hashCode());
//查找hash值在table中的索引
int i = indexFor(hash, table.length);
// 如果 i 索引处的 Entry 不为 null,通过循环不断遍历链表查找是否在链表中有相同key的Entry
for (Entry<K,V> e = tablei; e != null; e = e.next) {
 Object k;
 //找到与插入的值的key和hash相同的Entry
 if (e.hash == hash && ((k = e.key) == key|| key.equals(k)){
 //key值相同时直接替换value值,跳出函数
 V oldValue = e.value;
 e.value = value; e.recordAccess(this); return oldValue; } }
// 如果 i 索引处的 Entry 为 null 或者key的hash值相同而key不同 ,则需要新增Entry
modCount++; 
// 将 key、value 添加到 i 索引处
addEntry(hash, key, value, i); 
return null; 
} 

在put方法中解决hash碰撞的方式很清楚,即当两个entry的hash值相同时,需要对key值是否相同进行判断,只有key和hash都相同,才能进行修改,否则认为不是同一个entry。

3.addEntry的实现

代码:

void addEntry(int hash, K key, V value, int bucketIndex) { // 获取指定 bucketIndex 索引处的 Entry
Entry<K,V> e = tablebucketIndex; 
tablebucketIndex = new Entry<K,V>(hash, key, value, e); // 如果 Map 中的 key-value 对的数量超过了极限
if (size++ >= threshold)
 resize(2 table.length);
} 

在创建新Entry时如果table的bucketIndex处有元素的话,创建时需要将entry的next设置为原先存储的元素。

二,HashMap工作原理

以下为目录,有需要完整进阶视频可以加Android进阶群;701740775免费获取

1.目录

 

2.顺序表与链表

 

3.Hsh表

 

 

 

4.Hash源码

 

5.碰撞

 

需要完整进阶视频详解可以加Android进阶群;701740775免费获取!

附录Android高级技术大纲和进阶视频;

 

相关文章
|
2月前
|
存储 关系型数据库 MySQL
阿里面试:为什么要索引?什么是MySQL索引?底层结构是什么?
尼恩是一位资深架构师,他在自己的读者交流群中分享了关于MySQL索引的重要知识点。索引是帮助MySQL高效获取数据的数据结构,主要作用包括显著提升查询速度、降低磁盘I/O次数、优化排序与分组操作以及提升复杂查询的性能。MySQL支持多种索引类型,如主键索引、唯一索引、普通索引、全文索引和空间数据索引。索引的底层数据结构主要是B+树,它能够有效支持范围查询和顺序遍历,同时保持高效的插入、删除和查找性能。尼恩还强调了索引的优缺点,并提供了多个面试题及其解答,帮助读者在面试中脱颖而出。相关资料可在公众号【技术自由圈】获取。
|
2月前
|
存储 Java
Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。
【10月更文挑战第19天】本文详细介绍了Java中的HashMap和TreeMap,通过具体示例展示了它们在处理复杂数据结构问题时的应用。HashMap以其高效的插入、查找和删除操作著称,而TreeMap则擅长于保持元素的自然排序或自定义排序,两者各具优势,适用于不同的开发场景。
46 1
|
2月前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
64 2
|
9天前
|
存储 Java Serverless
深入探索:HashMap的底层数据结构揭秘
HashMap作为Java中一个非常重要的集合类,其底层数据结构的设计对于性能有着至关重要的影响。本文将详细解析HashMap的底层数据结构,帮助开发者更好地理解和使用这一强大的工具。
26 7
|
18天前
|
SQL 关系型数据库 MySQL
阿里面试:1000万级大表, 如何 加索引?
45岁老架构师尼恩在其读者交流群中分享了如何在生产环境中给大表加索引的方法。文章详细介绍了两种索引构建方式:在线模式(Online DDL)和离线模式(Offline DDL),并深入探讨了 MySQL 5.6.7 之前的“影子策略”和 pt-online-schema-change 方案,以及 MySQL 5.6.7 之后的内部 Online DDL 特性。通过这些方法,可以有效地减少 DDL 操作对业务的影响,确保数据的一致性和完整性。尼恩还提供了大量面试题和解决方案,帮助读者在面试中充分展示技术实力。
|
2月前
|
消息中间件 存储 canal
阿里面试:canal+MQ,会有乱序的问题吗?
本文详细探讨了在阿里面试中常见的问题——“canal+MQ,会有乱序的问题吗?”以及如何保证RocketMQ消息有序。文章首先介绍了消息有序的基本概念,包括全局有序和局部有序,并分析了RocketMQ中实现消息有序的方法。接着,针对canal+MQ的场景,讨论了如何通过配置`canal.mq.partitionsNum`和`canal.mq.partitionHash`来保证数据同步的有序性。最后,提供了多个与MQ相关的面试题及解决方案,帮助读者更好地准备面试,提升技术水平。
阿里面试:canal+MQ,会有乱序的问题吗?
|
2月前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
57 5
|
2月前
|
消息中间件 架构师 Java
阿里面试:秒杀的分布式事务, 是如何设计的?
在40岁老架构师尼恩的读者交流群中,近期有小伙伴在面试阿里、滴滴、极兔等一线互联网企业时,遇到了许多关于分布式事务的重要面试题。为了帮助大家更好地应对这些面试题,尼恩进行了系统化的梳理,详细介绍了Seata和RocketMQ事务消息的结合,以及如何实现强弱结合型事务。文章还提供了分布式事务的标准面试答案,并推荐了《尼恩Java面试宝典PDF》等资源,帮助大家在面试中脱颖而出。
|
2月前
|
SQL 关系型数据库 MySQL
阿里面试:MYSQL 事务ACID,底层原理是什么? 具体是如何实现的?
尼恩,一位40岁的资深架构师,通过其丰富的经验和深厚的技術功底,为众多读者提供了宝贵的面试指导和技术分享。在他的读者交流群中,许多小伙伴获得了来自一线互联网企业的面试机会,并成功应对了诸如事务ACID特性实现、MVCC等相关面试题。尼恩特别整理了这些常见面试题的系统化解答,形成了《MVCC 学习圣经:一次穿透MYSQL MVCC》PDF文档,旨在帮助大家在面试中展示出扎实的技术功底,提高面试成功率。此外,他还编写了《尼恩Java面试宝典》等资料,涵盖了大量面试题和答案,帮助读者全面提升技术面试的表现。这些资料不仅内容详实,而且持续更新,是求职者备战技术面试的宝贵资源。
阿里面试:MYSQL 事务ACID,底层原理是什么? 具体是如何实现的?
|
2月前
|
Kubernetes 架构师 算法
阿里面试:全国14亿人,统计出重名最多的前100个姓名
文章介绍了如何解决“从全国14亿人的数据中统计出重名人数最多的前100位姓名”的面试题,详细分析了多种数据结构的优缺点,最终推荐使用前缀树(Trie)+小顶堆的组合。文章还提供了具体的Java代码实现,并讨论了在内存受限情况下的解决方案,强调了TOP N问题的典型解题思路。最后,鼓励读者通过系统化学习《尼恩Java面试宝典》提升面试技巧。
阿里面试:全国14亿人,统计出重名最多的前100个姓名